1. 从一段热循环说起依赖分析到底在解决什么问题1.1 一个真实的向量化失败案例先说一个我实际遇到过的场景。前几年调一段数值计算的热循环代码非常简单void scale_add(double *a, double *b, int n) { for (int i 1; i n; i) { a[i] a[i - 1] b[i]; } }用-O3 -marchnative编译打开 GCC 的向量化报告得到的提示大概是 not vectorized: data dependence between iterations。当时第一反应是编译器太保守、太怂后来翻了底层手册才意识到编译器判断得一点没错第 i 次迭代要读a[i-1]而这个位置刚刚被第 i-1 次迭代写过。一条先写后读的链路横跨了相邻两次迭代这就是典型的循环携带依赖loop-carried dependence距离为 1。这条依赖为什么能堵死向量化因为 SIMD 是让多个 lane 同时执行同一指令如果一条向量指令同时处理a[i]、a[i1]、a[i2]、a[i3]那么 lane 2 要读的a[i1]正是 lane 1 这条指令正要写的位置。放在单条指令内部来看这就是一个 RAW 冒险——读操作必须等到写操作完成而 SIMD 硬件根本没有给 lane 之间留这种等待通道。只要依赖距离小于向量宽度这个矛盾就很难绕过去。这类问题在教科书里叫依赖分析dependence analysis分成两大体系数据依赖data dependence和控制依赖control dependence。数据依赖管制的是值的流向控制依赖管制的是会不会执行的决策权。搞懂这两件事再回头读编译器优化报告、写并行程序、甚至看 CPU 的乱序执行行为很多指标和报错都会变得有章可循。这篇文章就把这两套概念完整拆开讲一遍再用前缀和这个经典案例演示如何主动消解依赖最后分享一些我在实际工程里排查依赖问题的工具和心得。1.2 数据依赖与控制依赖两条完全不同的枷锁数据依赖的定义比较直白如果两条语句访问同一个内存位置且其中至少有一条是写操作那么这两条语句之间就存在依赖。比如x a b; y x * 2;第二条要读x第一条刚写了一版x顺序绝对不能颠倒。控制依赖则是另一码事它跟值没有直接关系而是指某条分支指令的结果决定了另一条语句是否会被执行。比如if (cond) { x 1; }x 1这条语句执行不执行完全取决于cond的真假那么它就控制依赖于这条分支。从编译优化的角度说数据依赖告诉我们哪些重排是被禁止的控制依赖告诉我们哪些代码不能跨过分支随意搬迁。两者叠加在一起构成了程序指令级并行的天花板。接下来我先讲数据依赖的四种类型再讲控制依赖的判定机制和应对手段。2. 数据依赖的四张面孔不只是先写后读2.1 流依赖RAW唯一无法通过改名消除的真依赖流依赖也叫真依赖true dependence对应经典的 RAWRead After Write冒险。形式是S1: x a b; S2: y x * 2;S2 要读的x必须来自 S1 刚写入的值这条价值链是程序语义真正需要的东西。无论怎么重排指令、怎么改名S2 都必须在 S1 之后执行。在循环里流依赖分两种同一次迭代内部的比如上面的 S1→S2另一次迭代跨到下一次迭代的比如第一节那个a[i] a[i-1] b[i]。后者才是并行化的最大障碍编译器看到它基本就会放弃向量化除非你能证明依赖距离足够大、或者用算法把它拆掉前缀和那一节会详细展开。2.2 反依赖WAR与输出依赖WAW寄存器重命名的用武之地反依赖对应 WARWrite After Read冒险形式是先读后写S1: x y 1; // 先读 y S2: y z * 2; // 后写 yS2 如果跑到 S1 前面S1 读到的y就不是原来的值了所以顺序必须保持。但仔细想一下这里的顺序要求并不是因为值真的要从 S1 流到 S2仅仅是因为两个语句碰巧用了同一个变量名。既然如此给 S2 换一个新的名字问题就消失了S1: x y 1; S2: y z * 2; // 改名后 S2 只是写了一个互不相干的变量寄存器重命名就是干这个的CPU 硬件在做乱序执行时就是靠每周期重新标记寄存器来消除这种伪依赖。输出依赖对应 WAWWrite After Write冒险形式是两个语句写同一个位置S1: x 1; S2: x 2;最终只关心x的最后一个值所以 S1 和 S2 的顺序要保住。但它同样是命名冲突造成的伪依赖改名或者做死代码消除把 S1 删掉即可解决。在循环里反依赖和输出依赖最典型的场景是两个迭代区间部分重叠的数组访问比如for (i 0; i n - 1; i) { a[i] b[i]; c[i] a[i 1]; // 读 a[i1]可能读到 a[i] 尚未写入的位置 }这类依赖看起来吓人但编译器往往能通过循环分发、数组标量化、或者内部改名来化解真正让编译器头疼的还是流依赖。2.3 输入依赖RAR不构成冲突却影响局部性两条语句都读同一个位置也就是 RARRead After Read严格说不算数据冲突因为两条读操作之间没有任何顺序要求。但编译器分析时仍然会把它们标记为输入依赖因为它对后续优化有价值两个读共用同一个数据可以合并访问、做公共子表达式消除也可以在调度时故意把它们放近一点提高 cache 命中率。循环里典型的输入依赖长这样for (i 0; i n; i) { t1 a[i] 1; t2 a[i] * 2; c[i] t1 t2; }两个语句都读a[i]没有写编译器会放心大胆地把这次读取缓存进寄存器t1和t2都从同一个值算出来。这给我们的启发是分析依赖时不要一看到同一变量出现两次就紧张先分清读写方向读写都是读的话反而是优化机会。2.4 把四种依赖放进同一个循环里看理论说多了容易飘回到一个组合循环for (i 1; i n; i) { S1: a[i] a[i - 1] b[i]; S2: c[i] a[i] d[i - 1]; S3: d[i] c[i - 1] * 2; }这里至少藏了六条关系S1(i) 读a[i-1]依赖 S1(i-1) 对流依赖S2(i) 读a[i]依赖 S1(i) 同迭代流依赖S2(i) 写c[i]S3(i1) 读c[i]距离 1 的流依赖S3(i) 读d[i-1]d在上一轮被 S3(i-1) 写过又是循环携带依赖。至于反依赖、输出依赖只要某个数组在两处被一读一写或两写就可能出现。我建议你自己拿笔在纸上画一遍这几个象限把每个数组访问的下标表达式列出来标注谁读谁写、距离多少。这一步练熟了后面看编译器报错和手写并行代码都会快很多。依赖分析的第一课不是背定义而是建立拿下标表达式算距离的条件反射。3. 控制依赖分支是执行秩序的另一种枷锁3.1 后支配关系控制依赖的形式化定义控制依赖的定义不像数据依赖那么直观。严格的定义要用到支配树dominator tree里的后支配post-dominate概念节点 Y 后支配节点 X指的是从 X 出发的所有执行路径最终都会经过 Y。如果 Y 后支配了某条分支 B 的 taken 出口却没有后支配 not-taken 出口那么 Y 就控制依赖于 B。用大白话讲程序走到分支路口往左走可能执行 Y往右走可能跳过 Y你的去向决定了 Y 的生死这就是控制依赖。举一个最简单的例子if (cond) { S1: x 1; } S2: y x 1;S1 控制依赖于分支condS2 不依赖无论往哪边走都会执行。编译器在做代码移动时绝对不能把 S1 挪到if之前——那样cond为假时也会执行 S1语义就变了。但 S2 可以自由移动前提是它不依赖别的数据因为它不控制依赖于任何分支。3.2 硬件与编译器如何绕过控制依赖控制依赖之所以重要是因为现代 CPU 有一个核心手段叫推测执行speculation分支条件还没算出来硬件就赌一个方向先跑了。赌错了怎么办把已经执行但还没提交的结果全部作废flush 流水线重来。这时候控制依赖并不是被消除了而是被硬件用回滚机制暂时搁置。编译器也有类似的招。最常见的是条件传送指令如 x86 的cmov把if (x y) max x; else max y;变成一条不需要分支、仅靠条件选择值的数据流指令。本质上是把控制依赖转换成了对条件值的数据依赖——执行顺序不再由分支方向决定而是由哪个值被选中决定。转换之后分支预测器和推测执行就不用参与指令流水线更平稳。这里有个很容易踩的坑cmov两边分支都会被计算如果其中一个分支有副作用比如除零、解引用空指针、函数调用就不能随便转换。编译器会非常保守有些看起来能转换的代码它不做就是这个原因。3.3 if-conversion把控制依赖降级为数据依赖比cmov更进一步的是编译器优化里的 if-conversion也叫谓词化predication。它对一大块受分支保护的代码统一处理给每条语句加一个谓词寄存器我把它想象成执行许可证。语句执行前先检查许可证许可证来自分支条件的计算值可能是真也可能是假。这样整块代码没有跳转每条语句按部就班执行只是那些许可证为假的结果不会被提交。GPU 的 SIMT 架构就是硬件版的 if-conversion。一组线程在同一个 warp 里遇到分支时硬件把两条路径都执行一遍用 mask 屏蔽不该生效的 lane。从依赖分析的角度看这个过程把控制依赖变成了对 mask 值的数据依赖。所以你在 CUDA 里看分支经常能观察到虽然分支存在但所有 lane 都跑了同一段指令就是这个原因。理解这一点对性能调优很有用当分支内代码很短、且没有副作用时编译器或硬件基本都能帮你处理控制依赖但分支体很大、要么干这要么干那的时候两边都执行的代价会很大我们需要依赖分析来判断到底要不要改写成分支无关的计算。4. 循环携带依赖并行化绕不开的主战场4.1 循环携带依赖与循环无关依赖绝大多数可并行的性能热点都在循环里所以循环的依赖分析是重中之重。这里要区分两件事循环无关依赖loop-independent dependence发生在同一次迭代内部不跨越迭代边界。循环携带依赖loop-carried dependence某次迭代访问的变量是由另一次迭代写入的读写跨越了迭代边界。循环无关依赖只在单次迭代内部约束顺序对循环整体并行化影响不大因为不同迭代之间互不干扰麻烦的是循环携带依赖它是阻碍循环并行、向量化的头号元凶。判断方法也很机械取出结构相同的两个访问比如a[i]和a[i-k]看它们的下标差k是不是常量。k是常量说明依赖距离固定k不恒定或者表达式非线性编译器就会非常保守地认为可能有依赖。4.2 距离向量与方向向量多层循环嵌套时每个循环维度的依赖距离拼在一起就是距离向量。比如for (i 0; i n; i) { for (j 0; j n; j) { A[i][j] A[i - 1][j 1] 1; } }访问A[i-1][j1]比当前A[i][j]在外层少 1、内层多 1所以距离向量是(1, -1)方向向量是(, -)。这个方向向量一出来很多并行化手段直接被否决外层循环我指望它并行但第 i 轮要读第 i-1 轮的数据不行内层想向量化结果它要往 j1 方向读也不行。方向向量里每一项是、、三种之一代表该维度依赖是从前到后、同一位置、还是从后到前。编译器做循环变换循环交换、倾斜、分块时就是在跟这些向量博弈想办法把方向向量规整成外层都是 或 、最内层可以并行的形态。我见过很多团队喜欢直接套用循环交换技巧但从来不看方向向量结果换了半天反而更慢。先算向量再决定变换才是正路。4.3 GCD 检验证明两个下标永不相等实践里一个非常有用的小工具是最大公约数检验GCD test。如果两个访问的下标是a[2*i]和a[2*i1]直觉上一个是偶数、一个是奇数永远碰不到。GCD 检验把这个直觉形式化了取两个下标表达式系数 2 和 2求gcd(2,2)2再看常量差(2i1) - (2i) 1。如果常数差不能被 gcd 整除就证明两个下标永远不相等可以安全判定无依赖。这里 2 不能整除 1所以确实无依赖。反过来a[2*i]和a[2*i-4]的常量差是 42 能整除 4那就不排除依赖。实际情况也确实存在依赖i 与 i-2 的访问会落到同一个小标上依赖距离为 2。GCD 检验只解决是否可能相等的问题不解决距离问题但它已经能挡掉大量保守误判。很多编译器报告里写着 unknown data dependence 的循环其实就是编译器不推 gcd、或者表达式太复杂推不动。这种情况下你可以自己手推一下确认无依赖后用 restrict 或拆分循环帮编译器一把。4.4 私用化、约简与归约消除循环携带依赖并不都是硬骨头有几类常见形态有固定解法。第一类是私有变量private。循环体内临时声明的标量不需要跨迭代保留值for (i 0; i n; i) { double t a[i] * 2.0; c[i] t b[i]; }t每个迭代自己算自己用根本不跨迭代这种变量声明在循环体内就是告诉编译器我是私有的不会形成循环携带依赖。第二类是约简reductionfor (i 0; i n; i) { sum a[i]; }表面上sum每轮都被读写存在距离为 1 的流依赖。但它满足结合律和交换律可以拆成每个线程先算部分和再合并。OpenMP 里直接写#pragma omp parallel for reduction(:sum)编译器就能自动生成树形合并逻辑。注意浮点加法不满足精确结合律所以并行后的结果可能和串行略有差异GCC 默认不并行浮点约简要开-ffast-math或手动写归约才会放开。这个差异我在做数值模拟时被坑过结果对不上查了半天才发现是浮点顺序变了不是算错。第三类是递归式变换。形如a[i] a[i-1] * k的循环编译器可以通过归纳变量化简成闭式解a[i] a[0] * k^i直接消掉依赖。但不是所有递归都能闭式化一旦出现类似前缀和a[i] a[i-1] b[i]这种无法化简的递归就得考虑换算法。5. 前缀和用算法变换主动消解数据依赖5.1 一个距离为 1 的典型循环携带依赖前缀和prefix sum也叫 scan是这样一类操作给定数组x计算out[i] x[0] x[1] ... x[i]。朴素写法for (i 1; i n; i) { x[i] x[i] x[i - 1]; }这就是第一节那个距离为 1 的循环携带依赖一串严格的串行链。不管你有多少核这个写法都得老老实实挨个算时间复杂度 O(n)关键路径长度也是 O(n)。前缀和的特殊之处在于它的操作是加法满足结合律这给了我们重新组织计算顺序的空间。依赖分析告诉我们顺序被这条链绑死了而算法变换告诉我们链的结构可以换。现在热词里那句前缀和解决数据依赖指的就是通过并行扫描算法把这个 O(n) 深度的串行依赖链改写成一个对数深度的并行依赖图。5.2 Hillis-Steele 扫描用冗余计算换并行度Hillis-Steele 是最容易理解的并行扫描算法思路是每次迭代把相距 d 的元素两两相加d 从 1 开始每次翻倍// 每次迭代结束后x[i] 保存的是以 i 结尾的 2d 个连续元素之和 // 这里用 y 做双缓冲避免同一迭代内读写同一个数组 for (int d 1; d n; d * 2) { for (int i 0; i n; i) in parallel { if (i d) y[i] x[i] x[i - d]; else y[i] x[i]; } swap(x, y); // 交换两个缓冲区的角色 }画一遍之后你会看到第一轮每个元素跟前面 1 个元素相加第二轮跟前面 2 个相加第三轮跟前面 4 个相加。两轮之后x[3]已经包含了x[0..3]的和。这个算法的并行深度只有O(log n)非常漂亮代价是总计算量变成了O(n log n)——每一层所有元素都参与加法做了大量重复计算在数据规模很大时会被带宽卡死。另外注意双缓冲如果偷懒写成x[i] x[i] x[i-d]那么第 i 号线程可能读到第 i-d 号线程刚写的新值这就不是依赖分析的问题了而是实打实的数据竞争结果不可复现。我在第一次实现时就是用了一个数组测试数据小看不出问题一放大就对不上后来才发现需要两个数组来回倒。这里也想强调一下写并行代码时避免同一个迭代内对共享内存读写重叠是第一原则依赖分析只能告诉你串行语义下有没有顺序要求真正的数据竞争要靠同步和复制来防。5.3 Blelloch 扫描work-efficient 的归约式写法Hillis-Steele 的O(n log n)工作量在大数组上不划算Blelloch 算法把工作量降回O(n)深度仍是O(log n)是现代 GPU 扫描库CUB、Thrust的底子。它分两步走先自底向上归约up-sweep再自顶向下分发down-sweep。// 前置条件n 是 2 的幂x 是输入数组 // 第一步up-sweep把数组变成一棵部分和树 for (int d 1; d n; d * 2) { int stride 2 * d; for (int i 0; i n; i stride) in parallel { x[i stride - 1] x[i d - 1]; } } // 第二步down-sweep从根开始把和往右侧分发 // 这里做的是 exclusive scanx[n-1] 先置 0 x[n - 1] 0; for (int d n / 2; d 1; d / 2) { int stride 2 * d; for (int i 0; i n; i stride) in parallel { int t x[i d - 1]; x[i d - 1] x[i stride - 1]; x[i stride - 1] t x[i stride - 1]; } }看不懂细节没关系核心思想是up-sweep 阶段让数组的某些位置积累出区间和down-sweep 阶段把这些区间和搬运给每个元素让每个位置都拿到它前面的累计和。整个过程中每个元素只参与常数次加法所以工作量和串行版本同阶只是并行深度变成O(log n)。这里有个工程上很容易搞混的点exclusive scan 和 inclusive scan 的差别。上面的 down-sweep 最终得到的是 exclusive 形式即out[i] sum(x[0..i-1])。要转成 inclusive要么最后再加一遍原始输入要么在初始化时预处理。CUB 和 Thrust 的接口里这两个版本分得很清楚选错直接差一个元素我建议写代码前先把语义写在注释里。5.4 从前缀和看依赖消除的本质前缀和这个案例给我们的启示是依赖分析只能识别依赖真正消除依赖的是算法、是数学性质。加法结合律允许我们调整括号把((ab)c)d变成(ab)(cd)依赖图就从一条链变成一棵树。泛化一下任何满足结合律的操作min、max、逻辑与或、矩阵乘法等都可以做类似的并行归约。反过来不满足结合律的操作比如浮点加法严格意义上也不满足但你愿意接受微小数值差异的话照样可以并行。这就是工程权衡不是所有数据依赖都要、都能消除有些是语义硬约束有些是可以用数值精度或额外空间换掉的。前缀和作为教科书级例子的意义就在于此——它同时演示了硬依赖长什么样、算法变换能做什么、以及工程上要付出的代价。6. 实操笔记用编译器和工具验证依赖判断6.1 GCC/Clang 向量化报告怎么读理论说再多不如让编译器亲口告诉你它看见了什么。GCC 的向量化报告gcc -O3 -marchnative -fopt-info-vec-missedmissed.txt scale_add.cClang 的对应选项更细clang -O3 -marchnative \ -Rpassloop-vectorize \ -Rpass-missedloop-vectorize \ -Rpass-analysisloop-vectorize \ scale_add.c打开missed.txt你会看到类似这样的行scale_add.c:4:5: note: loop not vectorized: unsafe dependent memory operations in loop scale_add.c:4:5: note: unknown data dependence between memory referencesunsafe dependent memory operations 和 unknown data dependence 是两个最常见的口吻。前者表示编译器确认了依赖后者表示编译器无法证明无依赖、保守放弃。实践中大部分无法证明其实都是指针别名问题。当你看到unknown时先别急着改算法优先考虑加restrict告诉编译器这两个指针不重叠void scale_add(double *restrict a, const double *restrict b, int n) { for (int i 1; i n; i) { a[i] a[i - 1] b[i]; // 加完 restrict编译器仍然会卡在 a 自身的循环携带依赖上 } }注意这个例子里restrict只解决了a和b的别名问题a[i-1]造成的内部依赖还在所以照样向量化失败。这说明读报告时要能区分外部别名和内部依赖别一见到 restrict 生效就以为万事大吉。6.2 手推一遍距离向量再写 restrict我现在的习惯是写高性能循环前先用纸笔把循环里每个数组访问的下标表达式抄出来算一遍距离向量和方向向量然后再打开编译器的向量化报告去印证。有一套判断顺序可以做参考如果只有一个数组且下标差为常量算距离距离为 0 看同迭代内是否有读写重叠距离大于 0 看它是否小于向量宽度。如果有两个数组参数先想清楚它们是否可能指向同一块内存能就加restrict。如果下标表达式带乘法或间接寻址a[b[i]]GCD 检验和方向向量都推不动尽早调整数据结构改成连续访问。编译器不是万能的它在可并行性证明上非常保守。你手推确认没有依赖后加restrict或重构循环往往能把 unknown 变成 vectorized。6.3 容易翻车的三个依赖判断误区第一个误区把 读同一变量 当成依赖。两个读操作之间的输入依赖不会阻塞任何重排但它会影响缓存局部性和公共子表达式消除分析时别把它们和 RAW 混为一谈。第二个误区忽略函数调用。循环里一旦出现外部函数调用编译器默认该函数可能读写任何内存等于把所有依赖全判为存在。我在一段日志代码里带上printf循环瞬间退化成串行。解法要么把函数内联要么用纯函数语义const、pure属性明确告诉编译器。第三个误区把静态依赖和数据竞争混为一谈。依赖分析是编译器基于串行语义做的静态推理数据竞争是实际并行执行时两个线程无同步地访问同一位置。两者有关系但不完全对应静态无依赖也可能因为调度问题产生竞争静态有依赖也不代表一定会竞争如果同步机制保护得好。排查并行程序崩溃时用 ThreadSanitizer 或 Helgrind 做动态检测跟编译器的静态依赖报告是两套工具、两套视角。6.4 一点个人经验最后说几句体感。我刚接触这些概念时总觉得依赖分析是学术圈的自嗨跟实际优化没什么关系。直到有一次在 GPU 上写归约乱序执行的锁步问题把我折磨了两个晚上我才真正意识到不理解依赖关系就不理解为什么硬件会在这里等你、为什么编译器会在那里放弃。前缀和那个例子让我印象最深——同样是x[i] x[i] x[i-1]换一种数据组织方式串行链就能变成并行树。瓶颈往往不在硬件而在你选择让数据以什么顺序流动。如果你现在正在被编译器优化报告折磨我的建议是别急着换编译器参数先把循环里的依赖关系画出来心里有数之后再决定是加restrict、拆循环、还是换算法。这套先依赖分析、再动手优化的方法我用了这些年几乎没有失手过。