并行算法

破除误解：并行算法不是 GPU 编程，也不是「线程越多越快」#

把这篇读成 GPU 教程会错位。GPU 与并行计算 讲的是 SIMT 硬件、吞吐量和数据并行如何映射到数千个简单核心；本文讲的是算法在工作–跨度模型里的渐近账。一个工作有效、跨度对数的算法，仍可能因为分支发散、不规则访存而在 GPU 上输给一个工作更多但更规整的核函数。反过来，一个 CUDA 核很快，并不自动给出 $O(\log n)$ 跨度的证明。两篇文章共用「并行」这个词，对象一个是芯片上的调度单元，一个是 DAG 上的 $W$ 与 $S$。

Amdahl 定律常被误当成并行算法的全部。它说串行比例 $f$ 会把加速比封在 $1/(f+(1-f)/p)$。工作–跨度模型更细：所谓串行比例，往往就是跨度 $S$ 在 $W$ 里的份额，但 $S$ 本身可以被算法改写。前缀和把看起来串行的累加改成跨度 $O(\log n)$；那不是在 Amdahl 的 $f$ 里挤牙膏，而是换了一张 DAG。布伦特不等式里 $W/p$ 与 $S$ 两项，哪一项主导，随 $p$ 变化：处理器少时像均分，处理器多时撞上跨度。

第三个误解是「工作有效」等于「实际最快」。工作有效（work-efficient）指 $W$ 与最优串行同阶，通常允许对数因子。跨度很小但工作变成 $n\log n$ 的算法，在 $p\ll n$ 时可能比一个 $W=n$、$S=n$ 的串行扫描更慢。并行算法必须同时报两个数，只报加速比没有意义。

工作–跨度与布伦特定理#

把计算写成 DAG：节点是常数时间操作，边是必须先发生的依赖。工作 $W$ 是节点数，跨度 $S$ 是最长路径长度。$p$ 台处理器的贪心调度（任意就绪节点可立刻执行）满足

$$\frac{W}{p}\ \le\ T_p\ \le\ \frac{W}{p}+S.$$

下界几乎是定义：每台处理器每步最多做 1 个单位工作，且不能短于关键路径。上界是布伦特的调度论证：任意时刻要么所有处理器都忙，要么「闲」是因为依赖还没到——把闲步记到跨度上。现代表述里常写成 $T_p\le W/p+O(S)$，隐藏调度开销。Cilk 的工作窃取把期望时间推到 $W/p+O(S)$，并给出与 $p$ 相关的空间界。

因此算法设计的目标函数是一对：最小化 $W$，同时压缩 $S$。只压缩 $S$ 而让 $W$ 涨成 $n^2$ 的「全并行穷举」没有价值。只保持 $W$ 而让 $S=W$ 的「表面上可并行」也没有价值。工作有效且跨度多对数，是并行算法里「好」的默认含义。

调度不是免费的。fork 一次、join 一次，模型里常算常数跨度，实现里是任务队列与缓存亲和。当任务粒度小于调度开销，$W$ 的纸面优势会被吃掉。粒度选择是把渐近模型接到常数的那一步，不是另一套理论。

前缀和：从串行扫描到工作有效的对数跨度#

前缀和（prefix sum / scan）：给定 $a_1,\ldots,a_n$ 与结合运算 $\oplus$，计算 $s_i=a_1\oplus\cdots\oplus a_i$。串行一次扫描 $W=n$、$S=n$。Hillis 与 Steele 的双对数算法用反复倍增，跨度 $O(\log n)$，但工作是 $O(n\log n)$：每个位置反复把自己加上距离 $2^k$ 的邻居。它展示了对数跨度，却不是工作有效。

