并行算法模型

四个必须分开的量 ​

对同一并行计算，记 $T_P$ 为使用 $P$ 个处理器的执行时间。两个极端量是

$$T_1\text{与}{T}_{\mathrm{\infty }},$$

前者是在一个处理器上执行并行程序全部工作所需时间，后者是在无限处理器下仍受依赖限制的时间，也称 span 或 depth。若每个原子任务单位成本，work $W=T_1$、span $D=T_{\mathrm{\infty }}$。

任意调度都满足

$$T_P\ge max\{T_1/P,T_{\mathrm{\infty }}\}.$$

第一项是容量下界，第二项是关键路径下界。只说“深度 $O(\log n)$”会隐藏总工作可能是 $\mathrm{\Theta }(n^2)$；只说“工作线性”又不说明是否有足够独立任务。

加速比、效率与成本 ​

相对同一算法的串行执行，加速比与处理器效率定义为

$$S_P=\frac{T_1}{T_P},E_P=\frac{S_P}{P}=\frac{T_1}{P{T}_P}.$$

总处理器成本是 $P{T}_P$。若 $T_1$ 与已知最佳串行算法同阶，才称 work-efficient；一个并行算法即使 $E_P$ 接近 1，若自身 $T_1$ 比最佳串行方案大很多，仍可能浪费工作。

实际报告还应写明 $P$ 是固定常数、输入函数还是上限。把 $P=n$ 代入理想式得到的时间，不能当作任意机器上的复杂度。

并行归并的任务轨迹 ​

合并两个各长 $n/2$ 的有序数组时，可从较长数组取中点元素 $x$，在另一个数组二分出 $x$ 的秩；这两个位置确定 $x$ 的最终输出下标，也把问题分成两个互不重叠的子归并。两子问题并行递归，写入的输出区间互斥。

每层所有二分与分割的总工作可控制在线性量级，递归深度为对数级；具体并行 merge 版本可达到 $O(n)$ work、$O(\log n)$ span。若直接让多个线程从共同输出尾指针抢位置，排序正确性和写冲突都需要额外同步，已不是同一 DAG。

把它放进并行 mergesort，可得到

$$W(n)=2W(n/2)+O(n)=O(n\log n),$$

span 取决于所用 merge：若每层 merge span 为 $O(\log n)$，则 $D(n)=D(n/2)+O(\log n)=O({\log }^{2}n)$。这说明子调用并行不等于整个算法自动只有一层对数深度。

共享内存、PRAM 与 fork–join ​

共享内存线程通过 load/store、原子操作和同步原语交流，缓存一致性与伪共享会影响成本。PRAM公理库PRAM 模型PRAM · parallel random-access machine让同步处理器访问共享随机存取内存，并以读写冲突规则区分 EREW、CREW 与 CRCW。把执行切成同步轮，并按 EREW、CREW、CRCW 规定同一单元的并发访问；它适合算法结构分析，却不计缓存层次。

Fork–join 程序在 spawn 时产生可并行子任务，在 sync 时等待子任务完成，执行可表示为动态 DAG。Work–Depth 模型公理库Work–Depth 模型work-depth model · work-span model · computation DAG model把并行计算表示为依赖 DAG，以总工作 W 和关键路径深度 D 分离工作量与并行性。抽去具体线程数，先分析 $T_1,T_{\mathrm{\infty }}$，再由调度定理映射到 $T_P$。

这些模型描述的冲突规则不同。PRAM 的同步轮不能无条件等同于现实线程 barrier；fork–join 的动态任务也不要求预先枚举所有处理器指令。

分布式内存与通信 ​

分布式内存中，处理器只能直接访问本地数据，远端信息通过消息传递。除 work 与 span 外，至少还要报告消息数、通信字节、同步轮数，或用延迟—带宽模型写成

$$\alpha \cdot \mathrm{\#}messages+\beta \cdot \mathrm{\#}words.$$

低 span 并不保证低通信。例如每轮让所有处理器读取一个远端中心值，在 PRAM CREW 中可视作常数轮，在网络上却可能形成广播瓶颈。数据划分、拓扑和局部内存容量属于模型前提。

正确性与保证类型 ​

并行正确性公理库算法正确性Algorithm correctness · Partial and total correctness所有合法执行都符合规格，并在完全正确时保证终止。既要证明输出满足规格，也要证明所有允许交错下无数据竞争或冲突由模型规则解决。确定性 DAG 的 work/span 是最坏界；随机算法要说明期望对随机输入、算法硬币还是调度器随机性取。

若运行时间写成“高概率 $O(f(n))$”，还要给失败概率和随机量词。平均处理器利用率、benchmark 加速或固定核数吞吐不是渐近 work/span 的替代品。

模型边界 ​

内存带宽、cache miss、NUMA、任务创建和 barrier 开销都可能使 $T_P$ 大于理想调度界。Amdahl 定律强调固定串行部分，Work–Depth 则把它表现为关键路径；二者都不能消除通信成本。

空间也需区分总空间与每处理器本地空间。为了把 span 降低而复制 $P$ 份长度 $n$ 的数组，会把总空间推到 $\mathrm{\Theta }(Pn)$，不能只报告每线程 $O(n)$。

参考资料

• Guy Blelloch, Programming Parallel Algorithms, Communications of the ACM, 1996.
• Thomas Cormen et al., Introduction to Algorithms, 4th ed., MIT Press, 2022, multithreaded algorithms chapters.
• Richard Cole, Parallel Merge Sort, SIAM Journal on Computing, 1988.