第2章 并行编程模型（Parallel Programming Models）

一、导读

2.1 本章学习目标

理解并行编程模型作为硬件与程序员之间抽象接口的核心作用，掌握抽象层次与实现效率之间的权衡关系

深入掌握共享内存编程模型的原理、实现机制和同步方法，能够使用 OpenMP 或 pthreads 编写正确的共享内存并行程序

深入掌握消息传递编程模型的原理和通信模式，能够使用 MPI 编写分布式内存并行程序

理解数据并行模型的工作机制，了解其在 GPU 计算（如 CUDA、OpenCL）中的应用

掌握 SPMD（Single Program Multiple Data）编程范式的核心思想，理解其与 MPI 和共享内存编程的关系

能够根据问题特性、硬件架构和性能需求，为具体应用选择最合适的并行编程模型

理解不同编程模型在正确性保证、性能可预测性和开发效率方面的差异

了解新兴的并行编程模型和框架（如 MapReduce、数据流模型）的发展趋势

2.2 为什么本章如此重要

并行编程模型是连接硬件能力与软件应用的桥梁。无论硬件多么强大，如果程序员无法方便地表达并行性，这些硬件能力就无法被有效利用。并行编程模型决定了程序员思考问题的方式、表达并行性的语法以及调试和优化程序的工具链。

从历史角度看，并行编程模型的演进直接影响了并行计算的普及程度。早期的并行编程需要直接操作硬件寄存器和中断，只有极少数专家才能胜任。共享内存模型的出现将程序员从显式通信的复杂性中解放出来，使得更多开发者能够编写并行程序。MPI 的标准化使得消息传递程序具有了可移植性，推动了集群计算的发展。近年来，CUDA 和 OpenCL 等 GPU 编程模型的成熟，使得深度学习的大规模训练成为可能。

从实践角度看，选择错误的编程模型可能导致开发效率低下或性能无法达标。例如，在分布式集群上使用共享内存模型会导致大量的远程内存访问开销；在共享内存系统上使用消息传递模型则会引入不必要的数据复制和通信延迟。理解各种模型的特点和适用场景，是高效开发并行程序的前提。

此外，现代并行系统越来越多地采用混合编程模型。例如，在由多核节点组成的集群上，节点内使用 OpenMP 利用共享内存，节点间使用 MPI 进行消息传递。理解各种基本模型的特点，是掌握混合编程的基础。

2.3 核心问题引导

共享内存模型和消息传递模型在硬件实现和编程接口上有什么本质区别？为什么没有一种模型能同时满足所有场景的需求？

在共享内存模型中，程序员是否需要关心数据实际存储在哪个节点的内存中？NUMA 架构对共享内存编程有什么影响？

MPI 的阻塞发送和非阻塞发送有什么区别？在什么场景下应该使用非阻塞通信？

数据并行模型为什么特别适合 GPU 架构？它与 SIMD 有什么联系和区别？

SPMD 模式如何在不使用显式进程编号的情况下实现不同进程执行不同的逻辑？

为什么 MapReduce 模型能够在大数据处理领域取得成功？它与传统的消息传递模型有什么异同？

在一个由多核节点组成的集群上，应该选择什么编程模型？为什么混合编程模型成为主流？

并行编程模型的未来发展趋势是什么？PGAS（Partitioned Global Address Space）模型如何结合共享内存和消息传递的优点？

二、核心概念详解

2.1 共享内存编程模型（约800字）

共享内存编程模型是最直观的并行编程范式。在这个模型中，多个处理器或线程共享同一个统一的地址空间，任何线程都可以直接通过读写内存地址来与其他线程交换数据。这种模型的核心优势在于编程的简洁性：数据共享是隐式的，程序员无需显式地发送和接收数据，只需通过读写共享变量即可实现线程间的通信。

从编程接口看，共享内存模型主要有两种实现方式。第一种是基于线程的方式，使用 pthreads（POSIX Threads）或 Windows Threads 等系统级线程库。程序员显式创建线程，每个线程执行不同的函数，通过共享变量和同步原语（互斥锁、信号量、条件变量等）进行协调。这种方式提供了最大的灵活性，但也要求程序员手动管理所有的同步细节。

