并行计算模型

概述

并行计算模型（Parallel Computing Model）是描述并行计算的抽象框架，用于设计、分析和比较并行算法。主要模型包括 PRAM（共享内存）、互连网络（消息传递）和动态多线程（CLRS 模型）。关键性能指标包括 work（总操作数）、span（关键路径长度）和并行度（work/span）。这些模型为算法并行化分析提供了理论基础。

定义

Work-Span 模型（动态多线程模型）

CLRS（《算法导论》）采用的动态多线程计算模型，使用两个核心指标刻画并行算法的性能：

• Work（$T_1$）：计算图中所有步骤的总数，等于单处理器串行执行时间
• Span（$T_{\infty }$）：计算依赖图中最长路径的长度，等于无限处理器下的并行执行时间
• 并行度（Parallelism）：$T_1/T_{\infty }$，表示算法能有效利用的最大处理器数

并行执行时间 $T_p$（使用 $p$ 个处理器）满足：

$\max \left(\frac{T_1}{p},T_{\infty }\right)\le T_p\le T_{\infty }+\frac{T_1-T_{\infty }}{p}$

下界由 Brent定理 给出。

三大并行计算模型

模型	通信方式	特点	代表系统
PRAM	共享全局内存	同步执行，理论分析友好	理论模型
互连网络	处理器间消息传递	异步执行，贴近实际硬件	MPI 集群
动态多线程	共享内存 + spawn/sync	支持动态创建并行任务	Cilk, OpenMP

互连网络拓扑：线性阵列、环、网格、超立方体、蝶形网络等，不同拓扑影响通信开销

核心性质

性质	描述
Work 定律	$T_p\ge T_1/p$，$p$ 个处理器至少需要 $T_1/p$ 时间完成所有工作
Span 定律	$T_p\ge T_{\infty }$，并行时间不可能短于关键路径长度
并行度	$T_1/T_{\infty }$ 衡量算法的并行潜力，越大越好
加速比	$S_p=T_1/T_p\le p$，理想加速比为 $p$ 倍
效率	$E_p=S_p/p=T_1/(p\cdot T_p)\le 1$，衡量处理器利用率

Work-Span 分析示例（并行归并排序）：

• Work：$T_1=O(n\log n)$（与串行归并排序相同）
• Span：$T_{\infty }=O({\log }^{2}n)$（递归深度 $\log n$，每层合并需 $O(\log n)$）
• 并行度：$T_1/T_{\infty }=O(n/\log n)$

应用场景

并行计算模型在算法设计与分析中有广泛应用：

• 算法并行化分析：使用 work-span 模型评估串行算法的并行化潜力
• 并行算法设计：在 PRAM 或动态多线程模型上设计高效并行算法
• 性能可移植性：分析算法在不同处理器数上的性能表现（Brent定理）
• 并行复杂性分类：NC 类、P-complete 等复杂性类的定义基于并行计算模型
• 实际系统映射：将理论模型的分析结果映射到实际并行系统（如 GPU、多核 CPU）

参见

• Brent定理 — 有限处理器下并行执行时间的精确上界
• PRAM模型 — 共享内存并行计算的经典理论模型
• BLAS — 并行线性代数计算的标准接口实现
• 缓存优化 — 实际并行系统中缓存层次结构对性能的影响
• 分治算法 — 分治策略是设计并行算法的重要方法