第 1 章 为什么需要并行计算#

1.2 为什么需要建立并行系统#

单核性能提升受限#

• 过去单处理器性能提升主要依赖晶体管密度增加。
• 晶体管变小可以提高速度，但会带来更高功耗和散热压力。
• 风冷散热逐渐接近极限，继续单纯提高单核速度变得困难。
• 因此，提高计算能力的重要方向转向并行化。

多核处理器#

• 多核处理器：在一个芯片上集成多个相对简单、完整的处理器核心。
• 单核系统：传统只有一个 CPU 核心的处理器系统。
• 普通串行程序通常不能自动利用多核，程序员需要学习并行编程。

并行化的两种基本方式#

并行程序的协调问题#

1.3 并行系统的分类#

按内存访问方式分类#

共享内存系统#

• 多个核心共享同一块内存。
• 原则上，每个核心都可以读写每个内存位置。
• 核心可通过共享变量进行协调。

核心0   ┐
核心1   ├── 共享内存
...    │
核心p-1 ┘

分布式内存系统#

• 每个核心或节点有自己的私有内存。
• 核心之间通常不能直接访问彼此内存。
• 需要通过网络发送消息进行通信。

核心0 -- 内存0     ┐
核心1 -- 内存1     ├── 网络
...               │
核心p-1 -- 内存p-1 ┘

按指令流和数据流分类#

这类分类通常称为 Flynn 分类法。它从两个维度描述并行系统：

• 指令流（instruction stream）：处理器执行的指令序列。
• 数据流（data stream）：指令作用的数据序列。

根据“指令流数量”和“数据流数量”，Flynn 分类法一共分为四类：

本书主要关注 SIMD 和 MIMD：

• SIMD 更像“同一条指令同时作用在多份数据上”。
• MIMD 更像“多个独立处理器各自执行自己的指令流”。
• MISD 理论上存在，但在通用并行程序设计中很少作为主要模型。

第 1 章小结#

并发、并行、分布式#

第 2 章 并行硬件与并行软件#

2.1 背景知识#

2.1.1 冯·诺依曼体系结构#

基本组成#

经典冯·诺依曼体系结构包括：

• 主存
• CPU：也叫处理器或核心
• 互连网络：连接 CPU 和主存

主存#

• 主存由一组存储位置组成。
• 每个位置有：
  • 地址：用于访问该位置。
  • 内容：保存指令或数据。

CPU#

冯·诺依曼瓶颈#

• CPU 和主存分离。
• 指令和数据必须通过互连网络传输。
• CPU 执行速度可能远快于内存访问速度，导致 CPU 等待内存。
• 互连网络限制了程序访问指令和数据的速率。

类比：

• CPU = 工厂
• 主存 = 仓库
• 互连 = 道路
• 如果运输速度跟不上生产速度，道路就成为瓶颈。

2.1.2 进程、多任务和线程#

进程#

进程：正在执行的程序实例。

进程通常包括：

• 可执行机器语言程序
• 内存块：代码、调用栈、堆等
• 资源描述符：如文件描述符
• 安全信息：可访问哪些资源
• 状态信息：是否可运行、是否等待资源、寄存器内容等

多任务#

• 多任务操作系统支持多个程序在同一时间段内运行。
• 单核系统也可通过时间片轮流执行不同进程，让它们看起来同时运行。
• 如果进程等待资源，会进入阻塞态，此时操作系统可以运行其他进程。

线程#

线程：进程内部的执行单元，用于把程序划分为多个相对独立的任务。是 CPU 资源调度的单元

特点：

• 同一进程内的线程共享大部分资源。
• 线程切换通常比进程切换更快。
• 每个线程需要自己的程序计数器和调用栈。

线程共享与独有内容：

图 2.2：有三个线程的进程

2.2 冯·诺依曼模型的改进#

本节介绍三类改进：

• 缓存
• 虚拟内存
• 低级别并行性

2.2.1 缓存基础#

缓存的作用#

• 缓存用于缓解冯·诺依曼瓶颈。
• 思想：
  • 一次传输一块数据或指令，而不是单个数据项。
  • 把常用数据和指令放在更靠近 CPU 的高速存储中。

CPU 缓存：CPU 能以比访问主存更快速度访问的一组内存位置。缓存速度快，但容量通常远小于主存。

局部性#

数组例子：

float z[1000];
sum = 0.0;
for (i = 0; i < 1000; i++)
    sum += z[i];

数组连续存储，访问 z[i] 后通常接着访问 z[i+1]，符合空间局部性。

缓存行#

• 缓存行 / 缓存块：内存和缓存之间传输的基本单位。
• 一次缓存缺失通常会把包含目标数据的一整行读入缓存。
• 如果一个缓存行保存 z[0] 到 z[15]，那么第一次访问 z[0] 后，后续访问 z[1] 到 z[15] 可能直接命中。

多级缓存#

CPU 访问数据时通常按 L1 -> L2 -> L3 -> 主存 的顺序查找。

缓存命中与缺失#

例子：L1 缺失但 L2 命中。

缓存缺失可能导致 CPU 暂停，等待数据从主存或低层缓存取回。

写策略#

2.2.2 缓存映射#

缓存映射问题：主存中的一个数据块被读入缓存时，应该放在缓存的哪个位置？

三种映射方式#

直接映射例子#

主存有 16 个块，缓存有 4 行：

缓存行索引 = 主存块索引 mod 4

映射：

• 0, 4, 8, 12 -> 0
• 1, 5, 9, 13 -> 1
• 2, 6, 10, 14 -> 2
• 3, 7, 11, 15 -> 3

两路组相联例子#

缓存 4 行，分成两组：

• 组 0：缓存行 0、1
• 组 1：缓存行 2、3

组索引 = 主存块索引 mod 2

映射：

• 偶数主存块：可放入缓存行 0 或 1
• 奇数主存块：可放入缓存行 2 或 3

表 2.1：16 个主存块分配到 4 个缓存行#

缓存替换策略#

• 当多个主存块可映射到多个缓存位置时，需要决定替换哪一行。
• LRU：Least Recently Used，最近最少使用。
• 思想：优先逐出最久没有被访问的缓存行。

2.2.3 缓存和程序：示例#

核心结论#

• CPU 缓存由硬件控制，程序员不能直接决定缓存内容。
• 但程序员可以利用局部性写出更缓存友好的代码。
• C 语言二维数组按行优先存储，因此按行访问通常比按列访问快。

行优先存储#

A[4][4] 在内存中按行连续存储：

两种循环顺序#

按行访问，缓存友好：

for (i = 0; i < MAX; i++)
    for (j = 0; j < MAX; j++)
        y[i] += A[i][j] * x[j];

按列访问，缓存不友好：

for (j = 0; j < MAX; j++)
    for (i = 0; i < MAX; i++)
        y[i] += A[i][j] * x[j];

原因：

• 第一种访问顺序类似：A[0][0], A[0][1], A[0][2], A[0][3]，连续。
• 第二种访问顺序类似：A[0][0], A[1][0], A[2][0], A[3][0]，不连续。

缓存缺失分析#

假设：

• MAX = 4
• 一个缓存行保存 4 个 double
• 缓存只能保存两行 A
• 循环开始时 A 不在缓存中

结果：

• 按行访问：每行第一次访问缺失，之后同一行命中；约 4 次缺失。
• 按列访问：频繁跨行访问，缓存行容易被替换；缺失更多。

结论：对 C 的二维数组，优先按行遍历，能更好利用空间局部性。

2.2.4 虚拟内存#

核心概念#

• 虚拟内存：让程序使用虚拟地址，由系统映射到实际物理地址。
• 页：虚拟内存和物理内存管理的基本块。
• 页表：记录虚拟页到物理页的映射关系。

TLB#

• TLB：Translation Lookaside Buffer，旁路转换缓冲区。
• 作用：缓存少量页表项，加速虚拟地址到物理地址的转换。
• 常见大小：几十到几百个条目。

虚拟内存与缓存的区别#

2.2.5 指令级并行#

指令级并行（Instruction-Level Parallelism，ILP）：通过让多个处理器组件或功能单元同时执行指令来提高处理器性能。

ILP 的两种主要方法：

几乎所有现代 CPU 都会使用流水线和多发射。

流水线#

流水线类似工厂装配线：不同阶段同时处理不同任务。

浮点加法可拆成多个阶段：

1. 获取操作数
2. 比较指数
3. 移位一个操作数
4. 相加
5. 标准化结果
6. 四舍五入
7. 存储结果

如果每个阶段需要 1 ns，单个浮点加法仍需 7 ns。但在循环中，不同加法可以同时处于不同阶段：

for (i = 0; i < 1000; i++)
    z[i] = x[i] + y[i];

效果：

• 非流水线：1000 次加法约需 7000 ns。
• 7 阶段流水线：理想情况下约需 1006 ns。
• 原因：流水线填满后，几乎每 1 ns 产生一个结果。

注意：k 阶段流水线通常无法获得严格 k 倍加速。

限制：

• 阶段速度受最慢功能单元限制。
• 等待操作数、分支等延迟可能导致流水线暂停。

多发射#

多发射处理器：复制功能单元，尝试同时执行程序中的多条不同指令。

例子：

for (i = 0; i < 1000; i++)
    z[i] = x[i] + y[i];

如果有两个浮点加法器：

• 第一个加法器计算 z[0] 时，第二个可以计算 z[1]。
• 第一个计算 z[2] 时，第二个可以计算 z[3]。

多发射分类：

前瞻执行#

前瞻执行（speculation）：编译器或处理器预测后续执行路径，并提前执行相关指令。

分支预测例子：

z = x + y;
if (z > 0)
    w = x;
else
    w = y;

系统可能预测 z > 0，于是提前执行 w = x。

指针别名预测例子：

z = x + y;
w = *a_p;

系统可能预测 a_p 不指向 z，于是尝试同时执行两个赋值。

前瞻执行的关键：