第二种是基于编译器指令的方式，以 OpenMP 为代表。OpenMP 通过 #pragma 指令让程序员标注哪些代码段需要并行执行，编译器自动生成线程创建、任务分配和同步的代码。例如，一个简单的 for 循环并行化只需要添加一行 #pragma omp parallel for 指令。OpenMP 极大地降低了共享内存编程的门槛，使得不具备深厚并行编程经验的开发者也能利用多核处理器的计算能力。

共享内存模型的主要挑战在于同步和数据竞争。当多个线程同时读写同一个共享变量时，如果没有适当的同步机制，程序的行为将变得不确定。数据竞争（Data Race）是共享内存编程中最常见的错误来源，也是最难调试的问题之一，因为它可能导致间歇性的错误，难以复现。

另一个重要问题是可扩展性。在 NUMA（Non-Uniform Memory Access）架构中，虽然所有处理器共享同一个地址空间，但访问本地内存和远程内存的延迟差异显著。如果程序员不关注数据的本地性，大量的远程内存访问会严重降低性能。OpenMP 和 pthreads 本身不提供 NUMA 感知的编程接口，需要结合操作系统提供的内存绑定（Memory Binding）机制来优化。

2.2 消息传递编程模型（约750字）

消息传递编程模型采用与共享内存完全不同的设计哲学。在这个模型中，每个进程拥有独立的私有地址空间，进程之间不能直接访问彼此的内存。所有数据交换必须通过显式的消息传递来完成，发送方调用 send 原语将数据放入通信缓冲区，接收方调用 receive 原语从缓冲区中取出数据。

MPI（Message Passing Interface）是消息传递模型最成功的标准化实现。MPI 定义了一组丰富的通信原语，包括点对点通信（send/receive）、集合通信（broadcast、scatter、gather、reduce 等）和进程组管理。MPI 的设计目标是高性能和可移植性，几乎所有的高性能计算集群都使用 MPI 作为主要的编程框架。

消息传递模型的核心优势在于其明确性。所有的数据通信都是显式的，程序员清楚地知道何时何地发生数据交换。这种明确性带来两个好处：第一，程序的行为是确定性的，不存在数据竞争的问题；第二，程序员可以精确控制通信的模式和时机，从而优化通信性能。

消息传递模型的另一个重要优势是可扩展性。由于每个进程拥有独立的地址空间，系统可以轻松地扩展到数千甚至数万个节点，每个节点可以是一台独立的计算机。这种模型天然适合分布式内存架构，如计算集群和超级计算机。目前世界上最快的超级计算机几乎都使用 MPI 进行编程。

然而，消息传递模型的编程复杂度也显著高于共享内存模型。程序员需要手动分解数据、设计通信模式、管理缓冲区，并处理各种通信模式可能带来的死锁问题。调试 MPI 程序也比调试共享内存程序更加困难，因为错误可能涉及多个进程之间的交互。

MPI 的通信模式可分为阻塞和非阻塞两种。阻塞发送（MPI_Send）在数据被安全传输后才会返回，可能导致发送方等待。非阻塞发送（MPI_Isend）立即返回，允许计算和通信重叠，是优化性能的重要手段。熟练使用非阻塞通信是编写高性能 MPI 程序的关键技能。

2.3 数据并行模型与 GPU 计算（约700字）

数据并行模型是一种高层次的并行编程抽象，其核心思想是将相同的操作同时应用于数据集的不同部分。程序员只需定义对单个数据元素的操作，运行时系统负责将操作分发到多个处理器上并行执行。这种模型极大地简化了并行编程，因为程序员无需显式管理线程或进程。

数据并行模型最成功的应用平台是 GPU（Graphics Processing Unit）。现代 GPU 拥有数千个轻量级计算核心，专为大规模数据并行计算而设计。NVIDIA 的 CUDA 和开放的 OpenCL 是两种主流的 GPU 编程模型。在 CUDA 中，程序员定义一个 kernel 函数来处理单个数据元素，然后通过启动（launch）配置指定线程数量和块大小，GPU 会自动将 kernel 分发到数千个核心上执行。

