矩陣乘法是科學(xué)計(jì)算的核心，但 naive 實(shí)現(xiàn)性能慘不忍睹。問(wèn)題出在緩存——三個(gè)大矩陣來(lái)回折騰，L1緩存根本裝不下。緩存分塊（Cache Blocking/Tiling）通過(guò)把大矩陣切成小塊，讓數(shù)據(jù)在緩存里多待一會(huì)兒，性能能提升幾倍。

1. 問(wèn)題：傳統(tǒng)矩陣乘法的緩存噩夢(mèng)

標(biāo)準(zhǔn)的三層循環(huán)矩陣乘法：

for (i = 0; i < N; i++)
  for (j = 0; j < N; j++) {
    r = 0;
    for (k = 0; k < N; k++)
      r += y[i][k] * z[k][j];  // z按列訪問(wèn)
    x[i][j] = r;
  }

問(wèn)題在哪？

空間局部性差：z[k][j]按列訪問(wèn)，但C數(shù)組是行主序。z[0][j]和z[1][j]在內(nèi)存中相隔N個(gè)元素，大概率不在同一緩存行。

時(shí)間局部性差：計(jì)算x[i][j]需要y的第i行和z的第j列。下一個(gè)元素x[i][j+1]又要重新加載y的第i行——雖然剛剛用過(guò)，但可能被踢出緩存了。

總訪問(wèn)量：假設(shè)三個(gè)N×N矩陣，計(jì)算量是2N3次操作，但內(nèi)存訪問(wèn)量也是O(N3)級(jí)別。如果N=1000，緩存裝不下，每次都要從內(nèi)存讀，性能暴跌。

2. 分塊優(yōu)化：把大矩陣切成小塊

核心思想：把矩陣分成B×B的小塊，確保三個(gè)塊能同時(shí)駐留緩存。

for (jj = 0; jj < N; jj += B)       // 分塊列循環(huán)
  for (kk = 0; kk < N; kk += B)     // 分塊行循環(huán)
    for (i = 0; i < N; i++)
      for (j = jj; j < min(jj+B, N); j++) {
        r = 0;
        for (k = kk; k < min(kk+B, N); k++)
          r += y[i][k] * z[k][j];   // 塊內(nèi)訪問(wèn)
        x[i][j] += r;
      }

關(guān)鍵變化：

• 最內(nèi)層循環(huán)只在B×B的塊內(nèi)操作
• 如果3B2 ≤ 緩存容量，三個(gè)塊都能駐留
• 塊內(nèi)數(shù)據(jù)復(fù)用，減少內(nèi)存訪問(wèn)

3. 分塊因子的選擇

分塊因子B不是越大越好，要匹配緩存容量。

3.1 理論計(jì)算

假設(shè)L1緩存32KB，float類(lèi)型（4字節(jié)）：

所以B≈52，取整64（方便SIMD對(duì)齊）。

3.2 實(shí)際考慮

Intel Advisor的實(shí)測(cè)建議^[1]：對(duì)于矩陣乘法，B=64是甜點(diǎn)區(qū)。

4. 分塊的局限

小塊開(kāi)銷(xiāo)：當(dāng)N很大但B固定時(shí)，分塊引入的循環(huán)開(kāi)銷(xiāo)可以忽略。但如果N本身很?。ㄈ鏝<100），分塊反而增加開(kāi)銷(xiāo)。

不規(guī)則矩陣：非方陣或稀疏矩陣，分塊效果打折扣。

5. 現(xiàn)代編譯器的自動(dòng)分塊

5.1 Intel ICC/ICX

#pragma omp parallel for
for (int i = 0; i < N; i++)
  #pragma unroll
  for (int j = 0; j < N; j++)
    // 編譯器自動(dòng)分塊

5.2 LLVM-Polly^[2]

Polly是LLVM的多面體優(yōu)化框架，能自動(dòng)進(jìn)行循環(huán)分塊：

clang -O3 -mllvm -polly -mllvm -polly-tile ./matmul.c

Polly的tile size選擇算法考慮：

• 緩存大小
• 緩存行大小
• 循環(huán)迭代次數(shù)

5.3 自動(dòng)調(diào)優(yōu)（Auto-tuning）

ATLAS和OpenBLAS采用empirical tuning：

1. 編譯多個(gè)版本的kernel，不同B值
2. 在目標(biāo)機(jī)器上實(shí)測(cè)
3. 選擇最快的版本

這比理論計(jì)算更準(zhǔn)確，因?yàn)榭紤]了：

• 緩存替換策略
• TLB行為
• 預(yù)取器影響

6. 總結(jié)

緩存分塊是矩陣運(yùn)算優(yōu)化的核心技術(shù)：

關(guān)鍵認(rèn)知：

1. 分塊因子B要匹配緩存容量：
2. 實(shí)際B值通常取64或128（考慮SIMD對(duì)齊）
3. 多層分塊（L1/L2/L3）能進(jìn)一步提升性能
4. 現(xiàn)代編譯器能自動(dòng)分塊，但手工調(diào)優(yōu)仍有價(jià)值

理解分塊，就能理解為什么OpenBLAS/GotoBLAS比naive實(shí)現(xiàn)快10倍以上。

參考

1. Intel Advisor Cookbook. Optimize Memory Access Patterns using Loop Interchange and Cache Blocking. 1.68x speedup with cache blocking. ?

2. LLVM Dev Meeting. Cache-aware Scheduling and Performance Modeling with LLVM-Polly. Tile size selection algorithm. ?