快取友善程式碼與記憶體山 (Cache-Friendly Code & the Memory Mountain)

Overview Table

快取參數對效能的影響(6.4 收尾,p.669)

快取設計是多維權衡:總容量 $C=S\times E\times B$(組數 × 每組行數 × 區塊大小)固定時,調整任一參數都有代價。

• 實例:Core i7 的 block 為 64 bytes;L1、L2 為 8-way,L3 為 16-way(miss penalty 越高的下層用越高 associativity)。
• 傳統上追求時脈的高效能系統在 L1 用較低 associativity(miss penalty 只有幾個 cycle),下層用較高者。

6.5 撰寫快取友善程式碼 (Writing Cache-Friendly Code, p.669–675)

局部性好的程式 miss rate 低,miss rate 低的程式跑得快。快取友善 (cache friendly) = 具有良好局部性的程式碼。基本方法只有兩條:

1. 讓 common case 快:程式大部分時間花在少數核心函式的少數迴圈 → 只需專注核心函式的內層迴圈,忽略其他。
2. 最小化每個內層迴圈的 cache miss 數:在 load/store 總數等其他條件相同下,miss rate 較低的迴圈較快。

stride-k 存取的 miss 公式

若 block 大小為 B bytes,stride-k(以 word 為單位)的參照模式,每次迴圈迭代平均產生

• k = 1 時最小 → stride-1 是空間局部性的黃金模式。
• 例:word 4 bytes、block 4 words(B=16)、cold cache,掃描 v[0..7] 的 hit/miss 模式為 m h h h m h h h → 每 4 次存取 1 miss(miss rate 1/4),cold cache 下已是最佳。

兩個關鍵教訓(以 sumvec 為例)

• 對區域變數的重複參照是好的:編譯器會把 i、sum 放進 register file(階層最頂層)→ 時間局部性。
• stride-1 參照模式是好的:所有層級的快取都以連續 block 存放資料 → 空間局部性。

二維陣列:迴圈順序決定生死

C 以 row-major(列優先) 存放陣列。sumarrayrows 內層迴圈沿列掃描(stride-1);sumarraycols 交換迴圈後變成沿行掃描(stride-N)。

row-major 記憶體佈局:  a[0][0] a[0][1] a[0][2] a[0][3] | a[1][0] a[1][1] ...

sumarrayrows(i 外 j 內)存取順序 →→→→ 沿記憶體連續前進(stride-1)
  hit/miss:  m h h h m h h h        miss rate = 1/4

sumarraycols(j 外 i 內)存取順序 ↓↓↓↓ 每步跳 N 個元素(stride-N)
  hit/miss:  m m m m m m m m        陣列大於快取時 → 每次都 miss!

• 實測:大陣列時 sumarrayrows 比 sumarraycols 快 25 倍(p.672)。

6.6 快取對程式效能的整體影響 (p.675–683)

6.6.1 The Memory Mountain(記憶體山, p.675–679)

Read throughput(read bandwidth):程式讀取 n bytes 花 s 秒,則吞吐量為

量測程式 mountain.c(Figure 6.40):

• test(elems, stride):以 stride 掃描陣列前 elems 個元素,用 4×4 loop unrolling(4 個累加器 acc0..acc3)增加內層迴圈的平行度(參見 05-Program-Optimization/03-Loop-Unrolling-and-Parallelism)。
• run(size, stride, Mhz):先呼叫一次 test 暖快取 (warm up the cache),再用 fcyc2 估計 cycle 數,換算 MB/s = (size/stride) / (cycles/Mhz)。注意 size 單位是 bytes、elems 單位是元素個數。
• size ↓ → 工作集小 → 時間局部性好;stride ↓ → 空間局部性好。對不同 (size, stride) 重複量測即得二維函數 = memory mountain。每台電腦都有一座獨一無二的記憶體山,刻畫其記憶體系統的能力。

Read throughput (MB/s)          Core i7 Haswell 2.1 GHz
      ^                          32KB L1d / 256KB L2 / 8MB L3 / 64B block
14000 |  ____
      | /L1  \____                <- ridges of temporal locality(垂直 size 軸)
      ||ridge \ L2 \____             工作集分別塞進 L1 / L2 / L3 / Mem
      ||       \ridge\  L3\____
      ||        \     \ridge\ Mem ridge
  900 ||_________\_____\_____\______
      +--------------------------------> size: 16K ........ 128M
     每條 ridge 沿 stride 方向下坡 = slopes of spatial locality(stride 越大越低)
     stride=1 有一條平坦高稜線(~12 GB/s)= 硬體 prefetch 的功勞

山的地理結構(Core i7 Haswell,size 16 KB–128 MB、stride 1–12 元素、元素為 8-byte long):