GPU 的线程层次结构通常分为三级：线程（Thread）组成线程块（Thread Block），线程块组成网格（Grid）。线程块内的线程可以通过共享内存（Shared Memory）进行高效通信和同步。线程块之间相互独立，不能直接通信。这种层次结构反映了 GPU 硬件的组织方式，程序员需要根据硬件特性合理设计线程块大小和数据分配策略。

数据并行模型的关键限制在于其适用范围。它最适合数据并行度高、计算密集且数据访问模式规则的任务。对于控制流复杂、数据依赖关系紧密或需要频繁通信的任务，数据并行模型的效率较低。此外，GPU 与主机之间的数据传输开销也不可忽视，需要尽量减少主机和设备之间的数据搬运。

近年来，数据并行模型已从图形处理扩展到通用计算领域。深度学习训练中的矩阵乘法、卷积运算等操作天然适合 GPU 的数据并行架构。TensorFlow、PyTorch 等深度学习框架在底层大量使用 GPU 的数据并行能力，使得大规模神经网络的训练成为可能。

2.4 SPMD 编程范式（约550字）

SPMD（Single Program Multiple Data）是一种兼顾灵活性和编程便利性的并行编程范式。在 SPMD 模式中，所有处理器执行同一份程序代码，但每个处理器处理不同的数据子集。程序员通过进程编号（rank）来区分不同处理器的行为，使用条件语句实现不同处理器执行不同的逻辑。

SPMD 是 MPI 编程的标准模式。在典型的 MPI 程序中，所有进程启动后执行相同的 main 函数，通过 MPI_Comm_rank 获取自己的编号，通过 MPI_Comm_size 获取总进程数。根据编号不同，每个进程负责计算不同的数据块。例如，在一个数组求和的程序中，进程 0 处理数组的前 1/4，进程 1 处理第二个 1/4，依此类推，最后通过 MPI_Reduce 汇总结果。

SPMD 的优势在于代码的简洁性和可维护性。只需要编写和维护一份代码，所有进程共享相同的逻辑。与 MPMD（Multiple Program Multiple Data）模式相比，SPMD 不需要管理多个不同的可执行文件，简化了程序的部署和调试。

SPMD 的另一个重要优势是它与底层硬件的良好映射。无论是共享内存系统上的线程，还是分布式系统上的进程，SPMD 模式都可以自然地适配。这也是为什么 SPMD 成为并行计算中最流行的编程范式。

2.5 PGAS 模型：统一两种范式（约500字）

PGAS（Partitioned Global Address Space，分区全局地址空间）模型试图结合共享内存和消息传递两种模型的优点。它提供全局地址空间，使得程序员可以像共享内存模型一样直接引用远程数据；同时在底层实现中，它明确区分本地和远程访问，使得程序员能够像消息传递模型一样优化通信性能。

UPC（Unified Parallel C）和 Coarray Fortran 是 PGAS 模型的早期实现。近年来，Chapel、X10 和 Julia 等新兴并行语言也采用了 PGAS 的理念。这些语言提供了更高层次的抽象，同时保持了对底层通信的控制能力。

PGAS 模型特别适合 NUMA 架构和分布式共享内存系统。在这些系统上，虽然所有内存都是全局可访问的，但本地访问和远程访问的性能差异显著。PGAS 模型允许程序员在逻辑上使用全局地址空间，同时在物理上优化数据的分布和访问模式。

三、深入分析与讨论

3.1 共享内存与消息传递的深层对比（约550字）

共享内存和消息传递两种模型代表了并行编程的两种基本哲学，它们的差异不仅体现在编程接口上，更深入到系统设计的各个层面。

在数据可见性方面，共享内存模型中所有线程看到的是同一个地址空间，一个线程对共享变量的修改对其他线程立即可见（在内存一致性模型允许的范围内）。消息传递模型中数据是私有的，必须通过显式通信才能共享。这使得共享内存模型在数据共享密集的场景中更自然，而消息传递模型在数据独立的场景中更高效。

在正确性保证方面，共享内存模型面临数据竞争的挑战。多个线程同时访问共享变量时，必须使用锁或其他同步机制来保证正确性。消息传递模型天然避免了数据竞争，因为数据通过复制在进程间传递，每个进程只操作自己的数据副本。