布莱洛克（Blelloch）的工作有效扫描分两趟。上趟把相邻元素两两结合，递归得到偶数位置的前缀；下趟把偶数前缀播回奇数位置。工作 $W=O(n)$，跨度 $O(\log n)$。这是并行算法课的标准范例，因为它把「结合性」用到了极致：没有结合性，DAG 就不能平衡成树。扫描随后成为排序（radix 的桶偏移）、稀疏矩阵压缩、分配器、以及几乎所有数据并行原语的底座。

CREW PRAM 上，带倍增的指针跳跃也能在 $O(\log n)$ 跨度里处理链表前缀，但工作通常更大，且依赖并发读。EREW 更严：同一单元不能被两台处理器同时读，算法必须先把数据复制到私有位置，复制本身又是前缀问题。模型的读写规则会改变同一问题的工作，这是 PRAM 作为算法分类工具的价值，不是对今日缓存一致性的字面模拟。

PRAM 档位、工作有效与 fork-join#

EREW：同时刻任何内存单元至多被一台处理器读或写。CREW：可并发读、不可并发写。CRCW：可并发写，再按「相同值才允许」「任意一个获胜」「优先级」分成几种子模型。同一问题在 CRCW 上有时跨度更短（例如用并发写做常数时间 OR），但这些指令在硬件上对应的是更强的同步原语。PRAM 论文比较的是信息流允许何种冲突，不是推荐你买哪种总线。

NC 类收集「多项式处理器、多对数时间」的问题，大致对应跨度多对数、工作多项式。P 完全问题（如电路值、某些最大流变体）被当作「本质上串行」的候选：在标准归约下，它们不太可能掉进 NC。这是并行算法的下界文化：不是所有多项式问题都有浅 DAG。最大流、线性规划、某些动态规划，跨度下界与细粒度假设相连，不能想当然地「并行化循环」。

Fork-join（Cilk、OpenMP 的 task、Java 的 fork-join 池）把 DAG 的生成写成语言原语：spawn 生成可并行子计算，sync 等待。工作–跨度分析可以直接在程序结构上做，不必先画满整张图。莱瑟森等人证明：工作窃取调度器在这套原语上接近布伦特界，且空间与串行执行同阶乘以 $p$ 的小倍数。这把 1970 年代的 PRAM 分析接到了 1990–2000 年代的运行时。MapReduce 是另一张 DAG：shuffle 的跨度被磁盘与网络主导，工作是 map/reduce 函数的总和；它是数据并行的工程模型，不是 PRAM 的替代定理。

与 GPU 的对照可以停在这一句：PRAM/fork-join 问的是任意 DAG 上的依赖；SIMT 要求锁步的同类指令与合并访存。把扫描写成工作有效的递归，在 CPU 多核上合理；在 GPU 上通常改成 Blelloch 的迭代、warp 内洗牌和块内共享内存，为的是匹配硬件，而不是改写 $W$ 与 $S$ 的定义。复杂度账仍然适用，只是常数和合法 DAG 的形状被芯片收紧了。

扫描之上：排序、列表与图#

有了工作有效扫描，许多算法变成「先标号、再搬运」。基数排序的每一数位：计数、扫描出桶偏移、按偏移写入，工作 $O(n)$ 乘以位数，跨度 $O(\log n)$ 乘以位数。比较排序里，Cole 的并行归并排序在 PRAM 上做到工作 $O(n\log n)$、跨度 $O(\log n)$，是工作有效且跨度最优的经典结果；简单的「两半递归再串行归并」会把跨度做成 $O(\log^2 n)$ 或把工作做成超线性，取决于归并是否本身并行。并行归并可以用双调或按秩划分，各自在工作与跨度之间换常数。

指针跳跃处理的是链表，不是数组。每个节点保存后继，一轮把后继改成后继的后继，距离倍增，跨度 $O(\log n)$。链表前缀、根树求欧拉序、树的子树大小，都走这条路。工作通常是 $O(n\log n)$，除非像扫描那样改成两趟收缩。它展示 PRAM 相对电路的特点：间接寻址是合法操作，算法可以沿着指针走；电路必须把间接展开成选择器。EREW 上的指针跳跃要先解决并发读同一后继的问题，常用的办法是先复制再跳。