• 如果预测正确，保留结果。
• 如果预测错误，丢弃预测结果并重新执行正确路径。
• 硬件通常会把预测执行结果先放在缓冲区中，确认正确后再提交到寄存器或内存。

指令重排#

• 动态多发射系统可以无序执行指令。
• 现代处理器通常仍按顺序加载指令，并按程序顺序提交结果。
• 优化编译器也可能重排指令。
• 指令重排会影响共享内存编程，后续需要注意内存可见性和同步问题。

2.2.6 硬件多线程#

ILP 的局限#

ILP 很难利用长依赖链程序中的并行性。

例子：直接计算斐波那契数列。

f[0] = f[1] = 1;
for (i = 2; i <= n; i++)
    f[i] = f[i-1] + f[i-2];

每一项依赖前两项，几乎没有可以同时执行的指令。

线程级并行#

线程级并行（Thread-Level Parallelism，TLP）：通过同时执行不同线程来提供并行性。

特点：

• 比 ILP 粒度更粗。
• 并行单位是线程，而不是单条指令。
• 当当前线程因为等待内存等原因暂停时，可以切换去执行另一个线程。

硬件多线程#

硬件多线程：处理器支持线程之间的快速切换，使系统在一个线程暂停时继续执行其他线程。

分类：

2.3 并行硬件#

2.3.2 SIMD 系统#

基本特点#

• SIMD：Single Instruction Multiple Data，单指令流多数据流。
• 一个控制单元向多个数据通路广播同一条指令。
• 各数据通路对自己的数据执行相同指令，或者在不适用时空闲。

抽象 SIMD 系统：

条件分支带来的问题#

SIMD 要求所有数据通路执行相同指令或空闲，这可能降低整体性能。

例子：

for (i = 0; i < n; i++)
    if (y[i] > 0.0)
        x[i] += y[i];

执行过程：

• 每个数据通路都要加载对应的 y[i] 并判断是否为正。
• 若 y[i] > 0，该通路执行加法。
• 若 y[i] <= 0，该通路在其他通路执行加法时只能空闲。

同步执行约束#

• 经典 SIMD 系统中，各数据通路必须同步运行。
• 每个数据通路必须等待下一条指令广播后才能继续。
• 数据通路通常没有自己的指令存储区，不能把指令保存起来延迟执行。

数据并行性#

数据并行性：把数据划分给多个处理器或数据通路，并让它们对各自的数据子集执行相同或相似的指令。

SIMD 系统主要利用的就是数据并行性。

GPU 不是纯 SIMD#

• 图形处理 API 通常用点、线、三角形表示对象表面，再通过图形处理流水线生成屏幕像素。
• 流水线中的可编程阶段由着色器函数指定。
• 着色器函数通常很短，并且可以应用到图形流中的大量元素，因此天然具有隐式并行性。
• GPU 每个处理核心通常包含大量数据通路，可用 SIMD 并行提高吞吐量。
• GPU 处理图像时数据量很大，需要很高的数据传输速率，因此严重依赖硬件多线程来隐藏内存访问暂停。
• GPU 在小问题上可能表现较差，因为需要大量线程才能让数据通路保持忙碌。
• GPU 会使用 SIMD 式的数据并行，但不是纯 SIMD 系统。
• 给定核心上的多个数据通路可以执行 SIMD 并行。
• 当代 GPU 的单个核心也可以运行多个指令流。
• 典型 GPU 有几十个核心，这些核心也能执行相互独立的指令流。
• 因此，GPU 既不是纯 SIMD，也不是纯 MIMD，而是混合了多种并行特征。

GPU 的内存特征#

• GPU 可以使用共享内存，也可以使用分布式内存。
• 大型 GPU 系统可能同时包含两种特征：
  • 一些核心访问共同的共享内存块。
  • 其他核心访问不同的共享内存块。
  • 访问不同内存块的核心可以通过网络通信。
• 本书后续主要讨论使用共享内存的 GPU。

2.3.3 MIMD 系统#

基本特点#

• MIMD：Multiple Instruction Multiple Data，多指令流多数据流。
• 支持多个并行指令流运行在多个数据流上。
• 通常由多个独立处理单元或核心组成。
• 每个处理单元通常有自己的控制单元和数据通路。

抽象 MIMD 系统：

异步执行#

• MIMD 系统通常是异步的。
• 各处理器可以按自己的速度运行。
• 许多 MIMD 系统没有全局时钟。
• 即使多个处理器执行相同指令序列，在任意时刻也可能处于不同语句。
• 如果需要让处理器在某些点对齐，程序员必须显式同步。

MIMD 的两类内存系统#

共享内存系统：

分布式内存系统：

共享内存系统#

• 最常见的共享内存系统使用一个或多个多核处理器。
• 多核处理器在单个芯片上包含多个 CPU 或核心。
• 核心通常有私有 L1 缓存，其他缓存可能共享，也可能不共享。

共享内存多核系统分为：

UMA 多核系统：

NUMA 多核系统：

分布式内存系统#

• 最常见的分布式内存系统称为集群。
• 集群通常由一系列商用系统组成，例如通过以太网连接的 PC。
• 集群中的节点是通过通信网络连接在一起的计算单元。
• 现代集群节点通常本身就是共享内存系统，并带有一个或多个多核处理器。
• 为了区别于纯分布式内存系统，这类系统有时称为混合系统。
• 现在通常默认集群具有共享内存节点。

网格#

• 网格提供基础设施，把地理上分布的大型计算机网络组织成统一的分布式内存系统。
• 网格通常是异构系统：不同节点可能由不同类型的硬件构成。

2.3.5 缓存一致性#

缓存一致性问题#

在共享内存多核系统中，多个核心的缓存可能保存同一个变量的副本。

问题：

• 核心 0 更新变量 x 后，核心 1 缓存中的 x 可能仍是旧值。
• 写直达会更新主存，但不一定更新其他核心缓存中的副本。
• 写回甚至可能暂时只更新核心 0 的缓存，主存和其他核心都看不到新值。

缓存一致性问题：当多个处理器缓存同一变量或同一缓存行时，需要保证一个处理器的更新能被其他处理器正确看到。

监听缓存一致性#

监听缓存一致性（snooping cache coherence）：各核心监听互连网络上的更新广播。

要点：

• 广播通常针对缓存行，不是单个变量。
• 互连不一定必须是总线，但必须支持从一个处理器向其他处理器广播。
• 监听可用于写直达缓存，也可用于写回缓存。
• 写回缓存需要额外通信，因为更新不会立刻写入主存。

基于目录的缓存一致性#

监听协议需要频繁广播，在大规模系统中广播成本高，可扩展性差。

基于目录的缓存一致性：使用一个称为目录的数据结构记录每个缓存行的状态。

目录通常记录：

• 某缓存行当前在哪些核心的缓存中有副本。
• 缓存行是否被修改。
• 缓存行的有效/无效状态。

工作方式：

1. 某核心读取一个缓存行时，目录记录该核心拥有该行副本。
2. 某核心更新该缓存行时，先查询目录。
3. 系统只通知那些真正保存该缓存行副本的核心，使其副本失效。

优缺点：

伪共享#

CPU 缓存由硬件实现，并且按缓存行工作，而不是按单个变量工作。这可能导致伪共享。

伪共享：多个核心访问的是不同变量，但这些变量位于同一个缓存行中，导致系统像它们共享同一变量一样不断失效缓存行。

串行例子：

int i, j, m, n;
double y[m];

/* y 初始化为 0 */
for (i = 0; i < m; i++)
    for (j = 0; j < n; j++)
        y[i] += f(i, j);

可以把外层循环的迭代划分给多个核心。例如两个核心时：

/* 私有变量 */
int i, j, iter_count;

/* 共享变量 */
int m, n, core_count;
double y[m];

iter_count = m / core_count;

/* 核心 0 */
for (i = 0; i < iter_count; i++)
    for (j = 0; j < n; j++)
        y[i] += f(i, j);

/* 核心 1 */
for (i = iter_count; i < 2 * iter_count; i++)
    for (j = 0; j < n; j++)
        y[i] += f(i, j);

关键假设：

• m = 8
• double 是 8 字节
• 缓存行是 64 字节
• y[0] 位于缓存行开头

于是一个缓存行正好能存下 8 个 double，即 y[0]..y[7] 全部位于同一个缓存行。

发生过程：

• 核心 0 更新 y[0]..y[3]。
• 核心 1 更新 y[4]..y[7]。
• 两个核心没有访问彼此的元素。
• 但这些元素属于同一个缓存行。
• 因此任一核心执行 y[i] += f(i, j) 时，都可能使另一个核心缓存中的同一行失效。
• 另一个核心下一次访问自己的 y 元素时，必须重新从内存取回该缓存行。

影响：

• 程序结果仍正确，但会产生大量不必要的内存访问，严重降低性能。
• 如果内层循环次数 n 很大，这种额外内存访问会非常频繁。

常见缓解方法：

• 使用线程或进程本地临时变量。
• 最后再把本地结果复制或归约到共享存储。
• 必要时通过填充、对齐或调整数据布局，避免不同线程频繁写同一缓存行。

2.3.6 共享内存与分布式内存#

• 共享内存对程序员更直观：可以通过共享数据结构隐式协调处理器工作。
• 分布式内存需要显式发送消息，编程负担通常更重。
• 但硬件上，共享内存系统需要维护互连、缓存一致性和访问延迟，扩展到大规模系统更困难。
• 因此，大规模系统常采用分布式内存或混合结构。

2.4 并行软件#

2.4.1 并行化、通信和同步#

易并行示例#

数组加法：

double x[n], y[n];

for (int i = 0; i < n; i++)
    x[i] += y[i];

并行化方法：把数组元素划分给不同进程或线程。

例如有 p 个进程/线程：

• 进程/线程 0 负责 0 ~ n/p - 1
• 进程/线程 1 负责 n/p ~ 2n/p - 1
• 依此类推

