第2章 · 并行编程模型与算法设计
第 2 章 · 并行编程模型与算法设计
章节摘要：硬件有了，怎么在上面写并行程序？这一章讲两件事：一是并行编程模型——MPI（消息传递）、OpenMP（共享内存线程）、CUDA（GPU 异构）三大主流各自的定位和用法；二是并行算法设计——分治、 reductions、数据分布、负载均衡这些把串行算法改造成并行的核心技巧，以及怎么评估通信开销。读完你会知道为不同硬件选什么编程模型，以及怎么把一个串行算法拆成可并行的形式。
本节地图
阅读完本章，你应当能够：
- 区分 MPI、OpenMP、CUDA 三大编程模型的定位和适用场景
- 说清分治并行、reductions、数据分布这些核心算法技巧
- 评估一个并行算法的通信开销
- 把一个简单的串行算法改造成并行版本
核心概念速览
编程模型是"怎么让多个单元协同"，算法设计是"怎么把问题拆成可协同的形式"——两者结合才是完整的并行编程。
本章为什么重要
第 1 章建立了理论地基，但理论本身不会自动变成跑得快的程序。从"知道并行能加速"到"写出一个真正高效的并行程序"，中间隔着两层功夫：一层是编程模型，决定了你用什么接口来表达并行；另一层是算法设计，决定了你的问题怎么被切分成可并行的形式。这两层缺一不可。同一个算法用不同编程模型实现，性能可能差出几个数量级；同一个编程模型跑不同算法，效率曲线的走向也完全不同。
HPC 领域长期并存三大编程模型，它们各有定位，并不互相替代。MPI（消息传递接口）是为分布式内存设计的标准，适合节点之间通过显式消息传递来协同的场景，是超算上多节点作业的事实标准；OpenMP 是共享内存的线程级并行模型，通过编译制导指令就能在单节点多核上展开并行，学习曲线平缓，常用于改造遗留串行代码；CUDA 则是 GPU 异构计算的编程模型，把海量数据并行任务映射到 GPU 的成千上万线程上，单位算力成本远低于 CPU。真实的大规模 HPC 程序往往是三者混合——MPI 负责节点间切分，OpenMP 负责节点内多核，CUDA 负责把热点循环卸载到 GPU。理解这三者的分工和组合方式，是写现代并行程序的前提。
光有编程模型还不够。同一个矩阵乘法，朴素三重循环并行化的效率，和分块、分治后再并行的效率，可以相差十倍以上。原因是并行算法要处理的不仅是计算量，还有数据局部性、通信次数、负载均衡这些底层因素。分治能把大问题切成独立的小块，天然适合并行；reduction 能把分散的中间结果归约成全局结果，但要付出同步开销；数据分布的块状、循环、块循环三种策略，直接影响负载是否均衡和通信是否频繁。本章 2.2 会把这些技巧拆开讲，并给出通信开销的评估方法——很多并行算法的低效，根因不在计算而在通信，能用公式估出通信代价，就拥有了判断算法好坏的依据。
子章节导航
2.1 并行编程模型与语言
讲清 MPI（分布式内存的消息传递）、OpenMP（共享内存的线程级并行）、CUDA（GPU 异构计算）三大模型的机理、典型用法和适用场景，以及它们在 HPC 里的分工。读完要建立的判断是：给定一个任务的特征（数据量、访问模式、节点规模），该选哪个模型，或哪几个模型的组合。
2.2 并行算法设计与优化
拆解分治并行、reductions、数据分布、负载均衡这些把串行算法并行化的核心技巧，给出通信开销的评估方法，并说明稠密计算与稀疏计算的不同并行策略。核心是理解：好算法的标准不是并行度有多高，而是把计算和通信的比例压到对硬件最有利的位置。
子章节之间的逻辑关系
2.1 讲"用什么工具协同"（编程模型），2.2 讲"怎么拆问题让工具发挥"（算法设计）。前者是语法和接口，后者是算法和策略——先掌握编程模型的表达能力，再学怎么用它把并行算法写出来。脱离编程模型空谈算法，会落不到代码；只懂编程模型不懂算法，写出来的程序并行度够但效率堪忧。两者结合，才构成完整的并行编程能力。
2.1 编程模型（工具） ──► 2.2 算法设计（怎么用工具） │ │ └── 掌握接口，再用它表达并行算法 ──┘
阅读建议
如果你有串行编程经验但没碰过并行，建议先从 OpenMP 入手——它的制导指令最接近串行思维，改动几行就能让循环跑在多核上，能快速建立并行的体感。之后再学 MPI，理解显式消息传递带来的开销和灵活性。CUDA 放最后，因为它要求理解 GPU 的硬件模型（线程束、共享内存、全局内存层级），门槛较高。学 2.2 的算法部分时，最好手边有一个正在做的计算任务做对照，把每个技巧往自己的代码上套一遍，比纯看理论有效得多。
前置知识与后续延伸
- 前置知识：读过第 1 章，理解并行理论和体系结构。会基本的 C 或 Fortran 编程，了解指针和内存布局的概念。
- 后续延伸：本章是写并行程序的基础。第 3 章讲怎么调优这些程序和管理运行它们的集群——程序写得对是一回事，跑得高效、跑得稳定是另一回事，需要性能分析和系统管理的功夫。