并行计算基础：任务分解、加速比与可扩展性 / Parallel Computing Fundamentals: Decomposition, Speedup, and Scalability

📅 创建时间：2026-07-20 🏷️ 标签：#并行计算 #Amdahl定律 #Gustafson定律 #性能模型 📚 前置知识：[[00-parallel-computing-overview]] 📚 相关知识：[[/02-systems-and-performance/02-computer-architecture-and-hardware/02-parallel-computing-theory]]

---

1. 并行之前先判断“能否拆分”

假设程序由以下步骤组成：

读取数据 → 预处理 → 核心计算 → 汇总结果 → 写入文件

只有相互独立的部分能够同时执行。任务之间常见依赖包括：

• 数据依赖：后一步需要前一步的结果
• 控制依赖：是否执行由前一步判断决定
• 资源依赖：多个任务竞争同一文件、锁或设备

数据并行与任务并行

数据并行：同一种操作处理不同数据
例：多个线程分别处理图像的不同行

任务并行：不同任务同时处理同一流程的不同阶段
例：一个线程读取、一个线程解码、一个线程推理

GPU 主要擅长数据并行，CPU 更容易同时承载数据并行和任务并行。

---

2. 衡量并行性能

加速比

S(p) = T(1) / T(p)

如果单线程需要 100 秒，8 线程需要 20 秒，则加速比为 5，而不是 8。

并行效率

E(p) = S(p) / p

上例的并行效率是 5 / 8 = 62.5%。剩余能力消耗在串行部分、同步、调度和负载不均上。

吞吐与延迟

• 延迟：完成单个任务需要多久
• 吞吐：单位时间能完成多少任务

GPU 往往提高吞吐，但单个小任务不一定比 CPU 延迟更低。

---

3. Amdahl 定律：固定问题规模的上限

如果程序中可并行比例为 P，使用 N 个处理器：

S(N) = 1 / ((1 - P) + P / N)

当 95% 可以并行时，即使处理器无限多：

最大加速比 = 1 / (1 - 0.95) = 20

这说明优化串行路径可能比继续增加核心更重要。

可并行比例	理论最大加速比
50%	2 倍
90%	10 倍
95%	20 倍
99%	100 倍

---

4. Gustafson 定律：问题规模也会增长

现实中获得更多计算资源后，通常不是只想更快完成原问题，而是希望处理更大的网格、更高分辨率或更大的模型。

S(N) = N - α(N - 1)

其中 α 是串行部分比例。Gustafson 定律解释了为什么超级计算机仍然有价值：资源增加后，可以扩大并行工作规模。

---

5. 强扩展与弱扩展

强扩展

保持总问题规模不变，增加处理器数量。

固定 1 亿个网格单元：1 核 → 8 核 → 64 核

处理器越多，每个处理器分到的工作越少，通信占比最终会上升。

弱扩展

每个处理器的工作量保持不变，处理器增加时同步扩大问题规模。

每核处理 100 万个网格单元：1 核 100 万 → 64 核 6400 万

弱扩展更能反映大型科学计算系统的容量能力。

---

6. 粒度、调度与负载均衡

并行粒度

• 粗粒度：任务大、调度少，但可能不均衡
• 细粒度：任务均衡机会多，但调度和同步成本高

任务耗时只有几百纳秒时，放进线程池可能比直接执行更慢。

静态调度与动态调度

• 静态调度：提前分工，开销低，适合任务耗时相近
• 动态调度：运行时领取任务，均衡好，但有额外竞争

负载不均衡

线程 A：100 ms
线程 B：102 ms
线程 C：98 ms
线程 D：300 ms  ← 所有人都要等它

并行阶段耗时由最慢参与者决定。

---

7. 同步不是免费的

互斥锁、原子操作、Barrier 和消息通信都会带来等待。常见优化方向：

• 减少共享可变状态
• 批量处理，降低同步频率
• 使用线程局部数据，最后统一归并
• 让通信与计算重叠
• 通过无锁结构降低阻塞，但不要默认无锁一定更快

---

8. 依赖图

任务和依赖可以表示为 DAG。

    A
   / \
  B   C
  |  / \
  D E   F
   \|  /
    G

只有前置依赖完成的任务才 Ready。

9. Work 与 Span

Work 是所有任务成本之和。

Span 是最长依赖路径。

available parallelism = Work / Span

更多资源不能突破 Span。

10. 真实与伪依赖

真实依赖来自算法数据流。

伪依赖来自共享容器、全局状态或不必要顺序。

线程局部结果再合并可以消除部分伪依赖。

11. 粒度

细粒度增加：

• 创建；
• 入队；
• 原子；
• 调度；
• 同步；
• 消息；
• Kernel 启动。

粗粒度减少任务数并增加尾部。

12. 调度

静态调度适合规则任务。

动态调度适合成本不均。

Work Stealing 让空闲 Worker 从其他队列获取任务。

13. 负载均衡

比较最大、最小和分布，不只看平均。

实体数量相等不代表计算成本相等。

14. 串行区

初始化、提交、I/O、全局锁和最终归约可能串行。

Profile 必须显示串行区占比。

15. 通信

communication = latency + bytes / bandwidth + overhead

小消息关注次数，大消息关注字节和拓扑。

16. 同步范围

同步可以发生在：

• SIMD Lane；
• Warp；
• Block；
• CPU 线程；
• 进程；
• 节点；
• 全局集合通信。

范围越大，成本和尾部风险通常越高。

17. 数据竞争

并发访问同一位置，至少一个写且无同步，会形成数据竞争。

在 C++ 中这可能导致未定义行为。

18. 死锁

多个任务循环等待资源时没有进展。

统一锁顺序、作用域锁和结构化通信降低风险。

19. 活锁与饥饿

活锁中线程持续动作但没有进展。

饥饿中某任务长期得不到资源。

公平性、退避和队列策略需要考虑。

20. 浮点

浮点加法不满足结合律。

并行归约改变顺序。

使用领域容差、稳定归约或更高精度累加。

21. Amdahl

固定问题规模下，串行比例限制最大加速。

真实系统还包含通信和协调。

22. Gustafson

资源增加时扩大问题规模，可能继续利用并行能力。

弱扩展仍受全局操作限制。

23. 强弱扩展

强扩展固定总问题。

弱扩展固定每资源工作。

同时报告时间、效率、通信、内存和正确性。

24. 基线

串行基线应正确且合理优化。

并行算法变化时说明工作量差异。

25. Profile

区分：

• Compute；
• Data Movement；
• Synchronization；
• Queue；
• Idle；
• I/O；
• Imbalance。

26. 最小实验

1. 串行；
2. 两线程；
3. 多线程曲线；
4. 静态/动态调度；
5. 粒度；
6. 线程局部归约；
7. False Sharing；
8. NUMA；
9. 错误和取消；
10. 正确性。

27. 完成标准

应能：

• 画 DAG；
• 算 Work/Span；
• 识别依赖；
• 选择粒度；
• 选择调度；
• 找不均衡；
• 解释同步；
• 验证正确性；
• 测量扩展。

章节测试

1. 为什么 16 核程序通常无法获得 16 倍加速？
2. 图像逐像素处理更接近数据并行还是任务并行？
3. 固定网格规模增加节点属于强扩展还是弱扩展？
4. 为什么任务拆得过细也会降低性能？

参考答案

1. 存在串行部分、同步、调度、访存和负载不均。
2. 数据并行。
3. 强扩展。
4. 调度、通信和同步成本可能超过任务本身。

下一篇：[[02-processor-architecture]]