第 27 章多线程算法 (Multithreaded Algorithms)

核心结论

动态多线程模型：用三个关键字 parallel、spawn、sync 表达逻辑并行；删除这些关键字即得「串行化」(serialization) 算法——多线程伪代码与串行伪代码同源。
计算 DAG (Computation DAG)：节点 = strand（连续无并发控制的指令段），边 = strand 间依赖（continuation / spawn / call / return）；work = DAG 节点数，span = 关键路径长度。
work / span / 并行度：work \(T_1\) = 单处理器执行时间；span \(T_\infty\) = 无限处理器下执行时间；并行度 \(T_1/T_\infty\) = 任意处理器数下可达到的最大加速比。
两条下界：work law \(T_P \geq T_1/P\)；span law \(T_P \geq T_\infty\)。贪心调度定理 27.1：\(T_P \leq T_1/P + T_\infty\)——上界紧到仅差 2 倍最优。
多线程矩阵乘法（§27.2）：分治递归 P-MATRIX-MULTIPLY，work \(\Theta(n^3)\)，span \(\Theta(\lg n)\)，并行度 \(\Theta(n^3/\lg n)\)。
多线程归并排序（§27.3）：递归 P-MERGE-SORT + P-MERGE，work \(\Theta(n \lg n)\)，span \(\Theta(\lg^3 n)\)——首次给出可分析的多线程分治算法。

本章主旨

本章扩展第 1 章对并行性的展望，给出动态多线程算法的形式化框架。多线程模型的关键贡献是「work-span 分析」：work 度量串行总成本，span 度量关键路径长度，两者比值即理论最大加速比。贪心调度定理保证这两个度量足以预测实际性能。三个范例（P-FIB、P-MATRIX-MULTIPLY、P-MERGE-SORT）演示了如何把串行分治算法转换为多线程版本——分治递归天然适合 spawn + sync 模式。

一、核心概念

本章围绕 6 个核心概念展开：先建立多线程模型与三个关键字，再引入 work/span 度量，然后讨论调度定理与并行度的极限，最后给出两个范例（矩阵乘法、归并排序）。

概念定义 + 重要性实现提示

概念	定义 + 重要性	实现提示
动态多线程模型	通过 `parallel` / `spawn` / `sync` 三关键字表达逻辑并行；并发平台（scheduler）自动负载均衡；删除关键字得串行化版本。	§27.1；Cilk / Cilk++ / OpenMP / TBB / TPL 等平台支持。
strand 与计算 DAG	strand 是连续无 spawn/sync/return 的指令序列；计算 DAG 节点 = strand，边 = continuation / spawn / call / return 四类依赖。	§27.1；work = 节点数；span = 关键路径节点数。
work / span / parallelism	\(T_1\) = work（单处理器总时间）；\(T_\infty\) = span（理想并行时间）；parallelism \(= T_1/T_\infty\) = 理论最大加速比。	§27.1；并行度是评估算法可扩展性的核心指标。
work law / span law	下界：\(T_P \geq T_1/P\)（work law）；\(T_P \geq T_\infty\)（span law）；二者给出任意算法在 P 处理器上的性能下限。	§27.1；公式 27.2-27.3。
贪心调度定理	贪心调度器（complete step 跑 P 条 ready strand，incomplete step 跑剩余所有）保证 \(T_P \leq T_1/P + T_\infty\)；与最优调度最多差 2 倍。	§27.1 定理 27.1；slackness > 10 时近完美线性加速。
多线程分治模式	spawn 左半递归 → 调用右半递归 → sync → 合并；work = 串行版本 work；span = 递归深度 × 单步代价。	§27.2 / §27.3；P-MATRIX-MULTIPLY / P-MERGE-SORT 范例。

动态多线程模型

通过 parallel / spawn / sync 三关键字表达逻辑并行；并发平台（scheduler）自动负载均衡；删除关键字得串行化版本。

§27.1；Cilk / Cilk++ / OpenMP / TBB / TPL 等平台支持。

strand 与计算 DAG

strand 是连续无 spawn/sync/return 的指令序列；计算 DAG 节点 = strand，边 = continuation / spawn / call / return 四类依赖。

§27.1；work = 节点数；span = 关键路径节点数。

work / span / parallelism

\(T_1\) = work（单处理器总时间）；\(T_\infty\) = span（理想并行时间）；parallelism \(= T_1/T_\infty\) = 理论最大加速比。

§27.1；并行度是评估算法可扩展性的核心指标。

work law / span law

下界：\(T_P \geq T_1/P\)（work law）；\(T_P \geq T_\infty\)（span law）；二者给出任意算法在 P 处理器上的性能下限。