并行化时需要做的事#

1. 在进程/线程之间分配工作。
2. 保证每个进程/线程工作量大致相同，即负载平衡。
3. 尽量减少通信量。
4. 安排进程/线程之间的同步。
5. 安排进程/线程之间的通信。

通信与同步常常相关：

• 分布式内存程序通常通过进程间通信隐式同步。
• 共享内存程序通常通过线程同步来完成通信。

2.4.3 共享内存#

共享变量与私有变量#

在共享内存程序中：

线程之间通常通过共享变量通信，因此通信是隐式的。

动态线程和静态线程#

本书后续经常使用静态线程范例。

非确定性#

非确定性：同一个输入可能导致不同输出。

在异步执行的 MIMD 系统中，多个线程独立运行，每个线程完成语句的相对速度可能每次运行都不同，因此输出顺序或结果可能变化。

例子：

printf("Thread %d > my_x = %d\n", my_rank, my_x);

两个线程的输出顺序可能不同：

Thread 0 > my_x = 7
Thread 1 > my_x = 19

也可能是：

Thread 1 > my_x = 19
Thread 0 > my_x = 7

如果只是输出顺序不同，通常问题不大；但在共享内存更新中，非确定性可能导致错误结果。

竞争条件#

竞争条件：多个线程或进程同时访问共享资源，并且访问顺序会影响结果。

例子：

my_val = Compute_val(my_rank);
x += my_val;

x += my_val 通常不是一条不可分割的操作，而是大致包含：

1. 把 x 加载到寄存器。
2. 把 my_val 加载到寄存器。
3. 相加。
4. 把结果写回 x。

如果两个线程交错执行，可能都先读到旧的 x = 0，最后一个写回的结果覆盖另一个线程的更新，导致结果错误。

原子性#

原子操作：操作执行期间不会被其他线程打断或观察到中间状态。

对于共享变量更新，理想情况是每个线程的：

x += my_val;

作为一个原子操作完成。

临界区#

临界区：一次只能由一个线程执行的代码块。

如果一个线程正在执行临界区，其他线程必须被排除在外。这称为互斥访问。

互斥量#

互斥量（mutex，也叫互斥锁、锁）：用于保证临界区互斥访问的同步对象。

使用方式：

my_val = Compute_val(my_rank);
Lock(&add_my_val_lock);
x += my_val;
Unlock(&add_my_val_lock);

流程图：

要点：

• 互斥量保证一次只有一个线程执行 x += my_val。
• 互斥量不规定哪个线程先执行。
• 临界区会被串行化，因此临界区应尽可能少、尽可能短。

忙等待#

忙等待（busy-waiting）：线程进入循环，不断测试某个条件是否成立。

例子：保证线程 1 在线程 0 更新 x 之后再更新。

my_val = Compute_val(my_rank);

if (my_rank == 1)
    while (!ok_for_1);  /* 忙等待循环 */

x += my_val;           /* 临界区 */

if (my_rank == 0)
    ok_for_1 = true;   /* 允许线程 1 更新 x */

特点：

• 优点：概念简单，容易理解。
• 缺点：等待线程会持续占用 CPU 资源，即使它暂时没有做有用工作。

信号量和监视器#

• 信号量：类似互斥量，也可用于线程同步，具体行为细节不同。
• 监视器：更高级的互斥机制，是一个对象，其方法一次只能由一个线程执行。

线程安全#

线程安全：函数或代码在多线程环境中被并发调用时，仍能得到正确结果，不会因为共享状态产生错误。

很多串行程序中的函数可以直接用于并行程序，但需要注意例外。

典型问题：函数内部使用静态局部变量。

• 普通局部变量位于线程自己的调用栈上，通常是私有的。
• 静态局部变量在函数调用结束后仍然存在。
• 如果多个线程同时调用该函数，就可能共享并覆盖同一个静态变量。

例子：strtok 一类函数不是线程安全的。

• 第一次调用时传入一个字符串。
• 后续调用依赖函数内部保存的静态状态继续分割字符串。
• 如果两个线程同时使用，后一个线程可能覆盖前一个线程的内部状态，导致结果错误。

结论：

• 多线程程序中要确认库函数是否线程安全。
• 避免在多个线程间隐式共享函数内部状态。
• 必要时使用线程安全版本的函数，或把状态显式放在线程私有存储中。

2.4.4 分布式内存#

基本特点#

• 在分布式内存程序中，每个核心或进程只能直接访问自己的私有内存。
• 进程之间不能直接读写对方变量。
• 通信通常通过消息传递完成。

消息传递#

消息传递 API 至少提供两类函数：

示意：

rank#

• 消息传递程序通常用序列号或 rank 标识进程。
• 如果共有 p 个进程，rank 通常为 0, 1, ..., p-1。
• 发送和接收时需要指定通信对象的 rank。

SPMD#

SPMD：Single Program Multiple Data，单程序多数据。

含义：

• 多个进程运行同一个可执行文件。
• 每个进程根据自己的 rank 通过不同分支执行不同操作。
• 每个进程处理不同数据。

典型结构：

my_rank = Get_rank();

if (my_rank == 1) {
    /* 进程 1 发送消息 */
    Send(message, MSG_CHAR, 100, 0);
} else if (my_rank == 0) {
    /* 进程 0 接收消息 */
    Receive(message, MSG_CHAR, 100, 1);
}

同名变量不共享#

在分布式内存中，不同进程中的同名变量属于不同内存块。

例如两个进程中都声明：

char message[100];

这不是同一块内存：

• 进程 0 的 message 位于进程 0 的私有内存。
• 进程 1 的 message 位于进程 1 的私有内存。
• 若要把进程 1 的 message 传给进程 0，必须显式发送消息。

核心区别：

2.5 输入和输出#

2.5.1 MIMD 系统#

这里的 MIMD 不是在讲“做计算的模型”本身，而是在讲：多个独立进程/线程同时运行时，如何处理输入和输出。

为什么 I/O 容易出问题#

MIMD 程序中，多个进程/线程可能同时访问：

• stdin
• stdout
• stderr
• 同一个文件

问题：

• 输出顺序不确定，多个进程的输出可能交错。
• 输入分配不明确：不知道哪个进程应该读哪个输入。
• 多个进程同时写同一个文件，可能导致内容混乱或覆盖。

标准输入输出约定#

为避免混乱，书中采用以下规则：

为什么通常让 0 号进程负责 I/O#

• 进程 0 或线程 0 通常被当作“主控者”。
• 可以避免多个进程同时读输入造成不确定性。
• 可以先由 0 号进程读取输入，再通过消息传递或共享变量分发给其他进程/线程。

2.6 性能#

并行程序的主要目标通常是提高性能。评价性能时，常用指标是加速比和效率。

2.6.1 MIMD 系统中的加速比和效率#

理想情况#

如果一个问题可以被平均分给 p 个核心，并且没有额外开销，那么：

并行运行时间 = 串行运行时间 / p

这种理想情况称为线性加速。

线性加速比#

线性加速比：使用 p 个核心时，加速比达到 p。

也就是：

含义：

• 用 2 个核心，理想上快 2 倍。
• 用 4 个核心，理想上快 4 倍。
• 用 p 个核心，理想上快 p 倍。

实际中很难完全达到线性加速，因为存在同步、通信、临界区、线程创建等开销。

加速比#

加速比（speedup）定义为：

其中：

例子：

• 串行运行 100s
• 并行运行 25s

则：

表示并行程序快了 4 倍。

效率#

效率（efficiency）衡量核心是否被充分利用。

定义：

把加速比公式代入：

其中：

解释：

• $E = 1$：完全理想，所有核心都被充分利用。
• $E < 1$：存在开销，核心没有被完全利用。
• $E$ 越接近 1，说明并行化效果越好。

问题规模对性能的影响#

一般来说：

• 增加问题规模时，加速比和效率可能增加。
• 减少问题规模时，加速比和效率可能降低。

原因：

• 并行程序通常有固定开销，例如线程创建、通信、同步、数据分发和结果收集。
• 问题规模较小时，固定开销占比大，并行收益容易被抵消。
• 问题规模较大时，计算量增加，固定开销被摊薄，核心更容易保持忙碌。

为什么实际加速比会低于线性加速#

常见原因：

• 负载不均衡：有些核心先完成后等待。
• 通信开销：进程/线程之间需要交换数据。
• 同步开销：临界区、互斥锁、屏障等会让部分核心等待。
• 串行部分：程序中有些部分无法并行。
• 额外开销：线程创建、数据分发、结果收集等。

2.6.2 阿姆达尔定律#

阿姆达尔定律（Amdahl’s Law）：如果程序中有一部分必须串行执行，那么无论增加多少核心，整体加速比都会受到这部分串行代码的限制。

基本公式#

设：

并行运行时间近似为：

加速比为：

当核心数 $p$ 趋近无穷大时：

也就是说，串行部分越大，最大加速比越低。

例子：90% 可并行#

假设：

• 串行运行时间 $T_{\text{serial}} = 20$
• 90% 可并行
• 10% 必须串行

则：

加速比：

当 $p$ 很大时，$\frac{18}{p}$ 接近 0，所以：

结论：即使并行部分做得很好，甚至使用很多核心，只要 10% 不能并行，最大加速比也不会超过 10。

核心结论#

• 阿姆达尔定律强调：优化并行程序时，不能只看可并行部分，也要关注串行瓶颈。
• 串行比例 $r$ 决定了理论最大加速比。
• 如果串行部分是 $1/100$，最大加速比也只能接近 100。
• 要获得更高加速比，需要减少串行部分，或增大问题规模，让并行部分占比更高。

注意#

阿姆达尔定律通常假设问题规模固定。实际中，随着核心数增加，我们也可能处理更大的问题，此时加速表现可能比固定规模分析更好。

2.6.3 可扩展性#

可扩展性：描述并行程序在增加处理器或核心数量时，性能能否持续提升的能力。

常用符号：

并行时间可粗略写成：

