深度解析 CPU 高速緩存架構：原理、映射機制、偽共享與程序優化指南

為什麼需要 Cache？

CPU 主頻 (GHz) 與內存延遲 (ns) 差距巨大。以 i5-2400S (2.5GHz) 為例：

• 時鐘週期：0.4ns
• L1 Cache 命中：1-2 週期 (~0.8ns)
• L2 Cache 命中：5-10 週期 (~4ns)
• 內存訪問：25-100 週期 (~40ns) → CPU 等待數百條指令槽

Cache 利用局部性原理 (時間/空間) 縮小速度鴻溝。

Cache 邏輯結構與地址映射

地址劃分三段：Tag | Set Index | Block Offset

31                    s+b-1  s+b-1        b-1  b-1       0
+----------------------+------------+-----------+
|        Tag (t)       | Set Index (s) | Offset (b) |
+----------------------+------------+-----------+

• Block Offset (b bits)：Cache 行內字節偏移，行大小 B = 2^b (典型 64B)
• Set Index (s bits)：選擇組，組數 S = 2^s
• Tag (t bits)：標識內存塊唯一身份，驗證命中

組織形式

總容量 C = S × E × B

多級 Cache 體系 (i5-2400S 實例)

Cache Miss 三類與代價

1. Compulsory (冷啟動)：首次訪問，必然 miss。預取可緩解。
2. Capacity (容量)：工作集超過 Cache 容量。優化數據結構、分塊算法。
3. Conflict (衝突)：多地址映射同一組，關聯度不足。填充對齊、調整訪問步長。

偽共享：多核性能殺手

現象

兩線程分別寫入不同變量，但兩變量落在同一 Cache 行 (64B)。導致 Cache 一致性協議 (MESI) 在核心間頻繁傳輸該行，性能暴跌。

示例

// 線程 0 頻繁寫入
struct { long a; } data0;
// 線程 1 頻繁寫入
struct { long b; } data1;
// 若 data0 與 data1 相鄰分配，極大概率共享一行

解決方案

1. 填充對齊：struct { long a; char pad[64 - sizeof(long)]; } 強制佔滿一行
2. 線程局部存儲：各線程私有副本，最後歸約
3. C11 alignas(64)：alignas(64) long counter;

Cache 友好編程實戰模式

1. 空間局部性：順序訪問、結構體熱點字段聚合

// 差：跳躍訪問
for (int i = 0; i < N; i += 16) sum += a[i];

// 好：順序掃描
for (int i = 0; i < N; i++) sum += a[i];

// 結構體：熱點字段放前面，同一行
struct Particle { float x,y,z; float vx,vy,vz; int life; }; // 48B < 64B

2. 時間局部性：循環融合、分塊

// 分塊矩陣乘法：子塊適應 L1/L2
for (int ii = 0; ii < N; ii += BLOCK)
  for (int jj = 0; jj < N; jj += BLOCK)
    for (int kk = 0; kk < N; kk += BLOCK)
      for (int i = ii; i < ii+BLOCK; i++)
        for (int j = jj; j < jj+BLOCK; j++)
          for (int k = kk; k < kk+BLOCK; k++)
            C[i][j] += A[i][k] * B[k][j];

3. 避免衝突 Miss：數組對齊、步長非 2 的冪

// 差：步長 4096 (2^12) 直接映射同一組
for (i) a[i * 4096] = 0;

// 好：填充改變步長
#define STRIDE 4097
for (i) a[i * STRIDE] = 0;

4. 預取提示

__builtin_prefetch(&a[i+16], 0, 1); // GCC/Clang 內建，提前載入

工具與分析

• perf stat -e cache-references,cache-misses ./prog：硬件計數器統計
• valgrind --tool=cachegrind：模擬 Cache 行為
• likwid-perfctr：詳細核心級事件

總結

理解 Cache 多級結構、映射機制、一致性協議、Miss 類型，是高性能編程的基石。核心原則：

1. 數據結構緊湊、熱點聚合 (空間局部性)
2. 訪問模式順序、可預測 (時間局部性 + 預取友好)
3. 多線程變量隔離 Cache 行 (消除偽共享)
4. 分塊算法適應 Cache 容量 (減少 Capacity Miss)

Cache 不可見，但決定程序上限。善用 perf、cachegrind 量化分析，針對性優化。