§27.1；公式 27.2-27.3。

贪心调度定理

贪心调度器（complete step 跑 P 条 ready strand，incomplete step 跑剩余所有）保证 \(T_P \leq T_1/P + T_\infty\)；与最优调度最多差 2 倍。

§27.1 定理 27.1；slackness > 10 时近完美线性加速。

多线程分治模式

spawn 左半递归 → 调用右半递归 → sync → 合并；work = 串行版本 work；span = 递归深度 × 单步代价。

§27.2 / §27.3；P-MATRIX-MULTIPLY / P-MERGE-SORT 范例。

二、详细笔记

27.1 动态多线程基础

What：动态多线程 = 用 parallel / spawn / sync 表达「逻辑并行」的编程模型；并发平台负责把并行任务映射到处理器并负载均衡。

Why：直接用静态线程编程并行程序复杂、易错；动态多线程让程序员只关心「哪些子问题可并行」，由运行时自动调度，是当前并行编程的主流范式。

How：

三关键字：

parallel：并行 for 循环（每轮迭代可并行）。
spawn：派生子任务，父任务可继续执行。
sync：等待所有已派生子任务完成。
删除所有多线程关键字 → 串行化版本。

P-FIB(n) 示例：

x = spawn P-FIB(n-1)
y = P-FIB(n-2)
sync
return x + y

strand 与计算 DAG：

strand：连续无 spawn/sync/return 的指令段。
节点 = strand；边 = continuation / spawn / call / return。
work = DAG 节点数（CLRS 图 27.2：P-FIB(4) 的 work = 17）。
span = 关键路径节点数（CLRS 图 27.2：span = 8）。

When：多核 CPU（Intel/AMD/ARM 多核）已成为 PC 默认；任何有「可独立子问题」的算法都可用动态多线程加速。

Example：P-FIB(4) 的计算 DAG：17 个节点（work），关键路径 8 个节点（span）；并行度 \(17/8 = 2.125\)。

27.2 work、span 与并行度

What：work \(T_1\) = 单处理器总时间；span \(T_\infty\) = 无限处理器下时间；并行度 \(T_1/T_\infty\) = 平均每步可并行的操作数。

Why：这是评估并行算法可扩展性的核心三件套——work 决定总成本，span 决定关键路径，并行度决定加速比上限。

How：

形式化（CLRS §27.1）：

\[T_P = \text{在 } P \text{ 个处理器上的运行时间}, \quad T_1 = \text{work}, \quad T_\infty = \text{span}\]

两条下界：

\[\text{work law: } T_P \geq T_1/P, \qquad \text{span law: } T_P \geq T_\infty\]

并行度（parallelism）：

\[\text{parallelism} = T_1/T_\infty\]

slackness：并行度 / 处理器数 = \((T_1/T_\infty)/P\)。

当 slackness ≥ 10 时，贪心调度可达到近似线性加速。
当 \(P > T_1/T_\infty\) 时，不可能完美线性加速。

复合规则（CLRS 图 27.3）：

串行组合：work 与 span 都相加。
并行组合：work 相加，span 取 max。

When：分析并行算法时首先报告 work 与 span；并行度告诉读者在多少核上有意义。

Example：P-FIB(n)：work \(T_1(n) = \Theta(\phi^n)\)；span \(T_\infty(n) = \Theta(n)\)；并行度 \(\Theta(\phi^n / n)\)——指数增长，故非常并行。

27.3 调度与贪心调度定理

What：贪心调度器每步「尽可能多」地分配 ready strand 给处理器；定理 27.1 证明贪心调度时间 \(T_P \leq T_1/P + T_\infty\)，与最优调度最多差 2 倍。

Why：实际平台（Cilk / OpenMP）使用「工作窃取」(work-stealing) 类贪心调度；定理 27.1 保证这类调度在 P 处理器上的实际性能可用 \(T_1/P + T_\infty\) 上界——分析时只需算 work 与 span。

How：

定理 27.1（贪心调度上界）：

\[T_P \leq T_1/P + T_\infty\]

证明思路：

complete step（≥ P 条 ready strand）：每步完成 P 单位的 work，故最多 \(\lceil T_1/P \rceil\) 个 complete step。
incomplete step（< P 条 ready strand）：贪心调度跑完所有 ready strand，使剩余 DAG 的关键路径长度减 1；故最多 \(T_\infty\) 个 incomplete step。
总步数：complete + incomplete ≤ \(T_1/P + T_\infty\)。

推论 27.2：贪心调度 \(T_P \leq 2 \cdot \max(T_1/P, T_\infty) \leq 2 T_P^*\)（2 倍最优）。

