Skip to content
Gains Summary
Main Navigation 首页 / Home
C++ 编程 / C++ Programming
系统与高性能 / Systems & Performance
Web 开发 / Web Development
人工智能 / Artificial Intelligence
工业软件 / Industrial Software
其他内容 / Other Topics
C++ 编程 / C++系统与性能 / SystemsWeb 开发 / Web人工智能 / AI工业软件 / Industrial

外观

Sidebar Navigation

← 系统与高性能 / Systems & Performance

计算系统 / Computing Systems

1. 计算系统：计算机如何执行与加速程序

2. 从 C++ 源码到 CPU 执行

3. CPU 流水线、乱序执行与分支预测

4. Cache、一致性、伪共享与 NUMA

5. GPU、SM、Warp 与显存

6. 计算执行模型：程序怎样映射到机器

7. SIMD 与编译器向量化

8. C++ 多线程与 OpenMP

9. CUDA 平台与编程模型

10. CUDA Kernel、内存与性能

11. CPU-GPU 异构流水线

12. MPI 与分布式并行

13. 并行算法模式

14. 性能模型与工具

15. 递进学习项目：从单线程到集群

历史完整正文 / Original Deep Dives

1. 历史完整正文：统一前文章逐篇保留

原体系结构与硬件 / Original Architecture

1. 硬件编程与高性能计算：一张可走通的学习地图 / A Practical Learning Map for Hardware Programming and HPC

2. 计算机体系结构：CPU、内存与 GPU / Computer Architecture: CPUs, Memory, and GPUs

3. 计算机架构基础——为什么 GPU 比 CPU 更快 / Computer Architecture Fundamentals: Why GPUs Outperform CPUs

4. 并行计算理论——30 天训练能优化到多快？ / Parallel Computing Theory and the Limits of Training Acceleration

5. GPU 架构深入——上万个核心如何分工协作 / GPU Architecture and Massive Parallel Execution

6. CUDA 编程模型——把矩阵乘法映射到 GPU / The CUDA Programming Model for Mapping Matrix Multiplication to GPUs

7. CUDA 内存管理——百亿参数如何装进显存 / CUDA Memory Management for Large Models

8. CUDA 性能优化——从 30 天缩短到 10 天 / CUDA Performance Optimization

9. CPU 并行编程——OpenMP 与 SIMD 向量化 / CPU Parallel Programming with OpenMP and SIMD

10. HPC 集群与 MPI——多节点分布式训练 / HPC Clusters and MPI for Distributed Training

11. 异构计算——CPU 与 GPU 如何协同工作 / Heterogeneous Computing with CPUs and GPUs

12. 深度学习训练优化实战——从 30 天到 3 天 / Deep Learning Training Optimization from Thirty Days to Three

13. 性能分析工具——找到真正的瓶颈 / Performance Analysis Tools for Finding Real Bottlenecks

14. NPU 全景——昇腾/寒武纪/TPU/苹果生态 / The NPU Landscape: Ascend, Cambricon, TPU, and Apple

15. 未来趋势——2030 年的计算机会是什么形态 / Future Computing Trends Toward 2030

16. 硬件与高性能计算：从“程序为什么慢”开始 / Hardware and HPC Starting from Why Programs Are Slow

原并行计算 / Original Parallel Computing

1. 并行计算：从 SIMD 到 MPI / Parallel Computing from SIMD to MPI

2. 并行计算全景：从晶体管、CPU、GPU 到计算集群 / Parallel Computing from Transistors, CPUs, and GPUs to Clusters

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

4. 处理器体系结构：从指令流水线到多核芯片 / Processor Architecture from Instruction Pipelines to Multicore Chips

5. CPU 并行：多线程、SIMD、Cache 一致性与 NUMA / CPU Parallelism with Threads, SIMD, Cache Coherence, and NUMA

6. 内存层次：Cache、带宽、局部性与一致性 / Memory Hierarchies, Bandwidth, Locality, and Coherence

7. GPU 体系结构：SIMT、Warp、SM 与吞吐优先设计 / GPU Architecture with SIMT, Warps, and Streaming Multiprocessors

8. CUDA 编程模型：Thread、Block、Grid 与内存协作 / CUDA Threads, Blocks, Grids, and Cooperative Memory Access

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

10. 异构计算：CPU、GPU、NPU 如何协同工作 / Heterogeneous Computing with CPUs, GPUs, and NPUs

11. 分布式并行：MPI、集合通信、RDMA 与多机多卡 / Distributed Parallelism with MPI, Collective Communication, and RDMA

12. 性能工程：测量、Roofline、瓶颈定位与优化闭环 / Performance Engineering with Measurement, Roofline, and Bottleneck Analysis

13. 并行计算实战：AI、CAE、图像与科学计算 / Parallel Computing for AI, CAE, Imaging, and Scientific Computing

