區域性與記憶體階層 (Locality & the Memory Hierarchy)

Overview Table

6.2 區域性 (Locality) (p.640-641)

寫得好的程式傾向展現良好區域性 (locality):引用的資料項靠近最近引用過的項目,或就是剛引用過的項目本身。此區域性原理 (principle of locality) 深刻影響硬體與軟體系統的設計與效能,具有兩種形式:

• Temporal locality(時間區域性):某記憶體位置被引用一次後,近期內很可能再被引用多次。
• Spatial locality(空間區域性):某位置被引用後,程式很可能在近期引用其鄰近位置。
• 通則:區域性好的程式跑得比區域性差的程式快,因此從硬體、OS 到應用程式都圍繞它設計。

各層級如何利用區域性:

背景(p.640, Figure 6.16):CPU 與 DRAM/disk 的速度差距(processor–memory gap)逐年擴大,現代電腦大量使用 SRAM-based cache 來彌補——這個做法之所以有效,正是因為程式的區域性。

6.2.1 程式資料引用的區域性 (p.642-643)

以 sumvec(循序加總向量)為例,判斷函式區域性的方法是逐一檢視每個變數的引用模式:

• sum(scalar):每次迭代都引用 → temporal locality 好;是純量 → 無 spatial locality。
• v[i]:依儲存順序循序讀取 → spatial locality 好;每元素只讀一次 → temporal locality 差。
• 迴圈本體中每個變數至少擁有一種好的區域性 → 整體判定 sumvec 區域性良好。

Stride 引用模式:

• stride-1 reference pattern(又稱 sequential reference pattern):循序訪問向量的每個元素(以元素大小為單位),是程式中 spatial locality 一種常見且重要的來源。
• stride-k reference pattern:每隔 k 個元素訪問一次。stride 越大,spatial locality 越差。

二維陣列的迴圈順序決定 stride(C 陣列以 row-major order 儲存):

記憶體佈局 (int a[2][3], row-major, 每元素 4 bytes):

Address:    0     4     8     12    16    20
Content:  a00 | a01 | a02 | a10 | a11 | a12

sumarrayrows 訪問順序:  1  2  3  4  5  6   (stride-1, 循序)
sumarraycols 訪問順序:  1  3  5  2  4  6   (stride-N=3, 跳躍)

6.2.2 指令擷取的區域性 (p.643-644)

程式指令也儲存在記憶體、須由 CPU 擷取 (fetch),因此同樣可以評估程式對指令擷取的區域性:

• 迴圈本體的指令依循序記憶體順序執行 → spatial locality 好。
• 迴圈本體被執行多次 → temporal locality 好。
• 程式碼與資料的重要差異:code 在執行期幾乎不會被修改——CPU 只從記憶體讀取指令,極少覆寫。

6.2.3 區域性判斷準則總結 (p.644)

定性評估程式區域性的簡單規則:

1. 重複引用相同變數的程式有好的 temporal locality。
2. stride-k 引用模式中,stride 越小 spatial locality 越好;stride-1 最佳;在記憶體中大步跳躍的程式 spatial locality 差。
3. 就指令擷取而言,迴圈天生有好的 temporal 與 spatial locality;迴圈本體越小、迭代次數越多,區域性越好。

6.3 記憶體階層 (The Memory Hierarchy) (p.645-646)

兩個基本且持久的事實恰好互補,催生了所有現代系統採用的記憶體階層 (memory hierarchy):

• 儲存技術:不同技術存取時間差異巨大;越快的每 byte 越貴、容量越小;CPU 與 main memory 的速度差距持續擴大。
• 軟體:寫得好的程式展現良好區域性。

                 ^  L0:  Registers            CPU 單一 clock cycle 存取
  Smaller,       |  L1:  L1 cache (SRAM)      數個 cycle;存放來自 L2 的 cache line
  faster,        |  L2:  L2 cache (SRAM)      存放來自 L3 的 cache line
  costlier/byte  |  L3:  L3 cache (SRAM)      存放來自 main memory 的 cache line
                 |  L4:  Main memory (DRAM)   數十~數百 cycle;快取本地磁碟的 disk block
  Larger,        |  L5:  Local disks          存放來自遠端伺服器的檔案
  slower,        |  L6:  Remote storage       分散式檔案系統 (AFS/NFS)、Web servers
  cheaper/byte   v

• 由高層到低層:裝置更慢、更便宜、更大。
• L6 例子:AFS(Andrew File System)、NFS(Network File System)等分散式檔案系統讓程式存取遠端伺服器上的檔案;WWW 讓程式存取世界任何角落 Web server 上的檔案。

6.3.1 記憶體階層中的快取 (Caching) (p.646-648)

Cache(讀作 "cash")是小而快的儲存裝置,作為較大、較慢裝置中資料物件的暫存區 (staging area);使用 cache 的過程稱為 caching。

中心思想:對每個 k,第 k 層較快較小的裝置,作為第 k+1 層較大較慢裝置的 cache——每一層都快取下一層的資料物件。例:local disk 快取遠端磁碟的檔案(如 Web pages)、main memory 快取 local disk 的資料……直到最小的 cache——CPU registers。