也就是：

并行时间 = 理想分摊后的计算时间 + 并行额外开销

由于：

且：

所以：

如果令 $T_{\text{serial}} = n$，并且：

则：

这个公式说明：如果问题规模 $n$ 不变，只增加处理器数 $P$，那么分母中的 $P T_{\text{overhead}}$ 会变大，效率 $E$ 通常会下降。

可扩展性分为两类：

强扩展性#

• 问题规模固定。
• 增加核心数 $P$。
• 如果效率 $E$ 能保持不变或下降很少，说明程序具有强扩展性。
• 只有通信、同步等并行开销很小时，才容易获得好的强扩展性。

例子：同样大小的矩阵乘法，从 4 个核心增加到 8 个核心，看运行时间是否接近减半。

理想情况下没有额外开销：

此时效率：

现实中通常有额外开销：

因此当 $P$ 增大时，强扩展效率通常会下降。

弱扩展性#

• 增加核心数 $P$。
• 同时按相同比例增加问题规模。
• 如果效率 $E$ 能保持不变或下降很少，说明程序具有弱扩展性。

例子：4 个核心处理 4GB 数据，8 个核心处理 8GB 数据。如果运行时间基本不变，说明弱扩展性较好。

如果：

P -> aP
n -> bn

则效率近似变为：

如果 $a = b$，即核心数和问题规模按相同比例增加，那么效率有可能保持稳定。

对比#

• 强扩展性问的是：同一个问题，用更多核心能不能更快？
• 弱扩展性问的是：更多核心能不能处理更大的问题，同时保持效率？
• 并行程序不是核心越多越好，因为 $P$ 变大时，通信、同步等额外开销也会被放大。

第 3 章 使用 MPI 进行分布式内存编程#

3.1 MPI 概述#

重点#

本章重点：

• 通信
  • 点对点通信
  • 集合通信
• 发送和接收消息的语义
  • 是否阻塞
  • 消息匹配
  • 消息顺序

MPI 是什么#

• MPI：Message Passing Interface，消息传递接口。
• MPI 用于分布式内存编程。
• MPI 程序的基本执行单位通常是进程，不是线程。
• MPI 实际上是一个函数库，不是一门新的编程语言。
• 进程之间通过显式发送和接收消息来通信。

3.2 编译与执行#

编译#

使用 mpicc 编译 MPI 程序：

mpicc -o hello hello.c

执行#

使用 mpiexec 启动多个 MPI 进程：

mpiexec -n 4 ./hello

含义：

• -n 4：启动 4 个进程。
• ./hello：每个进程运行同一个可执行文件。

这体现了 MPI 常见的 SPMD 模型：多个进程运行同一个程序，但根据自己的 rank 执行不同逻辑。

3.3 MPI 初始化和结束#

MPI_Init#

MPI_Init 必须在所有其他 MPI 函数调用之前执行。

作用：

• 初始化 MPI 运行环境。
• 建立通信环境。
• 通常可以理解为所有 MPI 进程进入 MPI 环境的起点。

函数原型：

int MPI_Init(int *argc, char ***argv);

MPI_Finalize#

MPI_Finalize 用于关闭 MPI 环境并清理资源。

函数原型：

int MPI_Finalize(void);

基本程序结构#

#include <mpi.h>

int main(int argc, char* argv[]) {
    MPI_Init(&argc, &argv);

    /* MPI 程序主体 */

    MPI_Finalize();
    return 0;
}

注意：实际函数名是 MPI_Init 和 MPI_Finalize，大小写要一致。

3.4 通信子、进程数和 rank#

通信子#

通信子（communicator）：一组可以互相发送消息的进程集合。

常用通信子：

MPI_COMM_WORLD

含义：由 MPI_Init 创建，包含用户启动的所有 MPI 进程。

MPI_Comm_size#

获取通信子中的进程总数。

int MPI_Comm_size(MPI_Comm comm, int *size);

示例：

int size;
MPI_Comm_size(MPI_COMM_WORLD, &size);

MPI_Comm_rank#

获取当前进程在通信子中的编号，即 rank。

int MPI_Comm_rank(MPI_Comm comm, int *rank);

示例：

int rank;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);

rank 的作用#

• rank 用于区分不同进程。
• rank 常用于决定每个进程执行什么任务。
• rank 也用于指定消息发送目标或消息来源。

3.5 MPI_Send#

MPI_Send 用于点对点发送消息。

函数原型：

int MPI_Send(
    void *buf,
    int count,
    MPI_Datatype datatype,
    int dest,
    int tag,
    MPI_Comm comm
);

参数：

tag 的作用#

tag 用于区分同一对进程之间的不同消息。

例子：

• 一部分浮点数用于加法，使用 tag = 0。
• 一部分浮点数用于减法，使用 tag = 1。

接收方可以通过 tag 判断收到的消息应该如何处理。

3.6 MPI_Recv#

MPI_Recv 用于点对点接收消息。

函数原型：

int MPI_Recv(
    void *buf,
    int count,
    MPI_Datatype datatype,
    int source,
    int tag,
    MPI_Comm comm,
    MPI_Status *status
);

参数：

MPI_Status#

MPI_Status 至少包含以下常用信息：

如果接收方事先不知道实际收到了多少个数据项，可以用 MPI_Get_count 从 status 中查询。

int MPI_Get_count(
    MPI_Status *status_p,
    MPI_Datatype datatype,
    int *count_p
);

含义：

• status_p：某次 MPI_Recv 返回的状态。
• datatype：接收时使用的数据类型。
• count_p：输出参数，保存实际接收到的数据项个数。

常用 MPI 数据类型#

MPI 通信时必须说明数据类型。count 表示数据项个数，datatype 说明每个数据项是什么类型。

3.7 消息匹配#

一个 MPI_Recv 能否匹配某个 MPI_Send，主要看三项：

source == 发送方 rank
recv_tag == send_tag
recv_comm == send_comm

还需要满足：

• 接收类型和发送类型匹配。
• 接收缓冲区足够大，即 recv_buff_sz >= send_buff_sz。

通配符#

MPI 提供两个接收方通配符：

注意：通配符只能在接收方使用。

3.8 MPI_Send 和 MPI_Recv 的阻塞语义#

MPI_Recv#

MPI_Recv 一定是阻塞的。

含义：

• 如果匹配的消息还没到达，MPI_Recv 会一直等待。
• 除非出错或被取消，否则进程会挂起在接收调用上。

MPI_Send#

MPI_Send 是否阻塞取决于消息大小和 MPI 实现。

常见情况：

所以：MPI_Send 可能立即返回，也可能阻塞。

常见实现里有两种发送机制：

所以不能把普通 MPI_Send 简单理解为“一定阻塞”或“一定非阻塞”。它的返回行为和消息大小、MPI 实现、接收方状态都有关。

消息不可超越#

MPI 要求同一发送进程连续发送给同一接收进程的消息不能乱序。

也就是说：

• 同一个进程连续发送的几条消息，必须按发送顺序到达。
• 不同发送进程之间的消息没有这个顺序保证。

例子：

进程 1 连续发送 A、B 给进程 0
进程 0 不会先收到 B 再收到 A

但如果：

进程 1 发送 A
进程 2 发送 B

进程 0 可能先收到 A，也可能先收到 B。

MPI_Ssend#

MPI_Ssend 是同步发送（synchronous send）。

额外的 s 表示 synchronous。它和 MPI_Send 的参数相同，但语义更严格：

• MPI_Ssend 保证阻塞。
• 只有当匹配的接收操作已经开始后，MPI_Ssend 才能返回。
• 它不会像普通 MPI_Send 那样因为消息较小、被复制到内部缓冲区就提前返回。

函数原型：

int MPI_Ssend(
    void *msg_buf_p,
    int msg_size,
    MPI_Datatype msg_type,
    int dest,
    int tag,
    MPI_Comm communicator
);

和 MPI_Send 的关系：

用途：

• 可以用来检查程序通信顺序是否安全。
• 如果把 MPI_Send 换成 MPI_Ssend 后程序挂起或崩溃，说明原程序可能依赖了 MPI 的内部缓冲区。
• 若使用 MPI_Ssend 后程序仍能正常运行，通常说明原来的点对点通信顺序更安全。
• MPI_Ssend 的参数和 MPI_Send 相同，所以常见调试方式是直接把 MPI_Send 临时替换成 MPI_Ssend。

3.9 集合通信#

集合通信是多个进程共同参与的通信操作。和点对点通信不同，集合通信通常要求通信子中的所有相关进程都调用同一个集合通信函数。

MPI_Reduce#

MPI_Reduce 用于把多个进程的数据按某种操作归约，并把结果存到指定的 root 进程。

常见用途：求和、求最大值、求最小值等。

示例：

MPI_Reduce(
    &local_sum,     /* 每个进程提供的本地数据 */
    &total_sum,     /* 归约结果，只在 root 进程有效 */
    1,              /* 数据个数，这里是 1 个 double */
    MPI_DOUBLE,     /* 数据类型 */
    MPI_SUM,        /* 归约操作：求和 */
    0,              /* root 进程编号，结果放到 rank 0 */
    MPI_COMM_WORLD  /* 通信子 */
);

参数含义：

MPI 预定义归约算子#

例子：4 个进程分别有：

rank 0: local_sum = 1.5
rank 1: local_sum = 2.0
rank 2: local_sum = 3.5
rank 3: local_sum = 4.0

执行 MPI_Reduce 后，只有 rank 0 上：

total_sum = 1.5 + 2.0 + 3.5 + 4.0;  /* 11.0 */

其他进程上的 total_sum 不保存最终归约结果。

树形结构通信#

集合通信指的是通信子中所有进程共同参与的通信函数。MPI_Send 和 MPI_Recv 是点对点通信，不属于集合通信。

MPI_Reduce 内部通常不会简单地让所有进程都直接把结果发给 0 号进程，因为这样 root 进程需要接收和计算太多次。