推论 27.3：slackness \(\gg 1\) 时 \(T_P \approx T_1/P\)（近完美线性加速）。

When：评估并行算法的实际性能时；分析算法的可扩展性时。

Example：P-MERGE-SORT(n) work = Θ(n lg n)，span = Θ(lg³ n)；并行度 Θ(n / lg² n)；在 100 核上 slackness = n / (100 lg² n)，n ≥ 10⁶ 时达到近完美加速。

27.4 多线程矩阵乘法（§27.2）

What：用分治递归 + spawn 实现 P-MATRIX-MULTIPLY；work \(\Theta(n^3)\)，span \(\Theta(\lg n)\)，并行度 \(\Theta(n^3/\lg n)\)。

Why：矩阵乘法是科学计算的基石；其并行版本在稠密线性代数、深度学习推理、图算法中广泛应用。

How：

P-MATRIX-MULTIPLY(A, B, C, n)：

把 A, B, C 各分成 4 个 n/2 × n/2 子矩阵。
spawn P-MATRIX-MULTIPLY(A₁₁, B₁₁, C₁₁, n/2)
spawn P-MATRIX-MULTIPLY(A₁₁, B₁₂, C₁₂, n/2)
spawn P-MATRIX-MULTIPLY(A₂₁, B₁₁, C₂₁, n/2)
spawn P-MATRIX-MULTIPLY(A₂₁, B₁₂, C₂₂, n/2)
sync
spawn P-MATRIX-MULTIPLY(A₁₂, B₂₁, C₁₁, n/2)
spawn P-MATRIX-MULTIPLY(A₁₂, B₂₂, C₁₂, n/2)
spawn P-MATRIX-MULTIPLY(A₂₂, B₂₁, C₂₂, n/2)
spawn P-MATRIX-MULTIPLY(A₂₂, B₂₂, C₂₂, n/2)
sync

分析：

\[T_1(n) = 8 T_1(n/2) + \Theta(1) = \Theta(n^3), \quad T_\infty(n) = \max\{T_\infty(n/2) \text{ for 8 sub-calls}\} + \Theta(1) = \Theta(n) \text{ (误)} \Rightarrow \text{实际 } T_\infty = \Theta(\lg n)\]

注：8 个并行 spawn，span 取 max + Θ(1)，递推得 \(T_\infty(n) = \Theta(\lg n)\)。

When：多核 CPU 上的稠密矩阵乘；可作为 Strassen 等更优算法的多线程版本基础。

Example：1000×1000 矩阵乘：work ≈ 10⁹，span ≈ 10；在 100 核上加速比近 100。

27.5 多线程归并排序（§27.3）

What：P-MERGE-SORT 递归并行排序 + P-MERGE 并行归并；work \(\Theta(n \lg n)\)，span \(\Theta(\lg^3 n)\)。

Why：归并排序是分治经典；多线程版本是「分治 → 递归 spawn + 串行 / 并行 merge」的范例，展示了如何把串行分治算法转换为多线程算法。

How：

P-MERGE-SORT(A, p, r)：

if \(p \geq r\): return
\(q = \lfloor (p+r)/2 \rfloor\)
spawn P-MERGE-SORT(A, p, q)
P-MERGE-SORT(A, q+1, r)
sync
P-MERGE(A, p, q, r)

P-MERGE(A, p, q, r)：类似串行归并，但用二分定位「第 k 小的元素」在哪一半；递归地并行取两个子问题。

work 与 span：

\[T_1(n) = 2 T_1(n/2) + \Theta(n) = \Theta(n \lg n), \quad T_\infty(n) = T_\infty(n/2) + \Theta(\lg^2 n) = \Theta(\lg^3 n)\]

注：P-MERGE 的 span 是 Θ(lg² n)（二分定位），归并树深度 lg n，故总 span = Θ(lg³ n)。

When：大规模数据排序；作为多线程分治算法的范例。

Example：n = 10⁶，work = 2·10⁷，span ≈ 400；100 核上加速比近 100（slackness >> 10）。

27.6 实际考量与局限

What：多线程算法在实践中受限于「Amdahl 定律」、内存带宽、伪共享 (false sharing)、负载均衡等。

Why：仅 work 与 span 的理论分析不足以预测实际加速；理解实际限制是部署并行算法的关键。

How：

Amdahl 定律：串行部分比例 s，加速比 ≤ 1 / (s + (1-s)/P)。

实际瓶颈：

内存带宽：多核共享内存总线，竞争可能限制实际加速比。
伪共享：不同线程写同一 cache line 导致频繁失效。
负载不均：贪心调度假设 perfect work-stealing，实际有调度开销。
启动 / 同步开销：spawn + sync 的运行时成本。