图算法的跨度更硬。连通分量在 CRCW 上有接近常数的随机算法，EREW 上则需要对数或多对数，取决于是否允许哈希。最小生成树的 Borůvka 轮是对数的，每轮收缩连通块；工作要控制在 $O(E\log V)$ 附近才谈得上工作有效。最短路的并行化撞上依赖：Ford 式松弛的轮数可以到 $n$，跨度跟着变成线性，于是「并行 Dijkstra」常常只是并行找最小值，跨度仍被递减键支配。P 完全把若干图问题标成「别指望 NC」：电路值、深度优先搜索的字典序、某些匹配变体，在对数空间归约下卡住浅电路。并行算法的诚实报告是：扫描和排序有漂亮的 $W,S$，一般图只有部分问题有。

矩阵乘法提供另一极。$n\times n$ 乘法工作 $O(n^\omega)$，平凡分块的跨度 $O(\log n)$（加法树），处理器需求随 $n^2$ 涨。Strassen 递归在 fork-join 里很干净：七个子乘法可并行，跨度仍是 $O(\log n)$ 乘以递归层。它工作有效相对于 Strassen 串行，但不相对于小学乘法——比较对象必须写明。GPU 上人们很少跑 Strassen，因为不规则与数值稳定性；这再次说明工作–跨度最优不等于芯片最优。

工作有效的判据与加速比#

设串行最优是 $T_1^*$。算法工作有效，若 $W=\Theta(T_1^*)$。$p$ 台处理器上的加速比至多 $T_1^*/T_p\le T_1^*/(W/p)$，因此工作膨胀直接封顶加速比。跨度有限时，当 $p\approx W/S$ 达到所谓并行度，再加处理器会被 $S$ 卡住。这个 $W/S$ 是算法海报上最有用的一个数：它告诉你这张 DAG 值得配多少核。前缀和 $W/S=\Theta(n/\log n)$，所以在几千核的机器上仍可能有空间；跨度为 $\sqrt n$ 的算法，并行度只有 $\sqrt n$，再堆 GPU 线程没有渐近意义。

布伦特不等式的加号不是装饰。$T_p\le W/p+S$ 在 $p=1$ 时给出 $T_1\le W+S$，通常 $S\le W$，故 $T_1=\Theta(W)$。这保证「用串行跑这张并行 DAG」不会比工作更坏一个因子以上。Cilk 的工作窃取再把期望 $T_p$ 接到 $W/p+O(S)$，并证明空间 $O(S_1 p)$ 量级（$S_1$ 为串行空间）。分析假设的是独立调度器，不是把线程绑死在操作系统进程上。把 fork-join 程序展开成百万操作系统线程，会把 $S$ 偷偷加进调度延迟，不等式的实验验证就会失败。

消息传递模型（BSP、LogP）把跨度改写成超步或间隙：一次全局同步是固定延迟 $L$，一次远程写是 $g$。工作有效的 PRAM 算法搬到 BSP 上，往往要先把细粒度读写聚成块，否则 $g$ 会把 $S$ 重新变成线性。这解释了为什么 MapReduce 与 MPI 程序看起来不像 PRAM 扫描：它们在最小化超步，而不是最小化 PRAM 步。工作–跨度仍然可用——把一次 shuffle 算成跨度里的一层——但必须把网络延迟写进 $S$，不能假装共享内存是免费的。Valiant 的 BSP 论文把这套会计说成可移植的桥：先在 PRAM 上设计 $W,S$，再按 $p,L,g$ 选择粒度。工作有效对 BSP 的意义是：超步内的本地工作仍与串行同阶，跨度则改用超步次数来报。前缀和在 BSP 上变成对数次全局通信加线性本地扫描，和共享内存扫描是同一张结合树，只是边的成本从一次读变成一次消息。通信轮次写成跨度，本地扫描写成工作，布伦特的两项仍然分开记账。把 shuffle 算进跨度之后，再谈加速比才不会把网络空等算成算法胜利。

