📚 课程目录第4章内存层次与数据局部性优化

4. 内存层次与数据局部性优化

在科学计算中，处理器算得再快，也常常被“等数据”拖住。现代计算机的内存并不是一块均匀、等速的存储，而是一个由寄存器、L1/L2/L3 缓存、主存和 NUMA 远端内存构成的多层体系。越靠近 CPU 的层次容量越小、延迟越低；越远的层次容量越大、带宽与延迟越差。理解这一层次结构，并让程序尽量在靠近 CPU 的层次里完成重复访问，就是数据局部性优化的核心。

缓存行：局部性的最小搬运单位

CPU 与主存之间不是按单个变量搬运数据，而是以缓存行（cache line，常见为 64 字节）为单位。一次缺失会把整行载入缓存，因此“访问一个元素”实际上可能带来一整行的数据。这带来两个直接后果：一是空间局部性好的访问（连续地址）能充分利用已载入的缓存行；二是当多个线程写同一缓存行中的不同变量时，会发生伪共享（false sharing），缓存行在核心间反复失效，性能急剧下降。

以双精度浮点（8 字节）为例，一行 64 字节可容纳 8 个元素。若按行优先遍历二维数组，内层循环沿列方向连续访问，命中率高；若按列优先遍历，则每次跨越一整行，几乎每次都是缺失。伪共享的典型修复是填充（padding）或对齐，使每个线程独占的计数器落在不同缓存行上。

预取、TLB 与 NUMA

预取（prefetch）利用硬件自动识别或软件显式指令（如 __builtin_prefetch）提前把即将用到的数据搬入缓存，掩盖访存延迟。硬件预取对连续、规则的访问模式有效，但对不规则稀疏访问往往无能为力，此时软件预取或改变数据布局更有效。

TLB（转译后备缓冲）缓存虚拟地址到物理地址的映射。大数组跨越大量页面时，TLB 项会被频繁换出，产生 TLB 缺失。使用大页（huge page）可显著减少页表项数量，降低 TLB 压力，对动辄数 GB 的科学计算数组尤为重要。

NUMA（非统一内存访问）意味着多路服务器上，每个 CPU 访问本地内存快、访问远端内存慢。若线程被调度到与数据所在节点不同的 CPU 上，就会出现远端访问。实践中应做到“数据就近分配、线程就近绑定”，例如使用 numactl --cpunodebind=0 --membind=0 让计算与内存落在同一节点。

分块：让重复访问留在缓存里

矩阵乘法 C = A×B 是局部性优化的经典对象。朴素三重循环对 C 的每个元素都要遍历 A 的一整行和 B 的一整列，A、B 元素被反复从主存读取，缓存利用率极低。分块（blocking）的思路是：把矩阵切成 Bs×Bs 的小块，让一个 A 块、一个 B 块和对应的 C 块能同时驻留在 L1/L2 中，块内的乘加在缓存里完成，从而把主存访问量降低一个数量级。

下面给出一个可运行的分块实现示例（行优先存储，C 初始化为 0）：

#define BS 64   // 分块尺寸，需结合 L1/L2 容量调优
void matmul_blocked(int n, const double *A, const double *B, double *C) {
    for (int ii = 0; ii < n; ii += BS)
      for (int jj = 0; jj < n; jj += BS)
        for (int kk = 0; kk < n; kk += BS)
          for (int i = ii; i < ii + BS && i < n; ++i)
            for (int k = kk; k < kk + BS && k < n; ++k) {
              double a = A[i*n + k];
              for (int j = jj; j < jj + BS && j < n; ++j)
                C[i*n + j] += a * B[k*n + j];
            }
}

这里最内层对 j 的循环沿行连续访问 B 和 C，空间局部性好；a 被提到循环外，减少重复加载。分块尺寸 BS 的选择取决于缓存容量：若 L1 为 32 KB，一个 64×64 的双精度块约 32 KB，A 块与 B 块合计已超出 L1，因此实际中常取 BS=32 或让 A、B 块适配 L2。这需要在目标机器上实测调优，而不是照搬常数。

循环重排与数据布局变换

循环重排（loop reordering）通过交换循环次序改善访问模式。例如把 i-k-j 顺序改为 i-j-k，可让最内层沿连续维度访问，提升空间局部性；但不同顺序对 A、B、C 的复用侧重不同，需结合分块一起考虑。数据布局变换则从存储格式入手：把“数组的结构”（AoS）改为“结构的数组”（SoA），或对稀疏矩阵采用 CSR 等压缩格式，使真正被访问的数据在内存中连续排列，减少无效缓存行载入。

实验：观察分块带来的变化

建议做一个对照实验：取 n=1024 的双精度矩阵，分别运行朴素三重循环与分块版本，记录耗时并计算 GFLOPS（浮点运算次数约为 2n³）。示例中若朴素版耗时 1.2 s、分块版耗时 0.35 s，则对应约 1.8 GFLOPS 与 6.1 GFLOPS——这些数值仅为说明量级的合理假设，实际结果依机器而定。判断优化是否生效，除了看总时间，还应关注：分块尺寸扫描曲线是否出现明显峰值、增大 n 后性能是否仍稳定、以及用 perf stat 观察 cache-misses 与 TLB misses 是否下降。

调优顺序建议：先保证访问连续（循环重排、布局变换），再做分块匹配缓存容量，最后用 NUMA 绑定与大页消除远端访问和 TLB 压力。每一步单独测量，避免多个改动叠加后无法归因。

需要强调的是，局部性优化不是一次性配置，而是“测量—假设—改动—再测量”的循环。缓存行决定搬运粒度，预取掩盖延迟，TLB 与大页影响地址翻译开销，NUMA 决定数据离计算有多远；分块、循环重排与布局变换则是把这四者落到代码上的具体手段。掌握这套对应关系，才能在面对真实科学计算负载时，判断瓶颈究竟在带宽、延迟还是地址翻译，并选择正确的优化方向。