如果 comm_sz = 1024：

• 简单集中到 0 号进程：0 号进程需要接收并计算 1023 次。
• 树形结构归约：大约只需要 log2(1024) = 10 轮通信和计算。

树形归约示意：

核心思想：

• 每一轮把相邻进程或局部结果两两合并。
• 合并后的部分和继续向上归约。
• 最终结果到达 root 进程。
• 这样能减少 root 进程的通信压力。

Reduce 和 Scan 的数据流对比：

区别：

• MPI_Reduce：把所有进程的数据归约到一个 root 进程。
• MPI_Scan：做前缀归约，每个进程得到从 rank 0 到自己这一段的部分归约结果。

集合通信与点对点通信的区别#

集合通信和点对点通信的调用规则不同，不能把它们当成一类操作来匹配。

1. 所有进程必须调用同一个集合通信函数#

通信子中的所有进程==必须调用相同的集合通信函数==。

错误例子：

rank 0 调用 MPI_Reduce
rank 1 调用 MPI_Recv

这种程序是错误的，可能导致挂起或崩溃。

2. 集合通信参数必须兼容#

每个进程传给集合通信的关键参数必须一致或兼容。

以 MPI_Reduce 为例：

• 所有进程必须使用相同的通信子。
• 所有进程必须使用相同的归约操作。
• 所有进程必须指定相同的 root。
• 数据类型和数据个数必须匹配。

如果一个进程把 root 设为 0，另一个进程把 root 设为 1，程序就是错误的。

3. 非 root 进程也要传入对应参数#

在 MPI_Reduce 中，接收缓冲区 recvbuf 只在 root 进程上真正使用。

但所有进程仍然需要调用同一个函数，并传入对应位置的参数。非 root 进程上的 recvbuf 不保存最终结果，通常可以理解为无效或被忽略。

4. 集合通信不靠 tag 匹配#

点对点通信通过以下信息匹配：

source
tag
comm

集合通信不使用 tag。它的匹配主要由以下因素决定：

• 通信子 comm
• 调用的集合函数类型
• 调用顺序

因此，如果同一个通信子里连续调用两次 MPI_Reduce，MPI 会把所有进程的第一次 MPI_Reduce 匹配在一起，把第二次 MPI_Reduce 匹配在一起。

多次 MPI_Reduce 调用示例#

假设所有进程都执行两次 MPI_Reduce，并且通信子相同：

MPI_Reduce(&a, &b, 1, MPI_INT, MPI_SUM, 0, comm);
MPI_Reduce(&c, &d, 1, MPI_INT, MPI_SUM, 0, comm);

则：

• 第一次调用只会和其他进程的第一次调用匹配。
• 第二次调用只会和其他进程的第二次调用匹配。
• 即使变量名不同，MPI 也不根据变量名匹配，只根据集合通信调用顺序匹配。

所以集合通信中，所有进程必须以相同顺序调用相同的集合通信函数。

不要混用输入和输出缓冲区#

对于 MPI_Reduce，通常不应该把发送缓冲区和接收缓冲区写成同一个地址，例如：

MPI_Reduce(&x, &x, 1, MPI_DOUBLE, MPI_SUM, 0, comm);

这种写法可能导致结果不可预测，甚至是非法的。

更安全的写法是：

MPI_Reduce(&local_x, &global_x, 1, MPI_DOUBLE, MPI_SUM, 0, comm);

其中：

• local_x：每个进程自己的输入数据。
• global_x：root 进程保存归约结果。

MPI_Bcast#

MPI_Bcast 用于广播：把 root 进程上的一份数据发送给通信子中的所有进程。

它可以看作是树形归约通信方向的“反向操作”：归约是把多个进程的数据汇总到 root，广播是把 root 的数据分发给所有进程。

函数原型：

int MPI_Bcast(
    void *data_p,
    int count,
    MPI_Datatype datatype,
    int source_proc,
    MPI_Comm comm
);

参数：

示例：

MPI_Bcast(a_p, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD);
MPI_Bcast(b_p, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD);
MPI_Bcast(n_p, 1, MPI_INT,    0, MPI_COMM_WORLD);

含义：

• rank 0 上的 a_p、b_p、n_p 是源数据。
• 调用后，通信子中所有进程都得到相同的 a、b、n。

树形广播示意：

注意：

• MPI_Bcast 是集合通信，通信子中的所有进程都必须调用。
• 所有进程传入的 count、datatype、source_proc、comm 必须匹配。
• 与手写多次 MPI_Send 相比，MPI_Bcast 通常更简洁，也可能由 MPI 库用树形结构优化。

MPI_Scatter#

MPI_Scatter 用于分散：root 进程把一整块数据切成多段，分别发送给通信子中的各个进程。

可以理解为：

root 上的大数组 -> 每个进程拿到其中一小段

典型用途：

• root 进程读入完整向量。
• 每个进程只处理自己负责的子向量。
• 避免把完整向量复制到所有进程，节省内存和通信量。

函数原型：

int MPI_Scatter(
    void *send_buf_p,
    int send_count,
    MPI_Datatype send_type,
    void *recv_buf_p,
    int recv_count,
    MPI_Datatype recv_type,
    int src_proc,
    MPI_Comm comm
);

重点参数：

注意：send_count 不是 send_buf_p 中的总数据量，而是每个进程收到多少个元素。

如果通信子中有 comm_sz 个进程，MPI_Scatter 会把 send_buf_p 指向的数据分成 comm_sz 个片段：

第 1 个片段 -> rank 0
第 2 个片段 -> rank 1
第 3 个片段 -> rank 2
...

所以 root 上的发送缓冲区至少需要容纳：

send_count * comm_sz

个元素。

例子：有 comm_sz 个进程，向量总长度为 n，则每个进程收到：

local_n = n / comm_sz

调用时通常类似：

MPI_Scatter(x, local_n, MPI_DOUBLE,
            local_x, local_n, MPI_DOUBLE,
            0, MPI_COMM_WORLD);

MPI_Bcast、MPI_Scatter 和 MPI_Gather 的数据方向对比：

MPI_Gather#

MPI_Gather 用于收集：每个进程把自己的一段数据发送给 root，root 把这些片段按 rank 顺序拼成完整数据。

可以理解为：

每个进程的一小段 -> root 上的大数组

它和 MPI_Scatter 方向相反：

函数原型：

int MPI_Gather(
    void *send_buf_p,
    int send_count,
    MPI_Datatype send_type,
    void *recv_buf_p,
    int recv_count,
    MPI_Datatype recv_type,
    int dest_proc,
    MPI_Comm comm
);

重点参数：

注意：recv_count 是从每个进程接收多少项，不是 root 最终接收到的总项数。最终总量通常是：

recv_count * comm_sz

root 上的 recv_buf_p 会按进程 rank 顺序存放结果：

rank 0 的数据 -> 第 1 块
rank 1 的数据 -> 第 2 块
rank 2 的数据 -> 第 3 块
...

MPI_Gather 和 MPI_Scatter 的重点都是 count 参数的含义：

• MPI_Scatter 的 send_count：root 发给每个进程多少个元素。
• MPI_Gather 的 recv_count：root 从每个进程收多少个元素。
• 它们都不是 root 缓冲区里的总元素数。

MPI_Allgather#

MPI_Allgather 用于全局聚集：每个进程发送一段数据，并且每个进程最终都得到所有进程的数据。

可以理解为：

MPI_Allgather = MPI_Gather + MPI_Bcast

也就是说，它先把各进程的数据聚集成完整结果，再让所有进程都拥有这份完整结果。实际 MPI 实现不一定真的分两步执行，但语义上可以这样理解。

区别：

函数原型：

int MPI_Allgather(
    void *send_buf_p,
    int send_count,
    MPI_Datatype send_type,
    void *recv_buf_p,
    int recv_count,
    MPI_Datatype recv_type,
    MPI_Comm comm
);

和 MPI_Gather 相比，MPI_Allgather 没有 root 参数，因为所有进程都会得到完整结果。

例子：4 个进程中：

int sendval = rank + 1;
int recvbuf[4];

MPI_Allgather(&sendval, 1, MPI_INT,
              recvbuf, 1, MPI_INT,
              MPI_COMM_WORLD);

执行后，每个进程的：

recvbuf = [1, 2, 3, 4]

注意：

• 所有进程都要提供 recvbuf。
• recvbuf 大小通常至少是 recv_count * comm_sz。
• 和 MPI_Gather 不同，MPI_Allgather 没有 dest_proc/root 参数，因为结果不是只发给某一个进程，而是发给所有进程。

MPI_Allgather 和 MPI_Alltoall 的语义对比：

MPI_Allgather 的常见实现之一是环算法：

环算法的直观过程：

• 每个进程一开始有自己的本地数据。
• 第 0 轮发送自己的数据。
• 之后每一轮把上一轮收到的数据继续传给右侧进程，同时从左侧进程接收新数据。
• 经过 p - 1 轮后，每个进程都拥有所有进程的数据。

另一类实现是递归倍增/蝶式通信：

它每一轮和更远距离的伙伴进程交换已有数据，轮数约为 log2(p)。实际 MPI 库会根据消息大小、进程数和网络结构选择实现方式。

MPI_Allreduce#

MPI_Allreduce 会把归约结果发送给通信子中的所有进程。

如果希望所有进程都得到总和，应使用：

MPI_Allreduce(
    &local_sum,
    &total_sum,
    1,
    MPI_DOUBLE,
    MPI_SUM,
    MPI_COMM_WORLD
);

区别：

全局和的两种实现模式#

全局和的目标是：每个进程一开始只有自己的局部值，最后所有进程都得到全局求和结果。

示例初始值：

rank 0:  5
rank 1:  2
rank 2: -1
rank 3: -3
rank 4:  6
rank 5:  5
rank 6: -7
rank 7:  2

总和为：

5 + 2 - 1 - 3 + 6 + 5 - 7 + 2 = 9

