《Programming Massively Parallel Processors》第四版 - 学习笔记与练习
注意：本章是理论总结章节，讨论并行编程的思维方法和设计原则，无代码练习。
本章介绍并行编程的核心思维方式：
- 计算思维（Computational Thinking）的定义与重要性
- 问题分解策略：任务并行 vs 数据并行
- 并行算法设计模式：Map、Reduce、Scan、Stencil、Gather、Scatter
- 性能优化框架：Roofline 模型、瓶颈分析
- 可扩展性分析：Amdahl 定律 vs Gustafson 定律
- 调试与验证策略
- 跨平台思维与持续学习
相关博客笔记：第十九章：并行编程与计算思维
用计算机科学的基本概念来解决问题、设计系统、理解人类行为。
在并行计算语境下：
- 识别问题的并行性
- 分解任务与数据
- 设计高效的通信模式
- 权衡各种资源约束
| 策略 | 描述 | 适用场景 |
|---|---|---|
| 任务并行 | 不同处理器执行不同任务 | 异构任务、流水线 |
| 数据并行 | 相同操作应用到不同数据 | 向量运算、矩阵乘法 |
| 输出驱动 | 每线程负责一个输出元素 | 矩阵乘法、图像滤波 |
| 输入驱动 | 每线程处理一个输入元素 | 直方图、归约 |
| 模式 | 描述 | 示例 |
|---|---|---|
| Map | 一对一变换 | ReLU、标量乘法 |
| Reduce | 多对一聚合 | 求和、最大值 |
| Scan | 前缀操作 | 流压缩、基数排序 |
| Stencil | 邻域模式 | 卷积、PDE 求解 |
| Gather | 间接读取 | 查表、稀疏访问 |
| Scatter | 间接写入 | 直方图、排序分桶 |
模式组合示例：
- 基数排序 = Histogram + Scan + Scatter
- 稀疏矩阵-向量乘 = Gather + Reduce
- BFS = Gather + Scatter + Reduce
性能 = min(峰值算力, 带宽 × 算术强度)
| 算术强度 | 瓶颈类型 | 优化方向 |
|---|---|---|
| < 10 | 内存受限 | 提高数据复用 |
| > 10 | 计算受限 | 优化计算效率 |
Amdahl 定律（强扩展）：
- P：可并行部分比例
- N：处理器数
- 串行部分决定加速上限
Gustafson 定律（弱扩展）：
- 增大问题规模可提高并行效率
- 理解硬件：了解 GPU 架构，扬长避短
- 数据为王：性能通常受限于数据移动
- 最大化并行：暴露足够并行性隐藏延迟
- 最小化同步：同步是性能杀手
- 合并访问：让内存访问连续
- 复用数据：共享内存是最好的朋友
- 避免发散：让 Warp 内线程走相同路径
- 权衡取舍：没有银弹，只有适合的解
- Profile 优先：数据驱动优化，不要猜测
- 渐进迭代：先正确，后优化，持续改进
┌─────────────────────────────────────────┐
│ 第四层：算法层 │
│ 选择更高效的算法、减少总操作数 │
├─────────────────────────────────────────┤
│ 第三层：并行策略层 │
│ 任务分解方式、负载均衡 │
├─────────────────────────────────────────┤
│ 第二层：内存层 │
│ 全局/共享/寄存器使用、访问模式优化 │
├─────────────────────────────────────────┤
│ 第一层：指令层 │
│ 循环展开、指令级并行 │
└─────────────────────────────────────────┘
从上往下优化：算法级改进的收益最大。
- 简化问题：先在小规模数据上测试
- 串行参考：保留 CPU 版本用于验证
- 使用工具：cuda-memcheck、Nsight Compute
- 渐进开发：先正确，后优化
Chapter19/
└── README.md # 本文档（理论章节，无代码）
本章为理论章节，无需编译运行。
- PMPP 第四版 Chapter 19
- GitHub参考仓库（空占位符）
- 第十九章：并行编程与计算思维
学习愉快！ 🎓
- Wing, J. M. (2006). Computational Thinking. Communications of the ACM.
- Williams, S., et al. (2009). Roofline: An Insightful Visual Performance Model.