在性能特征方面，共享内存模型中的同步操作（如获取锁）可能成为性能瓶颈，特别是在高竞争场景下。消息传递模型的通信延迟取决于网络拓扑和距离，在大规模分布式系统中可能显著高于共享内存的内存访问延迟。

在可扩展性方面，消息传递模型由于没有共享状态，理论上可以无限扩展。共享内存模型受限于单一地址空间的大小和互连网络的带宽，扩展性存在实际上限。

3.2 混合编程模型的实践策略（约500字）

现代大规模并行系统通常采用层次化架构：由多个多核节点通过网络互连组成集群。在这种架构上，单一的编程模型往往不能充分利用硬件能力。混合编程模型结合节点内共享内存和节点间消息传递，成为主流的实践策略。

最常见的混合方案是 MPI + OpenMP。节点间使用 MPI 进行消息传递，节点内使用 OpenMP 进行共享内存并行。这种方案的优势在于：减少 MPI 进程数可以降低通信开销和内存占用（每个 MPI 进程需要独立的内存空间），同时利用 OpenMP 线程充分利用节点内的多核资源。

混合编程的关键挑战在于如何合理分配并行度。例如，在一个有 64 个节点、每节点 32 核的系统上，可以选择 64 个 MPI 进程（每进程 32 线程），或 256 个 MPI 进程（每进程 8 线程），或其他组合。最优配置取决于应用的通信模式、计算强度和内存需求，通常需要通过实验确定。

3.3 并行编程模型的选择策略（约450字）

选择合适的并行编程模型需要综合考虑多个因素。首先是硬件架构：共享内存多核系统适合 OpenMP 或 pthreads；分布式集群适合 MPI；GPU 加速适合 CUDA 或 OpenCL；混合架构则需要混合编程模型。

其次是问题特性。数据并行度高、计算规则的任务适合数据并行模型；需要频繁数据交换的任务适合共享内存模型；数据独立、通信模式简单的任务适合消息传递模型。

第三是开发效率需求。OpenMP 的编译指令方式开发效率最高，适合快速原型开发。MPI 虽然复杂，但生态成熟，文档丰富。GPU 编程的学习曲线较陡，但性能潜力巨大。

最后是性能目标。如果对性能要求极高，需要精细控制通信和数据布局，MPI 或 CUDA 是更好的选择。如果性能要求适中，OpenMP 或高级并行框架可能更高效。

四、实践案例

4.1 案例一：矩阵乘法的三种并行实现对比（约450字）

以 C = A * B 的矩阵乘法为例，比较三种编程模型的实现方式。

在 OpenMP 共享内存模型中，只需在外层循环添加 #pragma omp parallel for 指令，编译器自动将行分配给不同线程。所有线程共享矩阵 A、B、C 的内存，无需显式数据分发。代码简洁，但需要确保循环之间没有数据依赖。

在 MPI 消息传递模型中，需要将矩阵 A 按行分块发送给各进程，矩阵 B 需要广播到所有进程。每个进程计算自己负责的行，最后通过 MPI_Gather 收集结果。代码较复杂，需要管理数据的分发和收集，但可以扩展到任意规模的集群。

在 CUDA 数据并行模型中，定义一个 kernel 函数计算 C 的一个元素，启动一个二维线程网格覆盖整个结果矩阵。GPU 自动将线程映射到数千个核心上执行。需要处理主机与设备之间的数据传输和 GPU 内存管理。

三种实现各有特点：OpenMP 最简单，MPI 最灵活，CUDA 性能潜力最大。选择哪种取决于硬件环境和性能需求。

4.2 案例二：MPI + OpenMP 混合编程在气象模拟中的应用（约400字）

全球大气环流模型（GCM）是典型的大规模科学计算应用。以某 GCM 为例，计算区域被划分为三维网格，每个时间步需要计算每个网格点上的温度、压力、风速等物理量。

该应用运行在由 128 个节点组成的集群上，每节点 64 核。采用 MPI + OpenMP 混合编程：使用 128 个 MPI 进程，每个进程负责一个节点上的计算区域子块；节点内使用 OpenMP 将每个子块的计算分配到 64 个线程上。

