并行算法模式：Map、Reduce、Scan、Stencil 与任务图 / Parallel Patterns: Map, Reduce, Scan, Stencil, and Task Graphs

📅 创建时间：2026-07-20 🏷️ 标签：#并行算法 #MapReduce #Scan #Stencil #任务图 📚 前置知识：[[06-cuda-programming-model]]

---

1. 为什么学习模式而不是死记 API

OpenMP、CUDA、TBB、MPI 和各种计算框架的 API 不同，但底层问题反复出现。识别并行模式，可以把新问题映射到成熟算法结构。

---

2. Map：独立地变换每个元素

[x0, x1, x2, x3] → [f(x0), f(x1), f(x2), f(x3)]

典型场景：

• 图像像素变换
• 向量激活函数
• 数据格式转换
• 蒙特卡洛样本计算

Map 几乎没有线程间通信，是最容易并行化的模式。

---

3. Reduce：把大量元素归并成少量结果

[a b c d e f g h]
  ↓ 两两合并
[ab  cd  ef  gh]
  ↓
[abcd    efgh]
  ↓
[abcdefgh]

求和、最大值、直方图统计都属于归约。

串行累加存在长依赖链；树形归约把深度从 O(n) 降为 O(log n)。浮点加法不满足严格结合律，所以并行归约结果可能与串行结果有微小差异。

---

4. Scan：保留所有前缀结果

输入：

[3, 1, 4, 2]

包含式前缀和：

[3, 4, 8, 10]

Scan 是压缩、流紧缩、排序、图算法和 GPU 内存分配中的基础原语。高效并行 Scan 通常包含向上归约和向下传播两个阶段。

---

5. Stencil：邻域计算

new[i,j] = f(old[i,j], old[i-1,j], old[i+1,j],
             old[i,j-1], old[i,j+1])

典型场景：

• 有限差分
• 图像卷积
• 热传导模拟
• 流体计算

Stencil 的重点不是算术表达式，而是邻域数据复用和边界交换。单机使用 Cache/Shared Memory 分块，多机使用 Halo Exchange。

---

6. Gather 与 Scatter

Gather

从不连续位置读取数据：

output[i] = input[index[i]]

Scatter

向不连续位置写入数据：

output[index[i]] = input[i]

Scatter 可能产生多个线程写同一位置的冲突，需要原子操作、排序或重新设计数据布局。

---

7. 分区、排序与负载均衡

不规则问题通常先进行分区：

• 按空间划分网格
• 按顶点划分图
• 按非零元素划分稀疏矩阵
• 按预计耗时划分任务

好的分区同时追求：

各分区计算量接近 + 分区之间通信量较少

两者经常冲突，需要根据应用权衡。

---

8. Pipeline：不同阶段并行

读取 → 解码 → 预处理 → 推理 → 后处理 → 写出

当不同阶段能够处理不同批次时，可以形成流水线：

时刻 1：读取 A
时刻 2：解码 A，读取 B
时刻 3：推理 A，解码 B，读取 C

流水线吞吐由最慢阶段决定，阶段之间还需要缓冲区和背压机制。

---

9. Task Graph：用依赖描述执行

复杂应用可表示为有向无环图 DAG：

A ─┬→ C → E
   └→ D ─┘
B ─────→ D

运行时在依赖满足后调度任务，适合：

• 编译系统
• 渲染引擎
• 多物理场仿真
• AI 计算图
• 异构 CPU-GPU 工作流

任务图比手工创建线程更容易表达复杂依赖和动态调度。

---

10. Map 工程边界

Map 迭代独立，但仍需检查：

• 输入输出别名；
• 异常；
• 分支；
• 数据布局；
• 尾部；
• 向量化；
• GPU 索引；
• 输出顺序。

11. Reduce 工程边界

Reduction 操作最好满足结合性。

浮点加法只近似结合。

局部累加、树形合并和补偿求和提供不同精度与成本。

12. Scan 实现阶段

典型 Scan 分为局部 Scan、Block Sum Scan 和偏移回写。

local scans
  -> scan block totals
  -> add block offsets

需要处理非整块输入和 In-place 语义。

13. Stencil 边界

Stencil 需要：

• Halo；
• Boundary Condition；
• Tile；
• 时间步；
• 双缓冲；
• Cache/Shared Memory；
• 多节点交换。

原地更新可能改变算法语义。

14. Histogram

Histogram 具有热点写和原子竞争。

候选方案：

• 线程私有；
• Block 私有；
• 分片桶；
• 两阶段合并；
• 排序后计数。

桶数量和数据倾斜决定选择。

15. Gather

Gather 是不规则读取。

优化方向：

• 重排索引；
• 压缩索引；
• Cache Blocking；
• 批处理；
• 预取；
• 分区。

16. Scatter

Scatter 是不规则写入。

需要处理冲突：

• 原子；
• 图着色；
• 排序；
• 私有缓冲；
• Owner Partition；
• 两阶段提交。

17. Compaction

过滤标记加 Scan 生成输出位置。

predicate -> flags -> scan -> scatter selected items

它是多个基础模式的组合。

18. Sort

并行排序选择依赖 Key、稳定性、分布和内存。

Radix、Merge、Sample Sort 和分布式排序有不同约束。

数据倾斜会破坏分区均衡。

19. Pipeline 背压

阶段间使用有界队列。

最慢阶段限制吞吐。

批量提高吞吐，也增加延迟和内存。

20. Task Graph 调度

Task Graph 需要：

• Ready Queue；
• 依赖计数；
• 优先级；
• Work Stealing；
• 取消；
• 错误传播；
• 资源约束；
• 关键路径。

任务过细时运行时开销主导。

21. 模式组合

真实系统组合模式：

Pipeline
  -> Map preprocessing
  -> Stencil / Compute
  -> Reduce metrics
  -> Compact output

组合边界决定数据移动和同步。

22. CPU 映射

SIMD、线程池、OpenMP 和任务图是常见实现。

关注 Cache、False Sharing、NUMA 和调度。

23. GPU 映射

关注 Grid、Warp、合并访问、Shared Memory、原子和 Kernel 启动。

24. MPI 映射

模式跨节点时需要分区、Halo、Collective 和拓扑。

25. 正确性

验证：

• 串行参考；
• 边界；
• 冲突；
• 浮点容差；
• 顺序要求；
• 取消；
• 部分失败；
• 资源释放。

26. Profile

记录：

• 每阶段时间；
• 字节；
• 同步；
• 原子；
• 队列；
• 不均衡；
• 通信；
• 正确性。

27. 选择模式的检查表

问题特征	优先考虑
每个元素独立处理	Map
汇总为一个或少量结果	Reduce
需要全部前缀状态	Scan
依赖邻域数据	Stencil
多个阶段持续处理数据	Pipeline
存在复杂任务依赖	Task Graph
数据访问由索引决定	Gather / Scatter

下一篇：[[08-heterogeneous-computing]]