14. 并行计算实践路线：从单核优化到多机多卡 / A Parallel Computing Project Path from Single-Core to Multi-Node GPUs

本页目录

并行算法模式：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：独立地变换每个元素 ​

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

典型场景：

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

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

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

text
[a b c d e f g h]
  ↓ 两两合并
[ab  cd  ef  gh]
  ↓
[abcd    efgh]
  ↓
[abcdefgh]
1
2
3
4
5
6
7

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

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

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

输入：

text
[3, 1, 4, 2]
1

包含式前缀和：

text
[3, 4, 8, 10]
1

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

5. Stencil：邻域计算 ​

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

典型场景：

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

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

6. Gather 与 Scatter ​

Gather ​

从不连续位置读取数据：

text
output[i] = input[index[i]]
1

Scatter ​

向不连续位置写入数据：

text
output[index[i]] = input[i]
1

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

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

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

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

好的分区同时追求：

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

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

8. Pipeline：不同阶段并行 ​

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

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

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

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

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

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

text
A ─┬→ C → E
   └→ D ─┘
B ─────→ D
1
2
3

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

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

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

历史模式补充 ​

本页保留合并前的并行模式说明。

当前版本增加工程边界、模式组合和验证方法。

Map ​

迭代独立，适合 SIMD、线程和 GPU。

检查别名、分支、尾部和输出顺序。

Reduce ​

局部结果树形合并。

浮点顺序需要容差或稳定算法。

Scan ​

通过局部 Scan、Block Sum 和 Offset 回写并行。

处理非整块和 In-place 语义。

Stencil ​

访问规则邻域。

关注 Tile、Halo、边界和双缓冲。

Histogram ​

热点桶造成原子竞争。

私有 Histogram 再合并是常见方案。

Gather ​

不规则读取受 Cache 和延迟限制。

重排和分区可能改善局部性。

Scatter ​

不规则写入需要冲突协议。

原子、着色、排序和私有缓冲是候选方案。

Compaction ​

Predicate、Scan 和 Scatter 组合生成紧凑输出。

Sort ​

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

Pipeline ​

不同阶段处理不同批次。

最慢阶段限制吞吐，有界队列提供背压。

Task Graph ​

显式依赖驱动 Ready Task。

运行时管理队列、偷取、取消和错误。

模式组合 ​

真实应用常组合 Map、Stencil、Reduce、Compact 和 Pipeline。

边界决定数据移动。

CPU 映射 ​

关注 SIMD、线程池、Cache、NUMA 和 False Sharing。

GPU 映射 ​

关注 Warp、Shared Memory、原子、访存和启动。

MPI 映射 ​

关注分区、Halo、Collective 和拓扑。

粒度 ​

细粒度增加调度。

粗粒度降低并行度和均衡。

负载均衡 ​

比较任务成本而非只比较数量。

正确性 ​

  • 串行参考；
  • 边界；
  • 冲突；
  • 浮点；
  • 顺序；
  • 取消；
  • 失败。

Profile ​

记录阶段、字节、同步、原子、队列、通信和不均衡。

历史版本边界 ​

运行库、GPU 架构和 MPI 实现会改变最优方案。

旧阈值必须重新测量。

当前课程映射 ​

当前文章补充：

  • Map/Reduce 工程边界；
  • Scan 阶段；
  • Histogram；
  • Compaction；
  • Sort；
  • Pipeline 背压；
  • Task Graph 调度；
  • 模式组合；
  • 正确性与 Profile。

阅读完成标准 ​

应能：

  • 识别模式；
  • 处理冲突；
  • 设计粒度；
  • 组合模式；
  • 映射 CPU/GPU/MPI；
  • 验证正确性；
  • Profile 数据流；
  • 限定历史结论。

归档实验记录 ​

  • 来源提交；
  • 模式名称；
  • 串行参考；
  • 输入规模；
  • 数据分布；
  • 分区；
  • 粒度；
  • CPU/GPU/MPI；
  • 线程或 Rank；
  • 内存布局；
  • 通信；
  • 同步；
  • 原子冲突；
  • Profile；
  • 原始样本；
  • 正确性；
  • 当前结果差异。

模式比较必须使用相同语义和输入。 无法复现旧环境时，保留原结果并说明替代平台。 模式名称相同不代表实现成本相同。 最终选型仍以当前端到端测量为准。 失败方案也应记录原因。 这样可以避免重复无效实验。

10. 选择模式的检查表 ​

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

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

最后更新于:

Pager
上一篇8. CUDA 编程模型：Thread、Block、Grid 与内存协作 / CUDA Threads, Blocks, Grids, and Cooperative Memory Access
下一篇10. 异构计算：CPU、GPU、NPU 如何协同工作 / Heterogeneous Computing with CPUs, GPUs, and NPUs

持续记录，持续成长

Copyright © Tidenflow