相邻子块之间需要交换边界数据（Halo Exchange）。每个 MPI 进程在每步计算前与相邻进程交换边界层数据，使用 MPI_Isend 和 MPI_Irecv 进行非阻塞通信，使通信与内部计算重叠。

这种混合方案相比纯 MPI（8192 进程）减少了进程间通信量，降低了通信开销，同时充分利用了节点内的共享内存资源。实测显示，混合方案在相同硬件上的性能比纯 MPI 方案提升约 15%，主要得益于减少的通信次数和更低的内存占用。

五、常见误区与注意事项

误区：共享内存模型不需要考虑数据分布。在 NUMA 架构上，虽然所有内存都是全局可访问的，但远程内存访问延迟可能是本地的两倍以上。不注意数据本地性会导致严重的性能下降。应使用内存绑定（numactl）将数据分配到访问它的线程所在的节点上。

误区：消息传递模型不存在同步问题。虽然消息传递模型没有数据竞争，但错误的通信模式可能导致死锁。例如，两个进程互相等待对方的消息而不发送自己的消息，就会形成死锁。需要仔细设计通信模式，必要时使用非阻塞通信。

误区：数据并行模型可以处理所有类型的并行问题。数据并行模型最适合规则的数据并行任务。对于需要复杂控制流、不规则数据结构或频繁全局同步的问题，数据并行模型效率低下。选择模型时应考虑问题的计算特性。

误区：混合编程一定比单一模型好。混合编程增加了代码复杂度，且需要仔细调优 MPI 进程数和 OpenMP 线程数的比例。对于小规模问题或通信密集型应用，混合编程可能反而不如单一模型。

注意事项：并行编程模型的选择应尽早确定。编程模型决定了程序的架构和数据流设计，后期更换成本极高。在项目初期就应根据目标硬件和应用特性选择合适的模型。

六、本章小结

本章系统介绍了主流的并行编程模型及其特点。共享内存模型通过统一的地址空间简化了数据共享，OpenMP 和 pthreads 是两种主要的实现方式，但需要处理同步和数据竞争问题。消息传递模型通过显式通信保证了确定性和可扩展性，MPI 是该模型最成功的实现，适合大规模分布式系统。数据并行模型将相同操作应用于不同数据，在 GPU 计算中得到了广泛应用，CUDA 和 OpenCL 是代表性平台。SPMD 模式通过让所有处理器执行相同程序处理不同数据，提供了编程便利性和灵活性的良好平衡。PGAS 模型试图统一共享内存和消息传递的优点，是并行编程模型发展的重要方向。在实际应用中，混合编程模型（如 MPI + OpenMP）成为大规模并行系统的主流选择。选择合适的编程模型需要综合考虑硬件架构、问题特性、开发效率和性能目标。

七、思考题与练习

使用 OpenMP 编写一个并行程序，计算数组所有元素的和。讨论在归约操作中可能出现的竞争条件，以及 OpenMP 的 reduction 子句如何解决这个问题。

使用 MPI 编写一个程序，实现矩阵向量乘法 y = A * x。矩阵 A 按行分块存储在不同进程上，向量 x 需要广播到所有进程。比较使用 MPI_Bcast 和 MPI_Scatter 的不同实现方式。

分析一个你熟悉的应用程序（如 Web 服务器、图像处理工具或科学计算程序），讨论它适合使用哪种并行编程模型，并说明理由。

对比共享内存模型和消息传递模型在以下方面的差异：数据共享方式、同步机制、可扩展性、编程复杂度和调试难度。给出各自最适合的应用场景。

解释为什么 GPU 架构特别适合数据并行模型。从 GPU 的线程层次结构、内存层次和计算核心密度三个方面进行分析。

设计一个 MPI + OpenMP 的混合编程方案，用于在一个由 32 个节点（每节点 16 核）组成的集群上求解大型稀疏线性方程组。说明 MPI 进程和 OpenMP 线程的分配策略，以及通信模式的设计。

研究 PGAS 模型的一种具体实现（如 UPC、Chapel 或 Julia 的分布式数组），分析它如何结合共享内存和消息传递的特点。编写一个简单的示例程序。

讨论并行编程模型的未来发展趋势。随着硬件架构的不断演进（如 Chiplet 封装、CXL 互连、近存计算），编程模型需要做出哪些适应？