模式一：先归约，再分发#

第一阶段：树形归约，把所有值逐步加到 root 进程。

第二阶段：root 再把结果广播给所有进程。

特点：

• 思路简单：先做 Reduce，再做 Broadcast。
• root 先得到最终结果，然后再分发给其他进程。
• 可理解为 MPI_Allreduce = MPI_Reduce + MPI_Bcast 的一种实现思路。

模式二：蝶式模式#

蝶式模式中，每一轮进程和一个“伙伴进程”交换当前部分和，交换后双方都更新自己的结果。

8 个进程需要 log2(8) = 3 轮：

第 1 轮：距离 1 的进程交换
(0,1), (2,3), (4,5), (6,7)

第 2 轮：距离 2 的进程交换
(0,2), (1,3), (4,6), (5,7)

第 3 轮：距离 4 的进程交换
(0,4), (1,5), (2,6), (3,7)

图示：

特点：

• 每一轮所有进程都参与交换和计算。
• 每个进程最终都直接得到全局结果。
• 不需要先集中到 root 再广播。
• 适合实现 MPI_Allreduce 这类所有进程都需要结果的集合通信。

3.10 MPI 程序中的 I/O 处理#

基本规则#

在 MPI 程序中：

• 输出：所有进程都可以访问 stdout，但输出顺序不可预测。
• 输入：通常只有 0 号进程访问 stdin。

因此常见做法是：

1. 0 号进程从标准输入读取数据。
2. 0 号进程把输入数据发送给其他进程。
3. 其他进程通过 MPI_Recv 接收这些数据。

示例：0 号进程读入并分发参数#

if (my_rank == 0) {
    printf("Enter a, b, and n\n");
    scanf("%lf %lf %d", a_p, b_p, n_p);

    for (dest = 1; dest < comm_sz; dest++) {
        MPI_Send(a_p, 1, MPI_DOUBLE, dest, 0, MPI_COMM_WORLD);
        MPI_Send(b_p, 1, MPI_DOUBLE, dest, 0, MPI_COMM_WORLD);
        MPI_Send(n_p, 1, MPI_INT,    dest, 0, MPI_COMM_WORLD);
    }
} else {
    MPI_Recv(a_p, 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD,
             MPI_STATUS_IGNORE);
    MPI_Recv(b_p, 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD,
             MPI_STATUS_IGNORE);
    MPI_Recv(n_p, 1, MPI_INT,    0, 0, MPI_COMM_WORLD,
             MPI_STATUS_IGNORE);
}

代码含义#

• my_rank == 0：
  • 0 号进程负责提示用户输入。
  • 读取 a、b、n。
  • 通过循环把三个参数发送给 rank 1 到 comm_sz - 1 的所有进程。
• my_rank != 0：
  • 非 0 号进程不访问 stdin。
  • 它们分别从 0 号进程接收 a、b、n。

图示#

注意点#

• count 是数据项个数，不是字节数。
• a_p 和 b_p 是 double*，所以使用 MPI_DOUBLE。
• n_p 是 int*，所以使用 MPI_INT。
• MPI_STATUS_IGNORE 表示忽略接收状态。
• 这里三条消息都使用 tag = 0，能够正确接收是因为同一发送方到同一接收方的消息不会乱序。

更简洁的替代方案#

如果所有进程都需要同样的输入数据，更常见的写法是使用广播：

MPI_Bcast(a_p, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD);
MPI_Bcast(b_p, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD);
MPI_Bcast(n_p, 1, MPI_INT,    0, MPI_COMM_WORLD);

MPI_Bcast 表示：root 进程把数据广播给通信子中的所有进程。

3.11 MPI 计时与同步#

MPI_Wtime#

MPI_Wtime 用于获取当前进程的墙上时钟时间（wall time），单位是秒，返回值类型是 double。

它常用于测量某段 MPI 程序的运行时间：

double start, end;

start = MPI_Wtime();

do_work();

end = MPI_Wtime();

printf("Elapsed time = %f seconds\n", end - start);

注意：

• MPI_Wtime() 返回的是当前进程看到的时间。
• 并行程序中各进程开始执行某段代码的时刻可能不同。
• 如果要测量一段并行计算的整体耗时，通常要先同步，再开始计时。

MPI_Barrier#

MPI_Barrier 是屏障同步函数：

int MPI_Barrier(MPI_Comm comm);

含义：

• 通信子 comm 中的所有进程都必须到达这个调用点。
• 只有所有进程都到达后，大家才能继续往下执行。
• 如果有进程还没到，其他已经到达的进程会阻塞等待。

典型用途：同步后再测量并行区域时间。

MPI_Barrier(MPI_COMM_WORLD);
double start = MPI_Wtime();

do_parallel_work();

MPI_Barrier(MPI_COMM_WORLD);
double end = MPI_Wtime();

if (rank == 0) {
    printf("Parallel section took %f seconds\n", end - start);
}

为什么前后都加 MPI_Barrier：

• 前面的 MPI_Barrier：保证所有进程都准备好后再开始计时。
• 后面的 MPI_Barrier：保证所有进程都完成并行段后再停止计时。
• 这样测到的时间更接近整个并行计算段的真实耗时。

3.12 MPI 派生数据类型#

MPI 的基本数据类型只能描述连续的 int、double、char 等数据。实际程序里经常需要发送更复杂的内存布局，例如矩阵的一列、结构体中的几个字段，或者二维数组中的一个子块。

派生数据类型的作用是：告诉 MPI“我要发送的数据在内存中怎样分布”，让 MPI 直接按这个布局通信，而不需要程序员手动把数据打包到临时数组。

典型使用流程：

MPI_Datatype new_type;

/* 1. 创建派生类型 */
/* MPI_Type_vector / MPI_Type_indexed / MPI_Type_create_struct 等 */

/* 2. 提交类型，之后才能用于通信 */
MPI_Type_commit(&new_type);

/* 3. 在 Send/Recv 或集合通信中使用 */
MPI_Send(buf, 1, new_type, dest, tag, comm);

/* 4. 不再使用后释放 */
MPI_Type_free(&new_type);

MPI_Type_contiguous#

MPI_Type_contiguous 用来描述一段连续的数据，相当于把多个相同类型的数据组合成一个新类型。

int MPI_Type_contiguous(
    int count,
    MPI_Datatype old_type,
    MPI_Datatype *new_type_p
);

例子：把 4 个连续的 MPI_DOUBLE 看成一个新类型。

MPI_Type_vector#

MPI_Type_vector 用来描述“重复出现的等长块”，每个块之间有固定间隔。它常用于发送矩阵的一列。

int MPI_Type_vector(
    int count,
    int blocklength,
    int stride,
    MPI_Datatype old_type,
    MPI_Datatype *new_type_p
);

参数含义：

示意图：

MPI_Type_indexed#

MPI_Type_indexed 比 vector 更灵活：每个块的长度和起始位置都可以不同。

int MPI_Type_indexed(
    int count,
    int blocklengths[],
    int displacements[],
    MPI_Datatype old_type,
    MPI_Datatype *new_type_p
);

适合描述不规则位置的数据。

MPI_Type_create_subarray#

MPI_Type_create_subarray 用来描述多维数组中的一个子数组。它常用于矩阵块划分，例如从一个二维矩阵里发送某个矩形区域。

MPI_Type_create_struct#

MPI_Type_create_struct 用来描述由不同类型字段组成的数据布局。例如一个结构体里既有 int，也有 double，并且只想发送其中某些字段。

结构体填充和 extent#

C 结构体中可能存在内存对齐填充。也就是说，字段之间或结构体末尾可能有一些程序员没有显式声明的空字节。

如果直接把结构体当成连续内存发送，可能会把不需要的填充字节或相邻字段一起发送出去。派生数据类型可以只描述真正需要通信的字段。

还有一个容易混淆的概念是 extent：它表示 MPI 在连续排列多个该类型对象时，相邻对象起点之间的跨度。结构体有填充时，extent 可能大于字段本身的有效数据长度。

必要时可以用 MPI_Type_create_resized 调整派生类型的 extent。

核心记忆：

• 派生数据类型描述的是内存布局，不是新建一份数据。
• 创建后必须 MPI_Type_commit，不用后要 MPI_Type_free。
• 发送非连续数据时，派生类型通常比手动打包更清晰，也更不容易出错。

3.13 MPI 死锁、Sendrecv 和非阻塞通信#

点对点通信中的死锁#

如果两个进程都先执行阻塞发送，再执行接收，就可能互相等待。

典型错误模式：

rank 0: MPI_Send(... rank 1 ...); MPI_Recv(... rank 1 ...);
rank 1: MPI_Send(... rank 0 ...); MPI_Recv(... rank 0 ...);

当消息较大或使用同步发送时，两个进程都在等对方先接收，程序就可能卡住。

解决方式一：调整发送接收顺序#

让一边先发送后接收，另一边先接收后发送，就能避免两边同时卡在发送上。

解决方式二：MPI_Sendrecv#

MPI_Sendrecv 把一次发送和一次接收合成一个调用，适合相邻进程交换数据。

int MPI_Sendrecv(
    const void *sendbuf,
    int sendcount,
    MPI_Datatype sendtype,
    int dest,
    int sendtag,
    void *recvbuf,
    int recvcount,
    MPI_Datatype recvtype,
    int source,
    int recvtag,
    MPI_Comm comm,
    MPI_Status *status
);

它的价值是：程序员不用手动安排“谁先发、谁先收”，MPI 会处理这个交换过程。

缓冲发送#

MPI_Bsend 是缓冲发送。它依赖用户提供的缓冲区，发送数据可以先被拷贝到这个缓冲区中。

注意：缓冲发送不是首选的死锁解决方案。更常用的是重新安排通信顺序、使用 MPI_Sendrecv，或者使用非阻塞通信。

非阻塞通信#

非阻塞通信的核心是：函数调用可以先返回，通信在后台继续进行。

常用函数：