Level k:      +----+----+----+----+   較小、較快、較貴的裝置,
   (cache)    |  4 |  9 | 14 |  3 |   快取 level k+1 的「部分」block
              +----+----+----+----+
                     ^    |
        以 block 為單位雙向傳輸 (block-size transfer units)
                     |    v
              +----+----+----+----+
Level k+1:    |  0 |  1 |  2 |  3 |   較大、較慢、較便宜的裝置,
              +----+----+----+----+   被劃分成 block(此例 16 個
              |  4 |  5 |  6 |  7 |   固定大小 block,編號 0..15)
              +----+----+----+----+
              |  8 |  9 | 10 | 11 |
              +----+----+----+----+
              | 12 | 13 | 14 | 15 |
              +----+----+----+----+

• 第 k+1 層儲存被劃分成連續的資料物件塊 block,每個 block 有唯一位址或名稱;通常固定大小(例外:Web server 上的遠端 HTML 檔為可變大小)。
• 第 k 層劃分成與第 k+1 層同大小、但數量較少的 block;任一時刻只保存 k+1 層 block 的子集。
• 相鄰兩層之間 block 大小固定,但不同「層對」可用不同大小:L1↔L0 常用 word-size block;L2↔L1、L3↔L2、L4↔L3 常用數十 bytes;L5↔L4 用數百至數千 bytes。越低層(離 CPU 越遠)存取時間越長,傾向用更大的 block 來攤銷 (amortize) 存取時間。

Cache hit(p.648):程式需要第 k+1 層的資料物件 d 時,先在第 k 層目前存放的 block 中找;若 d 已被快取,即為 cache hit,直接從較快的第 k 層讀取。

Cache miss(p.648):若 d 不在第 k 層,即為 cache miss。第 k 層從第 k+1 層取回含 d 的 block,若 cache 已滿則需覆寫既有 block:

• 覆寫動作稱為 replacing / evicting;被逐出的 block 稱為 victim block。
• 由 replacement policy 決定逐誰:random 策略隨機挑選;LRU (least recently used) 策略挑「最久未被存取」(last accessed the furthest in the past) 的 block。
• 取回後程式即可從第 k 層讀 d;block 會留在第 k 層,以期之後的存取命中。

程式請求資料 d
      |
      v
 d 在 level k? ----是----> Cache HIT:直接從 level k 讀 d(快)
      |
      否
      v
 Cache MISS:向 level k+1 取回含 d 的 block
      |
      v
 level k 已滿? --是--> 依 replacement policy 選 victim block 並 evict
      |                          |
      否                         v
      +------------------> 依 placement policy 放入 block
                                 |
                                 v
                    程式從 level k 讀 d;block 留下等待後續 hit

Miss 的種類(p.648-649):

• Placement policy:miss 後決定取回的 block 放哪裡。最彈性的做法是「k+1 層任何 block 可放 k 層任何位置」,但對階層高處(靠近 CPU)、以硬體實作且講求速度的 cache 而言,隨機放置的 block 定位成本太高;故硬體 cache 通常限制第 k+1 層的特定 block 只能放入第 k 層的一小組(甚至單一,singleton)位置。例:block i 必須放在第 k 層的 block (i mod 4)——block 0, 4, 8, 12 映到 block 0;block 1, 5, 9, 13 映到 block 1,依此類推。
• Conflict miss 範例:在 (i mod 4) 政策下,程式交替請求 block 0、8、0、8……兩者都映到 block 0,每次都 miss,儘管 cache 總共能容納 4 個 block。
• Working set:程式常以一連串 phase(如迴圈)執行,每個 phase 存取一組相對固定的 cache block(如巢狀迴圈反覆存取同一個陣列),這組 block 即該 phase 的 working set。

Cache 管理(p.649-650):每一層都要有某種邏輯管理 cache——切割 block、在層間搬移、判斷 hit/miss 並處理;管理者可以是硬體、軟體或兩者組合:

多數情況下 cache 自動運作,程式不需做任何明確或特定的動作。

6.3.2 記憶體階層概念總結 (p.650)

基於快取的記憶體階層之所以有效,因為慢的儲存比快的便宜,且程式傾向展現區域性:

• 利用 temporal locality:同一物件可能被重複使用;物件第一次 miss 被複製進 cache 後,可期待後續多次 hit,由較快的 cache 服務,遠快於原始的 miss。
• 利用 spatial locality:block 通常含多個資料物件;一次 miss 複製整個 block 的成本,可被後續對 block 內其他物件的引用攤銷。

Figure 6.23:快取在現代系統中無所不在(由快至慢):

Exam/Test Patterns

Related Notes

• 06-Memory-Hierarchy/01-Storage-Technologies
• 06-Memory-Hierarchy/03-Cache-Memories
• 06-Memory-Hierarchy/04-Cache-Friendly-Code-and-Memory-Mountain
• 09-Virtual-Memory/01-Address-Spaces-and-VM-Caching
• 05-Program-Optimization/04-Limiting-Factors-and-Memory-Performance
• 03-Machine-Level-Programs/05-Arrays-and-Data-Structures