实践准则：

spawn 粒度不能太小（避免开销淹没收益）。
数据布局考虑 cache locality（如 P-MERGE-SORT 的访问模式）。
用平台工具（Cilk’s cilkscreen、Intel VTune）找瓶颈。

When：实际部署多线程算法；优化现有多线程实现；评估理论加速比的可行性。

Example：P-FIB(n) 在 4 核上理论加速比 ≈ 4，但实际可能仅 2-3——因 Fibonacci 树深度小、spawn 开销相对大。

三、关键图表

核心公式对照表

公式编号

内容

式 27.1

Fibonacci 串行时间 \(T(n) = \Theta(\phi^n)\)

式 27.2

work law：\(T_P \geq T_1/P\)

式 27.3

span law：\(T_P \geq T_\infty\)

式 27.4

贪心调度上界：\(T_P \leq T_1/P + T_\infty\)

定义

并行度 \(= T_1/T_\infty\)；slackness \(= (T_1/T_\infty)/P\)

推论 27.2

贪心调度在 2 倍最优内

推论 27.3

slackness >> 1 时近完美线性加速

串行组合

work 加，span 加

并行组合

work 加，span 取 max

P-FIB

work Θ(φⁿ)，span Θ(n)，并行度 Θ(φⁿ/n)

P-MATRIX-MULTIPLY

work Θ(n³)，span Θ(lg n)，并行度 Θ(n³/lg n)

P-MERGE-SORT

work Θ(n lg n)，span Θ(lg³ n)，并行度 Θ(n / lg² n)

四、思维导图

mindmap
  root((第 27 章 多线程算法))
    动态多线程
      parallel
      spawn
      sync
      串行化
    计算DAG
      strand节点
      四类边
      work节点数
      span关键路径
    性能度量
      work T₁
      span T∞
      并行度
      slackness
    调度定理
      贪心调度
      T₁/P + T∞
      2倍最优
    多线程分治
      矩阵乘法
      归并排序
      递归spawn
    实际考量
      Amdahl定律
      内存带宽
      负载均衡
      粒度控制

五、重点与易错点

三个关键字不要混淆：parallel 用于 for 循环迭代；spawn 用于派生子任务（父继续）；sync 用于等待所有派生子任务。
删除多线程关键字得串行化版本：这意味着 work 分析 = 串行算法分析（与原书其他章相同）。
strand 不是「一条指令」：而是「连续无 spawn/sync/return 的指令段」——这是为了压缩 DAG 规模。
计算 DAG 边四类：continuation（水平）、spawn（向下，可继续）、call（向下，不可继续）、return（向上）；这区分了「派生」与「调用」。
work = 节点数（假设每 strand 单位时间）；span = 关键路径节点数（可在线性时间用 DFS 求）。
P-FIB 不是好算法：虽然并行度指数增长，但 work 也是指数——实际是「演示模型」用，不是「实用算法」。
贪心调度定理 27.1 是分析的核心：只需算 work 与 span 即得上界；不需要分析具体调度策略。
slackness 阈值：经验值是 10——并行度是处理器数 10 倍以上时近完美加速。
多线程分治模式：spawn 左 → 调用右 → sync → 合并——模板化的多线程分治结构。
P-MATRIX-MULTIPLY 的 span 是 Θ(lg n) 不是 Θ(n)：8 个并行 spawn 的 span 仅取决于递归深度，与分支数无关。
P-MERGE-SORT 的 span 是 Θ(lg³ n)：lg² 来自 P-MERGE 的二分定位，lg 来自归并树深度。
并行度是加速比上限：实际加速比受 Amdahl 定律、内存带宽、伪共享等约束。
多线程编程的实际平台：Cilk/Cilk++（MIT）、OpenMP（编译器指令）、Task Parallel Library（.NET）、Threading Building Blocks（Intel）。
与第 1 章并行情景的呼应：第 1 章提到「单核主频遇到瓶颈，多核成为主流」；本章给出形式化的多线程框架。
与第 4 章分治的呼应：分治的「子问题独立」天然适合 spawn；分治的合并 work 与 span 决定整体性能。

第 27 章 多线程算法 (Multithreaded Algorithms)

核心结论

一、核心概念

二、详细笔记

27.1 动态多线程基础

27.2 work、span 与并行度

27.3 调度与贪心调度定理

27.4 多线程矩阵乘法（§27.2）

27.5 多线程归并排序（§27.3）

27.6 实际考量与局限

三、关键图表

四、思维导图

五、重点与易错点

第 27 章多线程算法 (Multithreaded Algorithms)