并行算法模型

并行时间同时受总工作容量和最长依赖链约束：处理器再多也无法越过 span，关键路径再短也不能让有限处理器瞬间完成全部 work。模型把这两条轴先分开，再由调度、通信和具体处理器数解释实际 $T_P$，避免把理想加速比当作完整复杂度。

并行归并的任务轨迹 ​

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

这套“较长侧中点加串行二分”的归并，最长递归子问题至多约为原规模的 $3/4$，因此

总工作仍为 $O(n)$，但递归有对数层不等于 span 只有对数：每层还要支付一次二分查找。输出区间由秩预先确定，所以两支能独立写入，不需要竞争同一个尾指针。

在允许并发读输入、各块独占输出的共享内存模型中，对 $n\ge 2$ 可以用另一种归并机制取得线性工作和对数 span：把输出分成长度约 $\log n$ 的块，并行求每个输出边界在两输入中的 co-rank，即两侧各贡献多少项，再分别顺序合并各块。重复键固定由左输入先输出，可用一严格、一非严格的边界比较确定唯一 co-rank。

共有 $O(n/\log n)$ 个边界，每个定位用 $O(\log n)$ 工作；块内也只做线性于块长的归并。因此总工作 $O(n)$、span $O(\log n)$，但这是一种额外的分块/协同定秩构造。

把它放进并行 mergesort，可得到

若使用第一种递归归并，外层 span 满足 $D(n)=D(n/2)+O({\log }^{2}n)=O({\log }^{3}n)$。若明确换用上述 $O(\log n)$-span 的归并构造，才得到 $D(n)=D(n/2)+O(\log n)=O({\log }^{2}n)$。两种版本都保持 $O(n\log 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 外，至少还要报告消息数、通信字节、同步轮数，或用延迟—带宽模型写成

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

正确性与保证类型 ​

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

若运行时间理路时间复杂度Time complexity · Running time在固定计算模型与输入编码后，算法运行步骤数随输入规模增长的量级。写成“高概率 $O(f(n))$”，还要给失败概率和随机量词。平均处理器利用率、benchmark 加速或固定核数吞吐不是渐近 work/span 的替代品。

模型边界 ​

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

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