代价与争议#

处理器模型会过时，下界却常被连坐。CRCW 上的常数时间技巧不能翻译到消息传递；把 PRAM 下界说成「多核做不到」，忽略了缓存、预取和向量单元已经改变常数。反过来，忽略跨度、只堆线程，会在依赖链上制造缓存颠簸。正确的态度是：用 $W,S$ 做第一张地图，再用存储层次做第二张。

工作有效的理论算法，实现复杂度可以很高。三维划分矩阵乘法、某些并行连通分量，渐近好看，工程上输给库里的分块 GEMM 或标签传播。并行算法领域的健康状态，取决于是否同时维护「NC / 工作–跨度」的分类和「可在 BLAS/Cilk/CUDA 里跑」的实现。两者互相不能替代。

确定性与嵌套并行也有争议。工作窃取的随机性使运行时间成为高概率界；某些实时与可重现调试场景要求确定性调度，于是放弃一部分期望性能。嵌套并行很好分析，但不规则图算法会产生百万个小任务。没有粒度控制，布伦特的 $W/p$ 只存在于纸上。

跨域连接#

• 图论：工作–跨度模型把计算本身当成 DAG：节点是操作，边是必须维持的先后。布伦特不等式是这张图上的路径与割的算术——跨度是最长路径，工作是节点计数。并行算法的改进，往往是换一张等价但更浅的计算图，而不是在同一条链上多派处理器。连通分量与 Borůvka 轮则把输入图的收缩写成计算图的一层，两条图论叠在一起。
• 组合学：前缀和、平衡树归约、指针跳跃都依赖结合运算与可重排的括号结构。工作有效扫描的两趟递归，是把长度为 $n$ 的链重写成深度对数的结合树。没有组合上的结合性，浅 DAG 不存在；有结合性，才谈得上 NC 里的扫描、排序与基数分桶。括号重排的合法性，就是并行度的来源。
• 证明：布伦特定理和 Cilk 的工作窃取界都是调度的证明，不是芯片手册。阅读并行算法论文时，要分清「存在一张跨度为 $S$ 的 DAG」与「该 DAG 可在给定存储模型里无冲突地执行」。EREW 比 CREW 多出来的复制步骤，必须写进证明，否则跨度会在实现里偷偷变长。证明停在哪一个模型，结论才能走到哪一种硬件。
• 范畴论：fork-join 把并行合成写成可结合的双线性结构：两个子计算并置，再在 join 处配对。扫描作为列表上的同态，正是可结合幺半群上的 map-reduce。范畴语言不替代 $W$ 与 $S$，但它解释为什么同一套原语能从 PRAM 证明迁到语言运行时——因为合成律先于处理器数目，也先于 SIMT 是否锁步。

参考文献#

• Brent, R. P. "The Parallel Evaluation of General Arithmetic Expressions." Journal of the ACM 21(2):201–206, 1974.
• Blelloch, G. E. "Prefix Sums and Their Applications." Technical Report CMU-CS-90-190, 1990.
• Hillis, W. D. & Steele, G. L. "Data Parallel Algorithms." Communications of the ACM 29(12):1170–1183, 1986.
• Blumofe, R. D. & Leiserson, C. E. "Scheduling Multithreaded Computations by Work Stealing." Journal of the ACM 46(5):720–748, 1999.
• JáJá, J. An Introduction to Parallel Algorithms. Addison-Wesley, 1992.

延伸阅读#

• Blelloch, G. E. & Maggs, B. M. "Parallel Algorithms." 见 The Computer Science and Engineering Handbook 诸版中的综述章。
• Cormen, T. H., Leiserson, C. E., Rivest, R. L. & Stein, C. Introduction to Algorithms. 多线程章节（Cilk 工作–跨度）。