MPI_Isend(..., MPI_Request *request);
MPI_Irecv(..., MPI_Request *request);

I 表示 immediate。调用返回只表示“通信请求已经发起”，不表示通信已经完成。

因此必须配合等待或测试函数：

MPI_Wait(&request, &status);
MPI_Test(&request, &flag, &status);
MPI_Waitall(count, requests, statuses);

最重要的规则：

• 对 MPI_Isend，在通信完成前，不要修改或释放发送缓冲区。
• 对 MPI_Irecv，在通信完成前，不要读取接收缓冲区中的结果。
• 是否完成要看 MPI_Wait / MPI_Test 等函数。

MPI_Request 可以理解成一次未完成通信的“句柄”：

多个非阻塞通信可以一起等待：

也可以等待其中任意一个或一部分完成：

一句话总结：

阻塞通信：调用返回时，相关通信条件已经满足。
非阻塞通信：调用先返回，但之后必须 wait/test，才能确认通信完成。

第 4 章 使用 Pthreads 进行共享内存编程#

4.1 Pthreads 概述#

Pthreads 是什么#

Pthreads 是 POSIX 线程库，用于在共享内存系统中编写多线程程序。

和 MPI 的主要区别：

核心区别：

MPI：进程之间不共享内存，所以靠消息传递。
Pthreads：线程之间共享内存，所以靠同步保护。

MPI 中，每个进程像独立的执行单元，有自己的内存。要交换数据，必须显式调用：

MPI_Send(...);
MPI_Recv(...);

Pthreads 中，多个线程在同一个进程内运行，可以直接访问同一个共享变量。因此重点不是发送消息，而是防止多个线程同时乱改共享数据：

pthread_mutex_lock(&mutex);
/* 临界区 */
pthread_mutex_unlock(&mutex);

性能瓶颈也不同：

两者都可以使用 SPMD 思路：同一份程序由多个执行单元运行。区别是 MPI 通常用 rank 区分进程，Pthreads 通常用线程编号区分线程。

共享内存系统适合在同一台机器上使用多个线程，规模通常不会太大，因为多个核心访问共享内存时会受到内存带宽、总线、缓存一致性等因素限制。

Pthreads 程序的核心问题#

Pthreads 的重点不是“如何传消息”，而是：

• 线程之间如何通信：通过访问共享变量。
• 如何避免写写冲突：避免多个线程同时写同一个共享变量。
• 如何构造临界区：把一次只能由一个线程执行的代码包起来。
• 如何表达锁：使用互斥量 pthread_mutex_t。

Pthreads 程序也经常采用 SPMD 思路：所有线程运行同一个线程函数，但根据线程编号处理不同数据。

4.2 Hello World 示例#

编译与运行#

编译 Pthreads 程序时需要加 -pthread：

gcc -pthread hello_pthread.c -o hello_pthread
./hello_pthread

代码#

#include <stdio.h>
#include <pthread.h>

void* say_hello(void* arg) {
    int thread_id = *(int*)arg;
    printf("Hello from thread %d!\n", thread_id);
    return NULL;
}

int main() {
    const int NUM_THREADS = 4;
    pthread_t threads[NUM_THREADS];
    int ids[NUM_THREADS];

    for (int i = 0; i < NUM_THREADS; i++) {
        ids[i] = i;
        pthread_create(&threads[i], NULL, say_hello, (void*) &ids[i]);
    }

    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_join(threads[i], NULL);
    }

    printf("All threads finished. Goodbye!\n");
    return 0;
}

如果线程数运行时才确定，可以动态分配线程对象数组：

pthread_t* threads = malloc(num_threads * sizeof(pthread_t));

4.3 pthread_create：启动线程#

在启动线程前，需要先创建线程对象：

pthread_t thread;

每个线程对应一个 pthread_t 对象。创建线程使用：

int pthread_create(
    pthread_t* thread,
    const pthread_attr_t* attr,
    void* (*start_routine)(void*),
    void* arg
);

参数：

线程函数的固定形式通常是：

void* thread_func(void* arg);

如果要传多个参数，常见做法是定义结构体，把结构体指针作为 arg 传入。

4.4 pthread_join：等待线程结束#

pthread_join 用来等待一个线程结束：

int pthread_join(pthread_t thread, void** retval);

重点：

• pthread_join 不会主动停止线程。
• 它会阻塞调用它的线程，直到目标线程正常返回。
• 常用于主线程等待所有子线程执行完毕。

典型写法：

for (int i = 0; i < NUM_THREADS; i++) {
    pthread_join(threads[i], NULL);
}

如果主线程不等待子线程，主线程可能先结束，导致整个进程退出，子线程还没来得及完成。

4.5 共享变量、冲突和临界区#

线程如何通信#

Pthreads 中，同一个进程内的多个线程共享地址空间，因此线程可以直接访问同一批全局变量、堆内存和静态变量。

也就是说，线程之间的通信通常是隐式的：

线程 A 写共享变量
线程 B 读共享变量

这比 MPI 的显式发送和接收更方便，但也更容易出错。

写写冲突#

如果多个线程同时写同一个共享变量，就可能出现写写冲突。

例子：

sum += my_val;

这行代码看起来是一条语句，但底层通常包含：

1. 从内存读取 sum。
2. 加上 my_val。
3. 把结果写回 sum。

如果两个线程同时执行，就可能都读到旧值，最后其中一个写入覆盖另一个写入，导致结果错误。

竞争条件#

竞争条件：多个线程同时访问某个共享资源，并且程序结果依赖于线程执行的先后顺序。

例子：共享变量 x 初始值为 0，两个线程几乎同时执行：

y = compute();   /* Thread 0: y = 1; Thread 1: y = 2 */
x = x + y;

理想情况下，最终应该得到：

x = 1 + 2 = 3

但实际执行可能是：

1. 线程 0 读到 x = 0，准备加 y = 1。
2. 线程 1 也读到 x = 0，准备加 y = 2。
3. 线程 0 写回 x = 1。
4. 线程 1 写回 x = 2，覆盖线程 0 的结果。

最终得到 x = 2，而不是 x = 3。这说明 x = x + y 不是原子操作。

临界区#

临界区：一次只能允许一个线程执行的代码区域。

通常，临界区里面放的是更新共享变量的操作。

对于共享变量更新，常见做法是把更新语句放进临界区：

lock();
sum += my_val;
unlock();

临界区越大，串行化越严重；临界区越小，程序通常越容易保持并行性能。

临界区要解决的问题是：让多个线程对共享变量的访问变成互斥访问，从而避免多个线程同时修改同一个共享变量。

互斥锁#

忙等待会持续占用 CPU，因此更常用的方式是使用互斥锁和信号量。

互斥锁（mutex）是一种线程同步机制，用来保证同一时刻只有一个线程可以进入临界区。

Pthreads 使用 pthread_mutex_t 表示互斥量：

pthread_mutex_t mutex;

初始化#

使用互斥锁前需要初始化：

int pthread_mutex_init(
    pthread_mutex_t* mutex_p,
    const pthread_mutexattr_t* attr_p
);

一般情况下，属性参数传 NULL：

pthread_mutex_init(&lock, NULL);

上锁#

进入临界区前调用：

int pthread_mutex_lock(pthread_mutex_t* mutex_p);

含义：

• 如果锁空闲，当前线程获得锁并继续执行。
• 如果锁已被其他线程持有，当前线程阻塞等待。

解锁#

离开临界区后调用：

int pthread_mutex_unlock(pthread_mutex_t* mutex_p);

含义：释放锁，让其他等待线程有机会进入临界区。

销毁#

互斥锁不再使用时，应销毁：

int pthread_mutex_destroy(pthread_mutex_t* mutex_p);

典型使用方式#

pthread_mutex_t lock;
pthread_mutex_init(&lock, NULL);

pthread_mutex_lock(&lock);

/* 临界区 */
sum += my_val;

pthread_mutex_unlock(&lock);

pthread_mutex_destroy(&lock);

使用锁的目的不是提高速度，而是保证共享变量更新的正确性。

互斥锁的局限：不能保证执行顺序#

互斥锁只能保证：

同一时刻只有一个线程进入临界区

但它不能保证：

线程按照指定顺序进入临界区

所以，如果临界区里的操作对顺序敏感，仅使用互斥锁仍然可能得到不同结果。

典型例子：多个线程各自生成一个矩阵，然后把它乘到共享结果矩阵 product_mat 上。

void* Thread_work(void* rank) {
    long my_rank = (long) rank;
    matrix_t my_mat = Allocate_matrix(n);
    Generate_matrix(my_mat);

    pthread_mutex_lock(&mutex);
    Multiply_matrix(product_mat, my_mat);
    pthread_mutex_unlock(&mutex);

    Free_matrix(&my_mat);
    return NULL;
}

互斥锁可以保证一次只有一个线程执行：

Multiply_matrix(product_mat, my_mat);

但问题是：不同线程进入临界区的顺序由操作系统调度决定。

矩阵乘法不满足交换律：

A * B * C != C * B * A

因此，线程执行乘法的顺序不同，最终的 product_mat 可能不同。

结论：互斥锁适合保护共享变量，避免同时写；但如果操作本身对顺序敏感，还需要额外机制规定线程执行顺序。

信号量#

有些同步模式不是简单的“只能一个线程进临界区”，而是“一个线程要等另一个线程完成某些操作后才能继续”。这种情况更适合使用信号量。

使用信号量需要引入：

#include <semaphore.h>

信号量和互斥锁最大的区别：

对于当前学习目的，最关键的区别是：信号量没有所有权。

一句话记忆：

• mutex：谁 lock，通常谁 unlock；重点是保护同一段临界区。
• semaphore：任何线程都可以 post；重点是通知另一个线程可以继续。

也就是说：

• 主线程可以把所有信号量初始化为 0，表示这些事件一开始都尚未发生。
• 任意线程都可以对任意信号量执行 sem_wait。
• 任意线程也可以对任意信号量执行 sem_post。
• 因此，一个线程可以通过 sem_post 唤醒另一个正在等待该信号量的线程。

