跳到主要内容

并行性和局部性优化

并行性和局部性优化​

现代 CPU 早已不再是"单核直线跑代码"的模型。一颗普通桌面芯片就有 8 到 16 个核,每个核内部还有 SIMD 向量单元、乱序执行、多级 cache。如果编译器只按源代码顺序老老实实生成指令,多核和 cache 就全都闲着。并行性和局部性优化的目标,就是通过合法的循环变换,让程序既能同时用多个核,又能让访存尽量命中 cache。

通俗理解:写代码像写菜谱,编译器是把菜谱翻译给厨房的经理。原始菜谱是一个人按步骤做菜;经理发现厨房有 8 个厨师,还有一个大冰箱和一个小操作台,就会想办法把工序拆成能并行的部分,让每个厨师只从操作台上够得着的地方拿食材(cache),少跑冰箱(内存)。

这类优化的收益是几何级的。同样一个矩阵乘法,朴素三重循环和加了循环分块 + SIMD + 多线程之后的版本,性能能差几十倍甚至上百倍,而源代码只是"看起来做同一件事"。

数据依赖是一切变换的前提​

编译器不能随便调整循环顺序,前提是变换后的程序行为要和原来一致。判断哪些操作可以换序、可以并行,靠的是数据依赖分析。

依赖分为两大类:

  • 循环携带依赖(loop-carried):一次迭代产生的值被后面某次迭代读到。
  • 循环内依赖(loop-independent):同一次迭代内部的读写关系。
// 有循环携带真依赖:a[i+1] 需要上一次算好的 a[i]
for (int i = 0; i < N - 1; i++)
a[i + 1] = a[i] + b[i];

// 各次迭代完全独立:可以任意并行
for (int i = 0; i < N; i++)
a[i] = b[i] + c[i];

第一个循环无法直接并行,因为迭代之间是链式串行的;第二个循环可以让每个核算一段,也可以直接向量化。所以后续所有优化都要先过依赖分析这道关。

迭代空间与仿射变换​

多层循环嵌套可以看作一个 n 维整数点阵。比如 for (i=0;i<N;i++) for (j=0;j<N;j++) 就是二维平面上的 N×N 个点,每个点 (i, j) 代表一次迭代实例。

编译器把这些点视为向量,用矩阵乘法来"重新遍历"这个空间:

[i']   [1 0] [i]        # 交换 i、j 的顺序
[j'] = [0 1] [j]

只要变换矩阵是幺模的(unimodular),且不破坏数据依赖方向,就能得到合法的等价循环。循环交换、倾斜、反转本质上都是仿射变换。

常见的循环变换​

  • 循环交换(interchange):调换嵌套顺序,使内层循环访问数组的方式与内存布局对齐。
  • 循环合并(fusion):把两个访问同一数组的循环合成一个,提高时间局部性。
  • 循环分裂(distribution):把一个循环拆成两个,把有依赖的部分和无依赖的部分分开,暴露并行。
  • 循环分块(tiling / blocking):把大循环切成小块,让每一块的工作集能塞进 cache。

矩阵乘法是最经典的例子。朴素版本:

for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
for (int k = 0; k < N; k++)
C[i][j] += A[i][k] * B[k][j];

当 N 稍大时,B[k][j] 在 k 循环里跳着访问,cache 频繁失效。tiling 后:

for (int ii = 0; ii < N; ii += T)
for (int jj = 0; jj < N; jj += T)
for (int kk = 0; kk < N; kk += T)
for (int i = ii; i < ii + T; i++)
for (int j = jj; j < jj + T; j++)
for (int k = kk; k < kk + T; k++)
C[i][j] += A[i][k] * B[k][j];

选择合适的 T(一般是几十),一个 T×T 的子块就能整块留在 L1 里反复复用,实测速度往往能提升 3 到 8 倍。

cache 局部性​

cache 关心两种局部性:

  • 空间局部性:刚访问的地址附近的地址很快也会被访问。cache line 一次会拉一整段(一般 64 字节)。
  • 时间局部性:同一个地址在短时间内被反复访问,值还留在 cache 里。

C 语言二维数组是行主序,A[i][j] 和 A[i][j+1] 在内存里相邻。看这两个写法:

// 好:内层循环沿行走,命中 cache line
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) sum += A[i][j];

// 坏:内层循环跨行跳,几乎每次都 cache miss
for (int j = 0; j < N; j++)
for (int i = 0; i < N; i++) sum += A[i][j];

同样一段代码,把 i、j 换个位置,运行时间可能差 5 到 10 倍。Fortran 用列主序则正好相反,所以移植代码时循环顺序常常要跟着翻转。

SIMD 向量化​

现代 CPU 都有 SIMD 单元——x86 上的 SSE / AVX / AVX-512,ARM 上的 NEON、SVE。它们能用一条指令同时处理 4、8、16 个数据。编译器识别到独立的循环体后,会自动把标量指令替换成向量指令:

for (int i = 0; i < N; i++)
c[i] = a[i] + b[i];

在 AVX2 下会被展开为每次处理 8 个 float 的向量加法,等价于:

for (int i = 0; i < N; i += 8)
_mm256_store_ps(&c[i],
_mm256_add_ps(_mm256_load_ps(&a[i]),
_mm256_load_ps(&b[i])));

自动向量化要求循环体无依赖、数组指针不重叠、访问对齐或可以对齐。任何一条不满足,编译器就会保守地放弃。

循环并行化​

判断一个循环能不能并行,核心还是回到依赖分析:只要没有循环携带的真依赖(或者能通过手段消除),就可以拆到多个线程上。

两个常用的"消除依赖"手段:

  • 变量私有化(privatization):循环内部的临时变量各线程各自一份,不共享。
  • 归约(reduction):像 sum += a[i] 这种,每个线程先算局部和,最后再合并总和。

用 OpenMP 表达非常直接:

#pragma omp parallel for reduction(+:sum)
for (int i = 0; i < N; i++)
sum += a[i];

编译器看到 reduction(+:sum),就知道给每个线程分一个私有 sum,循环结束时用原子加合并回主变量。

编译器与手写的边界​

不是所有优化编译器都能自己做。它能自动搞定的通常是:结构简单的循环、编译期能证明无别名的数组、访问模式规则的场景。GCC/Clang 的 -O3 -march=native 加上恰当的 restrict 修饰,很多小循环就自动向量化了。

但一旦出现以下情况,编译器多半只能保守放弃,需要开发者出手:

  • 指针别名不明——加 restrict 或改成数组访问。
  • 依赖太复杂,静态分析看不穿——用 #pragma omp simd、#pragma ivdep 明确告诉它可以向量化。
  • 需要特定的 tile 大小或数据布局——手动 tiling,或用像 Halide、TVM 这样的 DSL 把算法和调度分开写。
  • 对极致性能有要求——直接写 intrinsic 或汇编,比如 BLAS 内核。

所以并行性和局部性优化本质上是编译器和程序员的合作:编译器负责把无争议的变换做扎实,程序员负责在关键路径上用注解和重写把编译器无法证明的假设明确出来。理解这些变换的原理,就能知道自己的代码"值不值得"被编译器优化,以及在必要时该怎么帮它一把。