并行算法模式
API 会变化，模式更稳定。先辨认数据依赖形状，再决定使用线程、GPU 还是进程。
1. Map：逐元素独立变换
[x0 x1 x2 x3] -> f on each -> [y0 y1 y2 y3]最容易并行：SIMD、OpenMP parallel for、CUDA 一线程一元素都可表达。关键是访问连续、工作量均衡、避免共享写入。
2. Reduce：多值归一
求和、最大值、直方图合并都属于归约。串行左折叠有依赖，并行实现使用树形合并：
a b c d e f g h
\ / \ / \ / \ /
ab cd ef gh
\ / \ /
abcd efgh
\ /
result操作需满足适当结合性；浮点加法数学上近似结合但机器舍入使不同合并顺序产生细微差异。不要在每个元素上争抢一个全局锁/原子，优先分层局部归约。
3. Scan：前缀计算
输入 [a,b,c,d] 的 inclusive sum 是 [a,a+b,a+b+c,a+b+c+d]。Scan 表面有前后依赖，但可通过上扫/下扫等树形算法并行，是流压缩、排序和索引构建的基础。
4. Stencil：邻域更新
每个网格点读取邻居并写下一时间步。适合分块、Halo 交换、Shared Memory 复用：
old grid -- read neighbors --> new grid通常使用双缓冲，避免同一轮既读又覆盖导致竞态。跨 MPI 域需要交换 Halo，GPU 内则关注 Tile 边界与复用收益。
5. Pipeline：阶段重叠
input -> decode -> compute -> encode -> output不同数据项同时位于不同阶段，提高吞吐。总体吞吐由最慢阶段限制；队列太小导致饥饿，太大增加内存与尾延迟，需要背压。
6. Task Graph：不规则依赖
A ---> C ---> E
\-> B -> D -^节点是任务，边是依赖。线程池、OpenMP task、CUDA Graph 等可减少手工线程管理，但图粒度过细会被调度开销吞没。
7. 模式与平台不是一一对应
| 模式 | CPU | GPU | 分布式 |
|---|---|---|---|
| Map | SIMD / OpenMP | Kernel | 分片后本地 Map |
| Reduce | 线程局部 + 树合并 | Block/Grid 分层 | MPI Reduce/Allreduce |
| Stencil | Cache blocking | Shared Memory tile | 域分解 + Halo |
| Pipeline | 队列/线程池 | Streams | 节点间流水 |
深入原理与工程实践
前面的内容负责建立统一心智模型；下面把同一主题继续拆到执行过程、代码、性能代价与工程判断。
<!-- migrated-deep-dive:start -->
完整迁入：原并行算法模式全文
并行算法模式：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 |
| 汇总为一个或少量结果 | Reduce |
| 需要全部前缀状态 | Scan |
| 依赖邻域数据 | Stencil |
| 多个阶段持续处理数据 | Pipeline |
| 存在复杂任务依赖 | Task Graph |
| 数据访问由索引决定 | Gather / Scatter |
下一篇：[[08-heterogeneous-computing]]
完整迁入：原并行计算应用案例
并行计算实战：AI、CAE、图像与科学计算 / Parallel Computing for AI, CAE, Imaging, and Scientific Computing
📅 创建时间：2026-07-20 🏷️ 标签：#AI训练 #CAE #图像处理 #科学计算 📚 前置知识：[[10-performance-engineering]] 📚 相关知识：[[/04-ai/01-llm-engineering/13-training-infrastructure]] [[/05-industrial-software/01-foundations-and-architecture/03-cae-basics]]
1. AI 训练
核心计算
Transformer 训练的大部分计算来自矩阵乘法和 Attention，适合 GPU/Tensor Core。
系统并行
CPU 数据处理
↓
GPU 前向与反向传播
↓
多 GPU 梯度同步
↓
优化器更新与 Checkpoint主要瓶颈可能是：
- GPU 算力
- HBM 带宽
- 激活和优化器显存
- GPU 间集合通信
- 数据加载和存储
优化手段包括混合精度、算子融合、Activation Checkpoint、数据/张量/流水线并行和通信重叠。
2. AI 推理
推理同时关心吞吐与响应延迟：
- Batching 提高吞吐，但会增加排队延迟
- KV Cache 减少重复计算，但消耗显存
- 量化减少容量和带宽，可能影响精度
- Continuous Batching 提高动态请求利用率
- Speculative Decoding 用额外计算换取更少串行解码步骤
自回归解码存在 Token 间依赖，不能简单把整个序列一次并行生成。
3. CAE 与有限元
典型流程：
网格读取 → 单元计算 → 矩阵组装 → 线性求解 → 后处理单元计算
不同单元可以并行，但向全局矩阵 Scatter 时可能产生写冲突。
稀疏线性求解
稀疏矩阵向量乘法通常算术强度低，容易受内存带宽限制。预条件器和收敛次数会显著影响总时间。
多节点划分
网格分区需要兼顾单元数量和边界规模，边界越大，Halo Exchange 越多。
4. CFD 与规则网格
有限差分和有限体积常使用 Stencil：
- CPU：多线程 + SIMD + Cache 分块
- GPU：Block + Shared Memory Tile
- 集群：空间分区 + Halo Exchange
时间步之间存在依赖，但同一时间步的大量网格点可以并行。
5. 图像与视频处理
像素级滤波天然适合 GPU，但完整流水线还包含：
磁盘/相机输入 → 解码 → 色彩转换 → 滤波 → 编码 → 输出只加速滤波 Kernel 可能无法改善被解码或 I/O 限制的系统。使用硬件编解码、流水线和设备内数据复用通常更重要。
6. 图计算
图算法具有不规则访问和动态工作量：
- 顶点度数差异巨大
- 邻接表访问不连续
- Frontier 大小动态变化
- 原子更新较多
CPU 擅长复杂控制，GPU 仍可通过 Frontier 压缩、负载分配和批处理获得高吞吐，但优化难度高于规则矩阵计算。
7. 数据库与数据分析
并行技术应用于：
- 分区扫描
- Hash Join
- 聚合与排序
- SIMD 向量化执行
- 多核查询调度
- GPU 数据库算子
列式存储提高连续访问和压缩效率，也更适合向量化。查询执行计划决定并行是否真正减少总工作量。
8. 领域选型表
| 场景 | 主要并行方式 | 常见瓶颈 |
|---|---|---|
| LLM 训练 | GPU + 多卡集合通信 | 算力、显存、网络 |
| LLM 推理 | Batching + GPU Kernel | HBM、KV Cache、延迟 |
| 有限元 | CPU/GPU + MPI | 稀疏访存、通信 |
| CFD | Stencil + 空间分区 | 带宽、Halo Exchange |
| 图像视频 | GPU + Pipeline | 传输、编解码 |
| 图计算 | 动态任务并行 | 随机访存、负载不均 |
| 数据分析 | SIMD + 多核分区 | 内存带宽、数据倾斜 |
核心总结
- 领域算法决定并行模式，不能从硬件型号反推算法。
- 规则密集计算更容易利用 GPU，不规则任务更依赖调度和数据结构。
- 端到端系统常包含 CPU、GPU、网络和存储的组合瓶颈。
- AI 与 CAE 都会同时遇到计算、容量和通信问题。
下一篇：[[12-learning-projects]]
完整迁入：原并行计算全景
并行计算全景：从晶体管、CPU、GPU 到计算集群 / Parallel Computing from Transistors, CPUs, and GPUs to Clusters
📅 创建时间：2026-07-20 🏷️ 标签：#并行计算 #计算机体系结构 #CPU #GPU #HPC 📚 前置知识：基本编程经验；了解 C/C++ 数组、指针和线程会更顺畅 📚 相关知识：[[/02-systems-and-performance/02-computer-architecture-and-hardware/00-hardware-overview]] [[/01-cpp/06-concurrency/04-concurrency]] [[/04-ai/01-llm-engineering/09-transformer-training-computation]]
文档目标
并行计算不是“多开几个线程”，而是一套横跨算法、编程模型、体系结构和硬件系统的完整方法论。
这套专题围绕一个核心问题展开：
当单个计算单元已经无法继续明显提速时，怎样让更多计算单元协同工作，并让数据及时到达它们手中？
学完后你应该能够：
- 区分并发、并行、分布式计算与异构计算
- 理解 CPU 多核、SIMD、GPU SIMT 和集群的差异
- 判断任务是否可以拆分，以及理论加速上限
- 解释 Cache、NUMA、显存和网络为什么决定真实性能
- 使用 OpenMP、CUDA 和 MPI 描述不同层级的并行
- 用 Speedup、Efficiency、Roofline 等模型分析瓶颈
- 为 AI、CAE、图像处理和科学计算选择合理架构
一张图理解整个专题
应用问题
│
├─ 能不能拆？ → 任务依赖、数据依赖、Amdahl 定律
│
├─ 在一个核心里怎样并行？ → 指令流水线、乱序执行、SIMD
│
├─ 在一颗 CPU 里怎样并行？ → 多核、线程、Cache 一致性、NUMA
│
├─ 在一张 GPU 里怎样并行？ → SIMT、Warp、SM、显存层次
│
├─ CPU 和 GPU 怎样协作？ → 异构计算、数据传输、任务流水线
│
├─ 一台机器不够怎么办？ → MPI、集合通信、RDMA、多机多卡
│
└─ 为什么没有变快？ → 测量、Roofline、负载均衡、通信开销并行系统的性能可以粗略写成：
总时间 = 有效计算 + 数据移动 + 同步等待 + 调度开销增加核心只会减少其中一部分。很多程序最终受限于数据移动和等待，而不是算术运算。
课程路线
| 阶段 | 文档 | 核心问题 |
|---|---|---|
| 建立直觉 | 01 基础概念与性能模型 | 为什么并行、最多能快多少？ |
| 硬件基础 | 02 处理器体系结构 | 指令在处理器里怎样执行？ |
| CPU 并行 | 03 多核、SIMD 与 NUMA | CPU 怎样同时完成不同工作？ |
| 内存系统 | 04 Cache、一致性与数据局部性 | 为什么访存经常比计算更贵？ |
| GPU 架构 | 05 GPU 与 SIMT | GPU 为什么适合海量规则任务？ |
| GPU 编程 | 06 CUDA 执行与内存模型 | Thread、Block、Grid 怎样映射硬件？ |
| 算法设计 | 07 并行模式与算法 | Reduction、Scan、Stencil 怎样设计？ |
| 单机异构 | 08 CPU-GPU 协同 | 任务和数据应该放在哪里？ |
| 集群并行 | 09 MPI、网络与集合通信 | 多台机器怎样交换数据？ |
| 工程优化 | 10 性能分析与 Roofline | 瓶颈究竟在哪里？ |
| 真实应用 | 11 AI、CAE 与科学计算 | 不同领域怎样组合这些技术？ |
| 实践路线 | 12 项目与实验 | 怎样从零建立并行工程能力？ |
推荐按编号顺序阅读。已经掌握计算机组成原理的读者，可以从 03 开始；已有 CUDA 经验的读者，也不建议跳过 01、04 和 10。
四种容易混淆的概念
并发
多个任务在一段时间内都获得执行机会，不保证同一时刻真正执行。单核操作系统也能并发。
并行
多个计算单元在同一时刻执行多个操作。多核 CPU、GPU 和多机集群都属于并行系统。
分布式计算
计算单元拥有独立内存，通过网络通信。重点是节点自治、通信和故障处理。
异构计算
系统中存在不同特性的处理器，例如 CPU、GPU、NPU 和 FPGA，由它们分别处理擅长的任务。
贯穿课程的三个案例
案例一：向量相加
for (int i = 0; i < n; ++i) {
c[i] = a[i] + b[i];
}循环之间互不依赖，适合 SIMD、多线程和 GPU，但算术强度低，通常受内存带宽限制。
案例二：矩阵乘法
C[i,j] = Σ A[i,k] × B[k,j]计算量大、数据可以复用，是 Cache 分块、向量化和 GPU Tensor Core 的经典场景。
案例三：大模型训练
模型训练同时涉及：
- GPU 内部的张量并行计算
- 单机多卡的高速互联
- 多机之间的梯度同步
- CPU 数据预处理和 I/O
- 显存容量、通信与计算重叠
它是现代并行计算各层技术的综合实例。
学习原则
- 先判断依赖，再决定如何拆分。
- 先测量瓶颈，再进行优化。
- 把数据移动视为一级成本。
- 同时考虑延迟、吞吐、容量和能耗。
- 优先使用成熟库，理解底层是为了正确选型和排障。
核心总结
- 并行性能由算法、硬件、内存和通信共同决定。
- CPU 擅长复杂控制与低延迟，GPU 擅长规则、高吞吐的数据并行。
- 从单核到集群，通信范围越来越大，代价也越来越高。
- 并行优化的本质，是让计算单元持续获得足够的数据和可执行工作。
下一篇：[[01-parallel-foundations]] <!-- migrated-deep-dive:end -->
面试速答
Reduce 为什么适合树形并行？ 独立局部结果可分层合并，关键路径由线性长度降到对数层数，同时减少全局争用。
Stencil 为什么常用双缓冲？ 本轮所有输出都应基于同一旧状态；分离读写缓冲可避免更新顺序改变结果和数据竞争。
自测
- 并行 Map 一定无竞争吗？
- 浮点并行归约为何可能与串行结果不逐位相同？
- Pipeline 为何不能让单个数据项延迟无限降低？
答案：不一定，输出别名或共享副作用仍会竞争；合并顺序改变舍入；流水主要提升吞吐且还增加排队与阶段开销。