更准确地说，信号量的重点不是“加锁”，而是表达：

某个事件已经发生，等待这个事件的线程可以继续了

这和互斥锁不同：互斥锁通常强调“==谁加锁，谁解锁==”。信号量更像一个可被不同线程共同操作的通知器或计数器。

sem_init：初始化#

int sem_init(
    sem_t* semaphore_p,
    int shared,
    unsigned initial_val
);

参数：

• semaphore_p：信号量对象地址。
• shared：是否用于进程间共享。通常写 0，表示用于同一进程内的线程之间。
• initial_val：信号量初值。常见地，0 表示事件尚未发生，等待线程需要阻塞。

例子：

sem_t sem;
sem_init(&sem, 0, 0);

当 initial_val = 0 时，先执行 sem_wait 的线程会阻塞，直到其他线程执行 sem_post。

sem_wait：等待#

int sem_wait(sem_t* semaphore_p);

含义：

• 如果信号量值 > 0，将其减 1，然后线程继续执行。
• 如果信号量值 = 0，线程阻塞，直到其他线程执行 sem_post 发出通知。

可以理解为：

等待某个事件发生；如果还没发生，就睡眠等待

sem_post：通知/释放#

int sem_post(sem_t* semaphore_p);

含义：

• 将信号量值加 1。
• 如果有线程正在 sem_wait 中阻塞，可能唤醒其中一个。

可以理解为：

宣布某个事件已经发生；如果有人在等，就叫醒一个

sem_destroy：销毁#

int sem_destroy(sem_t* semaphore_p);

信号量不再使用时，应调用 sem_destroy 销毁。

典型用法：控制线程先后顺序#

sem_t sem;
sem_init(&sem, 0, 0);

/* 线程 A */
sem_wait(&sem);
do_after_B();

/* 线程 B */
do_something();
sem_post(&sem);

/* 不再使用时 */
sem_destroy(&sem);

总结：

• 信号量的重点是表达“事件发生了，可以继续”。
• 它比互斥锁更适合控制线程之间的先后顺序。
• 初值为 0 时，表示事件还没发生，等待线程会阻塞。
• sem_post 可以由另一个线程调用，用来通知等待线程继续执行。
• 初值为 1 的二进制信号量可以模拟互斥锁，但这不是这里最重要的用法。

忙等待、互斥锁和信号量对比#

这三者都可以用于协调线程，但解决问题的重点不同。

本节最重要的主线不是“这三个工具分别叫什么”，而是：

它们能不能控制线程之间的执行顺序？

如果只是避免多个线程同时进入临界区，用互斥锁通常就够了；如果要求线程 A 做完后线程 B 才能继续，就需要能表达先后关系的机制。

一句话记忆：

忙等待：一直问“轮到我了吗？”
互斥锁：保护“这段代码一次只能一个线程执行”。
信号量：通知“某件事发生了，等待者可以继续”。

最终记忆：

互斥锁解决“不能同时执行”的问题；
信号量更适合解决“必须按某个顺序执行”的问题；
忙等待也能做顺序控制，但代价是一直占用 CPU。

栅栏#

栅栏（barrier）是一个同步点：所有线程都必须到达这里，任何线程才允许继续往后执行。

可以把栅栏理解成“阶段分界线”：

线程 0: 做 A --- 到达栅栏 | 等待 | 做 B
线程 1: 做 A --------- 到达栅栏 | 做 B
线程 2: 做 A -- 到达栅栏  | 等待 | 做 B

只有最后一个线程也到达栅栏后，所有线程才一起越过栅栏，进入下一阶段。

常见用途：

和互斥锁的区别：

重要风险：如果某个线程永远到不了栅栏，其他线程会一直等在那里，程序就会卡住。因此，栅栏适合用于“所有线程都会执行到这里”的阶段同步。

条件变量#

条件变量（condition variable）用于让线程在某个条件尚未满足时睡眠等待，等其他线程改变条件后再被唤醒。

典型调用：

pthread_cond_wait(&cond_var, &mutex);

它不是“拿着锁睡觉”。这个函数会在内部原子地完成几件事：

1. 把当前线程放进 cond_var 的等待队列。
2. ==释放 mutex==，让其他线程有机会修改共享状态。
3. 让当前线程睡眠，不再占用 CPU 忙等。
4. 被唤醒后，返回之前会重新获得 mutex。

为什么必须释放 mutex：如果等待线程一直拿着锁睡眠，其他线程就无法进入临界区修改条件，也就无法唤醒它。

通常写法：

pthread_mutex_lock(&mutex);
while (!condition_is_true) {
    pthread_cond_wait(&cond_var, &mutex);
}
/* 条件已经满足，继续处理共享数据 */
pthread_mutex_unlock(&mutex);

注意：这里通常用 while，不是 if。因为线程被唤醒后，条件不一定仍然成立，需要重新检查。

读写锁#

读写锁（read-write lock）适合读多写少的共享资源。

它允许多个线程同时读共享资源，但只允许一个线程写；并且写操作进行时，其他线程不能读也不能写。

锁状态：

初始化和销毁：

pthread_rwlock_t rwlock;

pthread_rwlock_init(&rwlock, NULL);
pthread_rwlock_destroy(&rwlock);

加读锁：

pthread_rwlock_rdlock(&rwlock);

• 如果当前没有写锁，就可以成功加读锁。
• 多个线程可以同时持有读锁。

加写锁：

pthread_rwlock_wrlock(&rwlock);

• 只有当前没有其他线程持有读锁或写锁时，才会成功。
• 写锁是独占访问。

解锁：

pthread_rwlock_unlock(&rwlock);

读锁和写锁都用同一个 pthread_rwlock_unlock 解锁。

一句话记忆：

读读可以并发，写写不能并发，读写也不能并发。

多线程链表操作#

链表的主要操作可以分为两类：

• 读操作：查找、遍历，不修改链表结构。
• 写操作：插入、删除，会修改指针。

因为不能让多个线程同时修改同一个指针，所以链表并发访问需要同步。

常见加锁方式：

使用读写锁时：

• 多个查找线程可以同时持有读锁，一起读链表。
• 插入或删除线程需要写锁，写锁期间不允许其他线程读或写。

效率结论：

• 当读操作很多、写操作较少时，读写锁通常比“整个链表加一把互斥锁”更高效。
• 当写操作较多时，读写锁的优势会变小，通常只比整个链表加锁快一点。
• 每个节点单独加锁看起来更细粒度，但锁操作太多，而且每个节点都要额外存锁，通常代价最大。

线程安全性#

线程安全：一段代码或一个函数在多线程环境中被并发调用时，仍然能得到正确结果，不会因为共享状态被互相覆盖而出错。

判断线程安全时，不能只看自己写的代码，还要看调用的库函数是否线程安全。

例子：多个线程共同读取文本，每个线程读一行，再把这一行拆成单词。

读输入可以用信号量保护：

sem_wait(&sems[my_rank]);
fg_rv = fgets(my_line, MAX, stdin);
sem_post(&sems[next]);

这样可以避免多个线程同时读 stdin。但是，后面如果使用 strtok 拆单词，程序仍然可能线程不安全：

my_string = strtok(my_line, " \t\n");
while (my_string != NULL) {
    my_string = strtok(NULL, " \t\n");
}

原因是 strtok(NULL, ...) 需要知道“上一次拆到哪里了”。strtok 会把这个位置保存在函数内部的静态状态中，类似：

static char* saved_position;

单线程中这没有问题；但多线程中，线程 0 正在拆自己的字符串时，线程 1 也调用 strtok，就可能覆盖这个内部位置。于是线程 0 下一次调用 strtok(NULL, ...) 时，可能继续拆线程 1 的字符串。

注意：问题不在 my_line。my_line 是线程自己的局部数组，通常位于各自栈上。真正的问题是 strtok 内部隐藏了共享状态。

解决办法是使用可重入版本 strtok_r：

char* saveptr;
char* my_string;

my_string = strtok_r(my_line, " \t\n", &saveptr);
while (my_string != NULL) {
    printf("%s\n", my_string);
    my_string = strtok_r(NULL, " \t\n", &saveptr);
}

strtok_r 把“拆到哪里了”这个状态放到调用者提供的 saveptr 中。如果每个线程都有自己的 saveptr，线程之间就不会互相覆盖解析位置。

保证线程安全的常见方法：

• 避免共享可变状态，尽量使用局部变量或线程私有变量。
• 如果必须共享状态，就用互斥锁、信号量、读写锁等同步机制保护。
• 使用线程安全或可重入的库函数，例如用 strtok_r 替代 strtok。
• 检查整个代码块，包括它调用的函数；只要其中某个函数内部有未保护的共享状态，整体就可能线程不安全。

忙等待#

忙等待（busy-waiting）：一个线程反复测试某个条件是否成立，在条件成立前不做其他有用工作。

例子：用共享变量 flag 控制线程进入临界区的顺序。

y = Compute(my_rank);
while (flag != my_rank);
x = x + y;
flag++;

核心理解：

• while (flag != my_rank); 的循环体是空的，只是在反复检查条件。
• 条件不满足时，线程会一直占用 CPU 等待。
• 可以用来强制线程按某种顺序进入临界区，但效率通常不好。
• 如果编译器优化或硬件重排改变了语句顺序，可能破坏程序正确性。
• 它依赖共享变量可见性，实际编程中要非常谨慎。

忙等待的关键问题：轮到的线程可能没被调度#

忙等待最重要的问题是：如果 flag 已经轮到某个线程，但操作系统恰好没有把 CPU 分配给这个线程，那么其他线程即使在运行，也只能卡在忙等待里空转。

假设有 2 个核心、5 个线程，并用 flag 控制线程按编号进入临界区：

while (flag != my_rank);
/* 临界区 */
flag++;

表 4.2：带有忙等待的可能事件序列。