• Ridges of temporal locality(垂直 size 軸的四條稜):工作集完全落在 L1 / L2 / L3 / main memory 的區域。L1 稜峰 >14 GB/s vs. 主記憶體稜谷 900 MB/s,相差超過一個數量級。
• Slopes of spatial locality(沿 stride 軸的下坡):stride 增大 → 空間局部性下降 → throughput 下滑。即使工作集塞不進任何快取,主記憶體稜上最高點仍比最低點高 8 倍 → 時間局部性差時,空間局部性仍能救援。
• stride-1 平坦稜線(~12 GB/s):即使工作集超過 L1、L2 容量,Core i7 的硬體 prefetching 會自動辨識循序 stride-1 參照模式並在存取前抓取 block。prefetch 演算法對小 stride 最有效 → 又一個偏好 stride-1 循序存取的理由。

兩種切片分析:

6.6.2 重排迴圈以提升空間局部性(矩陣乘法, p.679–683)

$C=AB$(n×n, double)的三重迴圈依 i, j, k 排列共 6 種版本,計算結果相同(假設加法可結合)、總運算量都是 $O(n^3)$、加法乘法次數相同、A 和 B 的每個元素都被讀 n 次——但內層迴圈的存取次數與局部性天差地遠。

分析假設:sizeof(double) = 8、單一快取 B = 32(一個 block 裝 4 個 double)、n 大到一列塞不進 L1、區域變數放暫存器(不產生 load/store)。

6 版本依內層迴圈實際觸碰的兩個矩陣分成三等價類(Figure 6.45):

class AB (ijk):  sum += A[i][k]*B[k][j]      class BC (kij):  C[i][j] += r*B[k][j]
   A: ─k→ 沿列 stride-1 (0.25 miss)             r = A[i][k] 放暫存器 (0 miss)
   B: ↓k  沿行 stride-n (每次 miss)              B: ─j→ stride-1 (0.25)
                                                 C: ─j→ stride-1 (0.25)  ← 最佳
class AC (jki):  C[i][j] += A[i][k]*r
   A: ↓i 沿行 stride-n (1.0)    C: ↓i 沿行 stride-n (1.0)   ← 最糟

Core i7 實測(Figure 6.46, cycles per inner-loop iteration vs. n)四個要點:

• 大 n 時最快版本比最慢版本快近 40 倍,儘管浮點運算次數完全相同。
• memory reference 數與 miss 數相同的版本對,實測效能幾乎一致(等價類成立)。
• 記憶體行為最差的兩個版本(AC 類)明顯慢於其他四個。
• miss rate 比總記憶體存取次數更能預測效能:class BC(0.5 miss/iter,2 load + 1 store)大勝 class AB(1.25 miss/iter,只有 2 load)。
• 大 n 時最快的 kij / ikj 效能保持恆定——即使陣列遠大於任何 SRAM 快取,prefetching 硬體認得 stride-1 模式且跟得上內層迴圈的存取速度 → 更加鼓勵寫出好空間局部性的程式。

6.6.3 在程式中利用局部性(p.683)

記憶體階層使程式存取記憶體的有效速率不是單一數字,而是隨程式局部性劇烈變動的函數(即記憶體山),差距可達數個數量級。不論底層記憶體系統的具體組織為何,建議三招:

1. 專注內層迴圈——大部分計算與記憶體存取都發生在那裡。
2. 最大化空間局部性——按資料在記憶體中的存放順序、以 stride-1 循序讀取。
3. 最大化時間局部性——資料物件一旦從記憶體讀入,就盡量多次使用。

6.7 本章總結 (Summary, p.684)

• 基本儲存技術:RAM(SRAM 快而貴 → 快取;DRAM 慢而廉 → 主記憶體與 graphics frame buffer)、ROM(斷電保留資料 → 存 firmware)、旋轉磁碟(機械式非揮發、容量大、每 bit 便宜,但存取時間遠大於 DRAM)、SSD(以非揮發 flash 為基礎,逐漸取代旋轉磁碟)。詳見 06-Memory-Hierarchy/01-Storage-Technologies。
• 通則:越快的技術每 bit 越貴、容量越小;各技術的價格/效能以極不同的速率演進,DRAM 與磁碟存取時間跟 CPU cycle 的差距持續擴大。
• 系統以記憶體階層弭平差距:上小快、下大慢。因為寫得好的程式有局部性,大多數資料由高層供應 → 整體效果是「以高層的速度運作、以低層的成本與容量儲存」。
• 程式設計師寫出好的空間與時間局部性即可大幅縮短執行時間;利用 SRAM 快取尤其關鍵——主要從快取取資料的程式遠快於主要從記憶體取資料者。

Exam/Test Patterns

Related Notes

• 06-Memory-Hierarchy/02-Locality-and-Memory-Hierarchy
• 06-Memory-Hierarchy/03-Cache-Memories
• 06-Memory-Hierarchy/01-Storage-Technologies
• 06-Memory-Hierarchy/Practice-Memory-Hierarchy
• 05-Program-Optimization/03-Loop-Unrolling-and-Parallelism
• 05-Program-Optimization/04-Limiting-Factors-and-Memory-Performance
• 02-Information-Representation/04-Floating-Point