动态多线程

概述

动态多线程（Dynamic Multithreading）是一种并行计算模型，通过 spawn（生成并行子任务）和 sync（等待子任务完成）两个关键字来表达算法中的并行性。其性能由三个关键指标刻画：work（总操作数）、span（最长依赖链/关键路径长度）和parallelism（并行度 = work/span）。

定义

动态多线程（Dynamic Multithreading）

动态多线程模型使用伪指令扩展串行模型：

• spawn：生成一个并行子线程，父线程可与子线程并行执行
• sync：等待所有通过 spawn 生成的子线程完成后再继续

算法的并行性由计算有向无环图（computation DAG）表示：

• 每个顶点代表一个strand（连续的非并行指令序列）
• 边代表 strand 之间的依赖关系（先后顺序）

性能指标

设计算 DAG 为 $G$，则：

• Work $T_1$：所有 strand 的执行时间之和（在单处理器上的运行时间）
• Span $T_{\infty }$：DAG 中最长路径（关键路径）的长度（在无限处理器上的运行时间）
• Parallelism $T_1/T_{\infty }$：理论最大加速比的上界

在 $P$ 个处理器上的运行时间 $T_P$ 满足：

$T_{\infty }\le T_P\le T_1/P+T_{\infty }$

核心性质

指标	符号	含义	理想目标
Work	$T_1$	总操作数	尽量接近最优串行算法
Span	$T_{\infty }$	最长依赖链	尽量短，决定并行加速上限
Parallelism	$T_1/T_{\infty }$	并行度	越大越好，理想 $\gg P$
Speedup	$T_1/T_P$	实际加速比	越接近 $P$ 越好

应用场景

• 并行归并排序：$T_1=\Theta (n\log n)$，$T_{\infty }=\Theta (n)$，并行度 $\Theta (\log n)$
• 并行矩阵乘法：$T_1=\Theta (n^3)$，$T_{\infty }=\Theta ({\log }^{2}n)$（递归分块），并行度 $\Theta (n^3/{\log }^{2}n)$
• 并行 FFT：$T_1=\Theta (n\log n)$，$T_{\infty }=\Theta (\log n)$，并行度 $\Theta (n)$
• 并行前缀和：$T_1=\Theta (n)$，$T_{\infty }=\Theta (\log n)$，并行度 $\Theta (n/\log n)$

参见

• 分治法 — 动态多线程的核心基础，分治天然适合并行化
• 归并排序 — 并行归并排序的详细分析
• 前缀和 — 并行前缀和（扫描算法）
• 矩阵乘法 — 并行矩阵乘法
• 多项式乘法 — 并行 FFT