第 160 / 187 篇

15.2. 分布式内存系统、消息传递与 MPI

说明

本文是个人学习用的非官方中英对照译文,原文:https://diveintosystems.org/book/C15-Parallel/distrmem.html。
原书采用 CC BY-NC-ND 4.0 许可(禁止演绎),请勿公开传播本译文。
标为「译注」「现代更新」的内容是译者补充,不代表原书作者观点;代码与原文逐字一致,未作改动。

15.2. Distributed Memory Systems, Message Passing, and MPI

第 14 章介绍了 Pthreads 和 OpenMP 等机制,程序可以借助它们在共享内存系统上利用多个 CPU 核心。在这类系统中,所有核心共享同一套物理内存硬件,因此它们可以通过读写共享的内存地址来交换数据、同步各自的行为。虽然共享内存系统让通信变得相对容易,但其可扩展性受限于系统中 CPU 核心的数量。

Chapter 14 describes mechanisms like Pthreads and OpenMP that programs use to take advantage of multiple CPU cores on a shared memory system. In such systems, each core shares the same physical memory hardware, allowing them to communicate data and synchronize their behavior by reading from and writing to shared memory addresses. Although shared memory systems make communication relatively easy, their scalability is limited by the number of CPU cores in the system.

截至 2019 年,高端商用服务器 CPU 一般最多提供 64 个核心。然而对于某些任务来说,即便有几百个 CPU 核心也远远不够。例如,设想模拟地球海洋的流体动力学,或者为整个万维网的内容建立索引以构建一个搜索应用。这类庞大的任务所需的物理内存和处理器数量,超出了任何一台计算机所能提供的范围。因此,需要大量 CPU 核心的应用会运行在放弃了共享内存的系统上:它们运行在由多台计算机组成的系统中,每台计算机都有自己的 CPU 和内存,彼此通过网络通信来协调行为。

As of 2019, high-end commercial server CPUs generally provide a maximum of 64 cores. For some tasks, though, even a few hundred CPU cores isn’t close enough. For example, imagine trying to simulate the fluid dynamics of the Earth’s oceans or index the entire contents of the World Wide Web to build a search application. Such massive tasks require more physical memory and processors than any single computer can provide. Thus, applications that require a large number of CPU cores run on systems that forego shared memory. Instead, they execute on systems built from multiple computers, each with their own CPU(s) and memory, that communicate over a network to coordinate their behavior.

现代更新(截至 2026-11)· 核数早已不止 64

  • AMD EPYC 9005(Zen 5):2024-10-10 发布,每插槽最多 192 核。AMD 公告
  • Intel Xeon 6+(Clearwater Forest,全 E 核):2026 年发布,每插槽最多 288 核。TechSpot
  • AMD 第 6 代 EPYC(Venice,Zen 6):AMD 公布的 2026 年产品,最多 256 核。Tom’s Hardware

双路服务器已有数百核,很多以前要上集群的任务单机就能完成;但原文的论点不变:2026 年 6 月世界第一的超算 LineShine 有 13,789,440 个核心,只能靠分布式内存组织。TOP500 2026-06

一组协同工作的计算机被称为分布式内存系统(distributed memory system,通常也直接叫分布式系统)。

A collection of computers working together is known as a distributed memory system (or often just distributed system).

原书注 · 关于时间顺序的说明(A Note on Chronology)

虽然本书按这样的顺序来介绍,但实际上,早在线程或 OpenMP 这类机制出现之前,系统设计者就已经在构建分布式系统了。

Despite the order in which they’re presented in this book, systems designers built distributed systems long before mechanisms like threads or OpenMP existed.

有些分布式内存系统的硬件集成度比其他系统更高。例如,超级计算机是一种高性能系统,其中大量计算节点紧密耦合(高度集成)在一个高速互连网络上。每个计算节点都有自己的 CPU、GPU 和内存,但多个节点可能共享二级存储、电源等辅助资源。不同超级计算机之间,硬件共享的具体程度各不相同。

Some distributed memory systems integrate hardware more closely than others. For example, a supercomputer is a high-performance system in which many compute nodes are tightly coupled (closely integrated) to a fast interconnection network. Each compute node contains its own CPU(s), GPU(s), and memory, but multiple nodes might share auxiliary resources like secondary storage and power supplies. The exact level of hardware sharing varies from one supercomputer to another.

在另一个极端,分布式应用可能运行在一组松散耦合(集成度较低)、完全自治的计算机(节点)上,这些节点通过以太网等传统局域网(LAN)技术相连。这样的一组节点被称为商用现成(commodity off-the-shelf,COTS)集群。COTS 集群通常采用无共享架构(shared-nothing architecture),即每个节点都拥有自己的一整套计算硬件(CPU、GPU、内存和存储)。图 1 展示了一个由两台共享内存计算机组成的无共享分布式系统。

On the other end of the spectrum, a distributed application might run on a loosely coupled (less integrated) collection of fully autonomous computers (nodes) connected by a traditional local area network (LAN) technology like Ethernet. Such a collection of nodes is known as a commodity off-the-shelf (COTS) cluster. COTS clusters typically employ a shared-nothing architecture in which each node contains its own set of computation hardware (CPU(s), GPU(s), memory, and storage). Figure 1 illustrates a shared-nothing distributed system consisting of two shared-memory computers.

Two computer block diagrams, each with a four-core CPU connected to a private memory and I/O controller. The I/O controller connects to a network interface, which connects the two nodes via unspecified network infrastructure (e.g., Ethernet, InfiniBand, Fibre Channel).

图 1. 由两个计算节点构成的无共享分布式内存体系结构的主要组成部分

Figure 1. The major components of a shared-nothing distributed memory architecture built from two compute nodes

译注

图中标签:Core=核心,Main Memory=主存,I/O Controller=I/O 控制器,Network Interface=网络接口(网卡),Network Infrastructure (e.g., Ethernet, InfiniBand, Fibre Channel)=网络基础设施(如以太网、InfiniBand、光纤通道)。

图中两台机器各自内部是”共享内存”(4 个核共享本机内存),彼此之间则只能通过网络传递消息——现实中的集群几乎都是这种混合结构。所以大型 HPC 程序常用”MPI + X”的写法:节点之间用 MPI,节点内部用 OpenMP 线程(第 14 章)或 CUDA(15.1 节)。图注里提到的 InfiniBand 是 HPC 常用的高速网络,支持 RDMA(远程直接内存访问:网卡直接读写远端机器的内存,绕过对方 CPU 和操作系统内核),延迟可低至微秒级,远低于普通 TCP/IP。

现代更新(截至 2026-11)· 互连网络

2026 年 6 月 TOP500 中,InfiniBand 占 292 台(58.4%),千兆级以太网占 165 台(33%);美国三台 E 级超算都用 HPE Slingshot-11。TOP500 2026-06 超以太网联盟于 2025-06-11 发布 UEC 1.0 规范,在以太网/IP 上提供面向 AI 和 HPC 的现代 RDMA。Linux 基金会公告

15.2.1. 并行与分布式处理模型

15.2.1. Parallel and Distributed Processing Models

应用设计者通常会采用一些久经考验的设计来组织分布式应用。采用这样的应用模型有助于开发者推理应用的行为,因为应用的行为会遵循大家熟知的规范。每种模型都有自己独特的优缺点——不存在放之四海而皆准的方案。下面我们简要介绍几种较常见的模型,但请注意,这并不是一份详尽的清单。

Application designers often organize distributed applications using tried-and-true designs. Adopting application models like these helps developers reason about an application because its behavior will conform to well-understood norms. Each model has its unique benefits and drawbacks — there’s no one-size-fits-all solution. We briefly characterize a few of the more common models below, but note that we’re not presenting an exhaustive list.

客户端/服务器

Client/Server

客户端/服务器模型(client/server model)是一种极其常见的应用模型,它把应用的职责划分给两类参与者:客户端进程和服务器进程。服务器进程为请求完成某项工作的客户端提供服务。服务器进程通常在一个众所周知的地址上等待,接收来自客户端的连接。建立连接后,客户端向服务器进程发送请求,服务器要么满足这些请求(例如取回所请求的文件),要么报告错误(例如文件不存在,或客户端无法通过身份验证)。

The client/server model is an extremely common application model that divides an application’s responsibilities among two actors: client processes and server processes. A server process provides a service to clients that ask for something to be done. Server processes typically wait at well-known addresses to receive incoming connections from clients. Upon making a connection, a client sends requests to the server process, which either satisfies those requests (e.g., by fetching a requested file) or reports an error (e.g., the file not existing or the client can’t be properly authenticated).

你可能没有意识到,你正在阅读的这本教科书就是通过客户端/服务器模型访问的!你的 Web 浏览器(客户端)连接到一个位于公共地址(diveintosystems.org)的网站(服务器),以获取本书的内容。

Although you may not have considered it, you accessed the textbook you’re reading right now via the client/server model! Your web browser (client) connected to a website (server) at a public address (diveintosystems.org) to retrieve the book’s contents.

流水线

Pipeline

流水线模型(pipeline model)把应用划分为一系列不同的步骤,数据从一个步骤流向下一个步骤。流水线中的各个组件独立且同时地处理各自的数据。这种模型很适合这样的应用:其工作流程是对大量输入数据执行线性的、重复性的任务。例如,考虑计算机动画电影的制作。电影的每一帧都必须经过一系列步骤的处理来变换画面(例如添加纹理或施加光照)。由于每个步骤都在序列中独立进行,动画师可以在一个大型计算机集群上并行处理多个帧,从而加快渲染速度。

The pipeline model divides an application into a distinct sequence of steps in which data flows from one step to another. Individual components within the pipeline each process their data independently and simultaneously. This model works well for applications whose workflow involves linear, repetitive tasks over large data inputs. For example, consider the production of computer-animated films. Each frame of the film must be processed through a sequence of steps that transform the frame (e.g., adding textures or applying lighting). Because each step happens independently in a sequence, animators can speed up rendering by processing frames in parallel across a large cluster of computers.

主管/工人(Boss/Worker)

Boss/Worker

在主管/工人模型(boss/worker model)中,一个进程充当中央协调者,把工作分配给其他节点上的进程。这种模型适合需要处理大量可分割输入的问题。boss 把输入分成较小的片段,给每个 worker 分配一个或多个片段。在一些应用中,boss 可能会静态地给每个 worker 恰好分配一个输入片段;而在另一些应用中,worker 可能会反复地处理完一个输入片段后,再回到 boss 那里动态地领取下一块输入。本节稍后会展示一个示例程序,其中 boss 把一个数组分给许多 worker,对数组执行标量乘法。

In the boss/worker model, one process acts as a central coordinator and distributes work among the processes at other nodes. This model works well for problems that require processing a large, divisible input. The boss divides the input into smaller pieces and assigns one or more pieces to each worker. In some applications, the boss might statically assign each worker exactly one piece of the input. In other cases, the workers might repeatedly finish a piece of the input and then return to the boss to dynamically retrieve the next input chunk. Later in this section, we’ll present an example program in which a boss divides an array among many workers to perform scalar multiplication on an array.

译注

静态分配 vs. 动态领取,对应第 14 章 OpenMP 中 schedule(static) 与 schedule(dynamic) 的区别:前者开销小,后者在各块工作量不均衡时能做负载均衡。分布式框架里常见的”任务队列 + 工作者拉取任务”(如 Celery、Ray、Spark 的任务调度)都是动态领取的变体。

注意,这种模型有时也被称为其他名字,比如”master/worker”(主/从)或其他变体,但核心思想是一样的。

Note that this model is sometimes called other names, like “master/worker” or other variants, but the main idea is the same.

对等(Peer-to-Peer)

Peer-to-Peer

与主管/工人模型不同,对等(peer-to-peer,P2P)应用不依赖于一个中央控制进程。相反,各个对等进程会自行把应用组织成一种结构,在其中它们各自承担大致相同的职责。例如,在 BitTorrent 文件共享协议中,每个对等节点反复与其他节点交换文件的各个部分,直到所有节点都收到了完整的文件。

Unlike the boss/worker model, a peer-to-peer application avoids relying on a centralized control process. Instead, peer processes self-organize the application into a structure in which they each take on roughly the same responsibilities. For example, in the BitTorrent file sharing protocol, each peer repeatedly exchanges parts of a file with others until they’ve all received the entire file.

由于没有中心化组件,对等应用通常对节点故障具有较强的鲁棒性。另一方面,对等应用通常需要复杂的协调算法,这使得它们难以构建,也难以进行严格的测试。

Lacking a centralized component, peer-to-peer applications are generally robust to node failures. On the other hand, peer-to-peer applications typically require complex coordination algorithms, making them difficult to build and rigorously test.

15.2.2. 通信协议

15.2.2. Communication Protocols

无论是作为超级计算机的一部分,还是 COTS 集群的一部分,分布式内存系统中的进程都通过消息传递(message passing)进行通信:一个进程显式地向一个或多个其他节点上的进程发送消息,由它们接收。如何利用网络由运行在系统上的应用自己决定——有些应用需要频繁通信,以便紧密协调许多节点上进程的行为;而另一些应用通信只是为了把大量输入分给各个进程,之后基本上独立工作。

Whether they are part of a supercomputer or a COTS cluster, processes in a distributed memory system communicate via message passing, whereby one process explicitly sends a message to processes on one or more other nodes, which receive it. It’s up to the applications running on the system to determine how to utilize the network — some applications require frequent communication to tightly coordinate the behavior of processes across many nodes, whereas other applications communicate to divide up a large input among processes and then mostly work independently.

分布式应用通过定义一个通信协议(protocol)来正式规定它的通信方式。协议描述了一组管理应用如何使用网络的规则,包括:

A distributed application formalizes its communication expectations by defining a communication protocol, which describes a set of rules that govern its use of the network, including:

  • 进程应该在什么时候发送消息
  • When a process should send a message
  • 应该把消息发给哪个(些)进程
  • To which process(es) it should send the message
  • 消息应该采用什么格式
  • How to format the message

没有协议,应用可能无法正确地解读消息,甚至可能发生死锁。例如,如果一个应用由两个进程组成,而每个进程都在等待对方先给自己发消息,那么两个进程都永远无法继续推进。协议为通信增加了结构,降低了出现这类故障的可能性。

Without a protocol, an application might fail to interpret messages properly or even deadlock. For example, if an application consists of two processes, and each process waits for the other to send it a message, neither process will ever make progress. Protocols add structure to communication to reduce the likelihood of such failures.

为了实现通信协议,应用需要一些基本功能,比如发送和接收消息、为进程命名(寻址)以及同步进程的执行。许多应用借助消息传递接口(Message Passing Interface)来获得这些功能。

To implement a communication protocol, applications require basic functionality for tasks like sending and receiving messages, naming processes (addressing), and synchronizing process execution. Many applications look to the Message Passing Interface for such functionality.

15.2.3. 消息传递接口(MPI)

15.2.3. Message Passing Interface (MPI)

消息传递接口(Message Passing Interface,MPI)定义了(但本身并不实现)一套标准化的接口,应用可以用它在分布式内存系统中进行通信。通过采用 MPI 通信标准,应用就具备了可移植性(portable),也就是说,它们可以在许多不同的系统上编译和运行。换句话说,只要系统上安装了某个 MPI 实现,一个可移植的应用就可以从一个系统迁移到另一个系统,并且可以期望它正确执行,即使这些系统的底层特性各不相同。

The Message Passing Interface (MPI) defines (but does not itself implement) a standardized interface that applications can use to communicate in a distributed memory system. By adopting the MPI communication standard, applications become portable, meaning that they can be compiled and executed on many different systems. In other words, as long as an MPI implementation is installed, a portable application can move from one system to another and expect to execute properly, even if the systems have different underlying characteristics.

现代更新(截至 2026-11)· MPI 标准版本

MPI-4.0(2021-06-09)→ MPI-4.1(2023-11-02)→ MPI-5.0(2025-06-05)。MPI Forum MPI-5.0 最大的变化是加入标准 ABI,让不同厂商的 MPI 实现在二进制层面可以互换(以前用 Open MPI 编译的程序不能直接换 MPICH 运行);任何合法的 MPI-4.1 程序仍是合法的 MPI-5.0 程序,本节示例代码不受影响。MPI-5.0 背景说明

MPI 允许程序员把一个应用划分成多个进程。它给应用中的每个进程分配一个唯一的标识符,称为 rank(秩,即进程编号)。对于一个有 N 个进程的应用,rank 的取值范围是 0 到 N-1。进程可以调用 MPI_Comm_rank 函数得知自己的 rank,调用 MPI_Comm_size 得知应用中一共有多少个进程在执行。要发送消息,进程调用 MPI_Send 并指定目标接收者的 rank。类似地,进程调用 MPI_Recv 来接收消息,并指定是等待来自某个特定节点的消息,还是接收来自任意发送者的消息(使用常量 MPI_ANY_SOURCE 作为 rank)。

MPI allows a programmer to divide an application into multiple processes. It assigns each of an application’s processes a unique identifier, known as a rank, which ranges from 0 to N-1 for an application with N processes. A process can learn its rank by calling the MPI_Comm_rank function, and it can learn how many processes are executing in the application by calling MPI_Comm_size. To send a message, a process calls MPI_Send and specifies the rank of the intended recipient. Similarly, a process calls MPI_Recv to receive a message, and it specifies whether to wait for a message from a specific node or to receive a message from any sender (using the constant MPI_ANY_SOURCE as the rank).

除了基本的发送和接收函数之外,MPI 还定义了多种函数,使一个进程更容易把数据传给多个接收者。例如,MPI_Bcast 允许一个进程只调用一次函数,就把一条消息发送给应用中的所有其他进程。MPI 还定义了一对函数 MPI_Scatter 和 MPI_Gather:一个进程可以把数组拆分开,把各个片段分发给各个进程(scatter,分发),各进程处理完数据后,再把所有数据取回来汇总结果(gather,收集)。

In addition to the basic send and receive functions, MPI also defines a variety of functions that make it easier for one process to communicate data to multiple recipients. For example, MPI_Bcast allows one process to send a message to every other process in the application with just one function call. It also defines a pair of functions, MPI_Scatter and MPI_Gather, that allow one process to divide up an array and distribute the pieces among processes (scatter), operate on the data, and then later retrieve all the data to coalesce the results (gather).

译注 · 集合通信(collective communication)

Bcast / Scatter / Gather 这类”一组进程一起参与”的操作统称集合通信。另外两个必须认识的是 **MPI_Reduce**(把各进程的值用加法/求最大值等运算归约到一个进程)和 MPI_Allreduce(归约后结果发回给所有进程)。Allreduce 今天最出名的用途是分布式深度学习训练:每块 GPU 算出自己那份数据的梯度后,用 all-reduce 求和/平均,再各自更新模型参数——这就是数据并行训练的核心一步。

现代更新 · 集合通信与 AI

NVIDIA 的 NCCL 库为多 GPU 提供 AllReduce、Broadcast、Reduce、AllGather、ReduceScatter、AlltoAll、Gather、Scatter 等集合操作,名字与 MPI 一一对应;数据并行训练每一步都要用 AllReduce 汇总各 GPU 的梯度。NCCL 文档

由于 MPI 只规定了一组函数及其应有的行为,每个系统的设计者都可以根据自己系统的能力,以合适的方式来实现 MPI 的功能。例如,如果一个系统的互连网络支持广播(同时把一条消息的一份拷贝发送给多个接收者),那么它实现 MPI 的 MPI_Bcast 函数的效率,可能会比不支持广播的系统更高。

Because MPI specifies only a set of functions and how they should behave, each system designer can implement MPI’s functionality in a way that matches the capabilities of their particular system. For example, a system with an interconnect network that supports broadcasting (sending one copy of a message to multiple recipients at the same time) might be able to implement MPI’s MPI_Bcast function more efficiently than a system without such support.

15.2.4. MPI Hello World

15.2.4. MPI Hello World

作为 MPI 编程的入门,来看下面这个”hello world”程序(hello_world_mpi.c):

As an introduction to MPI programming, consider the “hello world” program (hello_world_mpi.c) presented here:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
#include <unistd.h>
#include "mpi.h"

int main(int argc, char **argv) {
int rank, process_count;
char hostname[1024];

/* Initialize MPI. */
MPI_Init(&argc, &argv);

/* Determine how many processes there are and which one this is. */
MPI_Comm_size(MPI_COMM_WORLD, &process_count);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);

/* Determine the name of the machine this process is running on. */
gethostname(hostname, 1024);

/* Print a message, identifying the process and machine it comes from. */
printf("Hello from %s process %d of %d\n", hostname, rank, process_count);

/* Clean up. */
MPI_Finalize();

return 0;
}

译注

代码注释依次为:初始化 MPI;确定一共有多少个进程、本进程是哪一个;确定本进程运行在哪台机器上;打印一条消息,标明来自哪个进程、哪台机器;清理。MPI_COMM_WORLD 是 MPI 预定义的通信子(communicator),代表”本次启动的所有进程”;也可以用 MPI_Comm_split 等函数把进程划分成更小的组,rank 是相对于某个通信子而言的。

启动这个程序时,MPI 会以独立进程的形式,在一台或多台计算机上同时执行它的多个副本。每个进程都调用 MPI 来确定一共有多少个进程在执行(用 MPI_Comm_size),以及自己是其中的哪一个(即进程的 rank,用 MPI_Comm_rank)。查到这些信息后,每个进程打印一条简短的消息,其中包含自己的 rank 以及所运行计算机的名字(hostname),然后结束。

When starting this program, MPI simultaneously executes multiple copies of it as independent processes across one or more computers. Each process makes calls to MPI to determine how many total processes are executing (with MPI_Comm_size) and which process it is among those processes (the process’s rank, with MPI_Comm_rank). After looking up this information, each process prints a short message containing the rank and name of the computer (hostname) it’s running on before terminating.

原书注 · 运行 MPI 代码(Running MPI Code)

要运行这些 MPI 示例,你需要在系统上安装一个 MPI 实现,比如 OpenMPI 或 MPICH。

To run these MPI examples, you’ll need an MPI implementation like OpenMPI or MPICH installed on your system.

译注 · 在自己电脑上试一试

不需要集群,单机就能跑:macOS 上 brew install open-mpi,Ubuntu 上 sudo apt install openmpi-bin libopenmpi-dev(或 mpich)。然后 mpirun -np 4 ./hello_world_mpi 就会在本机起 4 个进程。如果进程数超过 CPU 核数,Open MPI 会拒绝运行,加 --oversubscribe 即可。

要编译这个示例,调用 mpicc 编译器程序,它会执行一个支持 MPI 的 gcc 版本来构建程序,并将其与 MPI 库链接:

To compile this example, invoke the mpicc compiler program, which executes an MPI-aware version of gcc to build the program and link it against MPI libraries:

1
$ mpicc -o hello_world_mpi hello_world_mpi.c

译注

mpicc 本身只是一个包装脚本(wrapper),它会调用系统上的 C 编译器(gcc 或 clang)并自动加上 MPI 的头文件路径和库。用 mpicc --showme(Open MPI)或 mpicc -show(MPICH)可以看到它实际执行的命令。

要执行这个程序,用 mpirun 工具通过 MPI 启动多个并行进程。需要告诉 mpirun 在哪些计算机上运行进程(--hostfile),以及在每台机器上运行多少个进程(-np)。这里,我们给它提供了一个名为 hosts.txt 的文件,让 mpirun 在两台计算机上创建四个进程,一台名为 lemon,另一台名为 orange:

To execute the program, use the mpirun utility to start up several parallel processes with MPI. The mpirun command needs to be told which computers to run processes on (--hostfile) and how many processes to run at each machine (-np). Here, we provide it with a file named hosts.txt that tells mpirun to create four processes across two computers, one named lemon, and another named orange:

译注 · 原文表述不够准确

准确地说,-np 8 指定的是进程总数(8 个),而不是”每台机器的进程数”;每台机器放几个进程由 hostfile 里的 slots 决定。原文”create four processes across two computers”应理解为两台机器各 4 个、共 8 个(输出里 rank 0–7 正好各占 4 个)。对应的 hosts.txt(Open MPI 格式)大致是:

1
2
lemon slots=4
orange slots=4

在超算/集群上,通常不直接用 mpirun,而是通过作业调度系统(最常见的是 Slurm)提交,例如 srun -N 2 -n 8 ./hello_world_mpi。

1
2
3
4
5
6
7
8
9
$ mpirun -np 8 --hostfile hosts.txt ./hello_world_mpi
Hello from lemon process 4 of 8
Hello from lemon process 5 of 8
Hello from orange process 2 of 8
Hello from lemon process 6 of 8
Hello from orange process 0 of 8
Hello from lemon process 7 of 8
Hello from orange process 3 of 8
Hello from orange process 1 of 8

原书警示 · MPI 的执行顺序(MPI Execution Order)

你永远不应该对 MPI 进程的执行顺序做任何假设。这些进程在多台机器上启动,每台机器都有自己的操作系统和进程调度器。如果程序的正确性依赖于进程按特定顺序运行,你就必须确保这个顺序真的会发生——例如,强制某些进程暂停,直到它们收到某条消息为止。

You should never make any assumptions about the order in which MPI processes will execute. The processes start up on multiple machines, each of which has its own OS and process scheduler. If the correctness of your program requires that processes run in a particular order, you must ensure that the proper order occurs — for example, by forcing certain processes to pause until they receive a message.

15.2.5. MPI 标量乘法

15.2.5. MPI Scalar Multiplication

来看一个更有实质内容的 MPI 示例:对一个数组执行标量乘法。这个例子采用主管/工人模型——一个进程把数组分成较小的片段,再分发给各个 worker 进程。注意,在这个标量乘法的实现中,boss 进程在把各部分分发给其他 worker 之后,自己也充当一个 worker,负责数组中一部分元素的乘法。

For a more substantive MPI example, consider performing scalar multiplication on an array. This example adopts the boss/worker model — one process divides the array into smaller pieces and distributes them among worker processes. Note that in this implementation of scalar multiplication, the boss process also behaves as a worker and multiplies part of the array after distributing sections to the other workers.

为了从并行工作中获益,每个进程只把自己本地的那一段数组乘以标量值,然后所有 worker 把结果发回给 boss 进程,以构成最终结果。在程序的好几个地方,代码会检查进程的 rank 是否为 0:

To benefit from working in parallel, each process multiplies just its local piece of the array by the scalar value, and then the workers all send the results back to the boss process to form the final result. At several points in the program, the code checks to see whether the rank of the process is zero:

1
2
3
if (rank == 0) {
/* This code only executes at the boss. */
}

译注

注释的意思:这段代码只在 boss 上执行。

这个检查确保只有一个进程(rank 为 0 的那个)扮演 boss 的角色。按照惯例,MPI 应用通常选择 rank 0 来执行一次性任务,因为无论有多少个进程,总会有一个进程的 rank 是 0(即使只有一个进程在执行)。

This check ensures that only one process (the one with rank 0) plays the role of the boss. By convention, MPI applications often choose rank 0 to perform one-time tasks because no matter how many processes there are, one will always be given rank 0 (even if just a single process is executing).

MPI 通信

MPI Communication

boss 进程首先确定标量值和初始的输入数组。在真实的科学计算应用中,boss 很可能会从输入文件中读取这些值。为了简化这个例子,boss 使用一个常数标量值(10),并生成一个简单的 40 元素数组(内容是 0 到 39 的序列)来做演示。

The boss process begins by determining the scalar value and initial input array. In a real scientific computing application, the boss would likely read such values from an input file. To simplify this example, the boss uses a constant scalar value (10) and generates a simple 40-element array (containing the sequence 0 to 39) for illustrative purposes.

这个程序需要 MPI 进程之间在以下三项重要任务上进行通信:

This program requires communication between MPI processes for three important tasks:

  1. boss 把标量值和数组的大小发送给所有 worker。
  1. The boss sends the scalar value and the size of the array to all of the workers.
  1. boss 把初始数组分成若干片段,给每个 worker 发送一个片段。
  1. The boss divides the initial array into pieces and sends a piece to each worker.
  1. 每个 worker 把自己那段数组中的值乘以标量,然后把更新后的值发回给 boss。
  1. Each worker multiplies the values in its piece of the array by the scalar and then sends the updated values back to the boss.

广播重要的值

Broadcasting Important Values

为了把标量值发送给 worker,示例程序使用了 MPI_Bcast 函数,它让一个 MPI 进程只需调用一次函数,就能把同一个值发送给所有其他 MPI 进程:

To send the scalar value to the workers, the example program uses the MPI_Bcast function, which allows one MPI process to send the same value to all the other MPI processes with one function call:

1
2
/* Boss sends the scalar value to every process with a broadcast. */
MPI_Bcast(&scalar, 1, MPI_INT, 0, MPI_COMM_WORLD);

译注

注释的意思:boss 通过广播把标量值发送给每个进程。MPI_Bcast 的 5 个参数依次是:缓冲区地址、元素个数、元素类型、根进程(root)的 rank、通信子。

这个调用把从 scalar 变量地址开始的一个整数(MPI_INT),从 rank 为 0 的进程发送给其他每一个进程(MPI_COMM_WORLD)。所有 worker 进程(即 rank 不为零的进程)都把广播的内容接收到自己本地的 scalar 变量副本中,所以这个调用完成后,每个进程都知道了要使用的标量值。

This call sends one integer (MPI_INT) starting from the address of the scalar variable from the process with rank 0 to every other process (MPI_COMM_WORLD). All the worker processes (those with nonzero rank) receive the broadcast into their local copy of the scalar variable, so when this call completes, every process knows the scalar value to use.

原书注 · MPI_Bcast 的行为(MPI_Bcast Behavior)

每个进程都执行 MPI_Bcast,但它的行为取决于调用进程的 rank。如果 rank 与第四个参数一致,调用者就扮演发送者的角色。所有其他调用 MPI_Bcast 的进程都充当接收者。

Every process executes MPI_Bcast, but it behaves differently depending on the rank of the calling process. If the rank matches that of the fourth argument, the caller assumes the role of the sender. All other processes that call MPI_Bcast act as receivers.

类似地,boss 把数组的总大小广播给其他每个进程。得知数组总大小后,每个进程用数组总大小除以 MPI 进程数,得到 local_size 变量的值。local_size 变量表示每个 worker 分到的那段数组包含多少个元素。例如,如果输入数组有 40 个元素,应用由 8 个进程组成,那么每个进程负责数组中的 5 个元素(40 / 8 = 5)。为了让例子保持简单,这里假设进程数能整除数组大小:

Similarly, the boss broadcasts the total size of the array to every other process. After learning the total array size, each process sets a local_size variable by dividing the total array size by the number of MPI processes. The local_size variable represents how many elements each worker’s piece of the array will contain. For example, if the input array contains 40 elements and the application consists of eight processes, each process is responsible for a five-element piece of the array (40 / 8 = 5). To keep the example simple, it assumes that the number of processes evenly divides the size of the array:

1
2
3
4
5
6
7
8
9
/* Each process determines how many processes there are. */
MPI_Comm_size(MPI_COMM_WORLD, &process_count);

/* Boss sends the total array size to every process with a broadcast. */
MPI_Bcast(&array_size, 1, MPI_INT, 0, MPI_COMM_WORLD);

/* Determine how many array elements each process will get.
* Assumes the array is evenly divisible by the number of processes. */
local_size = array_size / process_count;

译注

注释依次为:每个进程确定一共有多少个进程;boss 通过广播把数组总大小发送给每个进程;确定每个进程会分到多少个数组元素(假设数组大小能被进程数整除)。不能整除时,应改用 MPI_Scatterv / MPI_Gatherv,它们允许为每个进程分别指定元素个数和偏移量。

分发数组

Distributing the Array

现在每个进程都知道了标量值,以及自己负责相乘的值有多少个,接下来 boss 必须把数组分成若干片段,分发给各个 worker。注意,在这个实现中,boss(rank 0)也作为 worker 参与计算。例如,对于一个 40 元素的数组和 8 个进程(rank 0–7),boss 应该把数组元素 0–4 留给自己(rank 0),把元素 5–9 发给 rank 1,元素 10–14 发给 rank 2,依此类推。图 2 展示了 boss 如何把数组的各个片段分配给每个 MPI 进程。

Now that each process knows the scalar value and how many values it’s responsible for multiplying, the boss must divide the array into pieces and distribute them among the workers. Note that in this implementation, the boss (rank 0) also participates as a worker. For example, with a 40-element array and eight processes (ranks 0-7), the boss should keep array elements 0-4 for itself (rank 0), send elements 5-9 to rank 1, elements 10-14 to rank 2, and so on. Figure 2 shows how the boss assigns pieces of the array to each MPI process.

Each chunk of five array elements is distributed to the next process. For example, elements 0-4 are assigned to rank 0, elements 5-9 are assigned to rank 1, elements 10-14 are assigned to rank 2, and the patter continues until elements 35-39 are assigned to rank 7.

图 2. 一个 40 元素的数组在 8 个 MPI 进程(rank 0–7)之间的分配

Figure 2. The distribution of a 40-element array among eight MPI processes (ranks 0-7)

译注

图中 Input Array=输入数组,Distributed Array Pieces=分发后的数组片段,rank 0 (boss)=rank 0(主管进程)。这种”每个进程分到连续一段”的划分叫块划分(block distribution);另一种常见做法是循环划分(cyclic,元素 i 分给 rank i mod P),在各元素工作量不均匀时更有利于负载均衡。

把数组片段分发给每个 worker 的一种做法是:boss 端调用 MPI_Send,每个 worker 端调用 MPI_Recv:

One option for distributing pieces of the array to each worker combines MPI_Send calls at the boss with an MPI_Recv call at each worker:

1
2
3
4
5
6
7
8
9
10
11
12
13
if (rank == 0) {
int i;

/* For each worker process, send a unique chunk of the array. */
for (i = 1; i < process_count; i++) {
/* Send local_size ints starting at array index (i * local_size) */
MPI_Send(array + (i * local_size), local_size, MPI_INT, i, 0,
MPI_COMM_WORLD);
}
} else {
MPI_Recv(local_array, local_size, MPI_INT, 0, 0, MPI_COMM_WORLD,
MPI_STATUS_IGNORE);
}

译注

注释的意思:对每个 worker 进程,发送数组中独有的一段;从数组下标 i * local_size 处开始发送 local_size 个 int。MPI_Send 的 6 个参数:缓冲区、个数、类型、目标 rank、标签(tag)、通信子;MPI_Recv 多一个状态参数,不关心时传 MPI_STATUS_IGNORE。

在这段代码中,boss 执行一个循环,每个 worker 进程执行一次,每次给一个 worker 发送数组的一个片段。它从 array 地址偏移 (i * local_size) 的位置开始发送数据,以确保每个 worker 拿到的是数组中独有的一段。也就是说,rank 1 的 worker 拿到从下标 5 开始的一段,rank 2 拿到从下标 10 开始的一段,依此类推,如图 2 所示。

In this code, the boss executes a loop that executes once for each worker process, in which it sends the worker a piece of the array. It starts sending data from the address of array at an offset of (i * local_size) to ensure that each worker gets a unique piece of the array. That is, the worker with rank 1 gets a piece of the array starting at index 5, rank 2 gets a piece of the array starting at index 10, etc., as shown in Figure 2.

每次调用 MPI_Send 都会把 local_size(5)个整数的数据(20 字节)发送给 rank 为 i 的进程。靠近末尾的参数 0 表示消息标签(tag),这是一个本程序用不到的高级特性——把它设为 0 就是对所有消息一视同仁。

Each call to MPI_Send sends local_size (5) integers worth of data (20 bytes) to the process with rank i. The 0 argument toward the end represents a message tag, which is an advanced feature that this program doesn’t need — setting it to 0 treats all messages equally.

所有 worker 都调用 MPI_Recv 来获取属于自己的数组片段,并把它存放到 local_array 所指向的内存地址中。它们从 rank 为 0 的节点接收 local_size(5)个整数的数据(20 字节)。注意,MPI_Recv 是一个阻塞(blocking)调用,也就是说,调用它的进程会暂停,直到收到数据为止。由于 MPI_Recv 调用会阻塞,在 boss 发来属于自己的数组片段之前,任何 worker 都不会继续往下执行。

The workers all call MPI_Recv to retrieve their piece of the array, which they store in memory at the address to which local_array refers. They receive local_size (5) integers worth of data (20 bytes) from the node with rank 0. Note that MPI_Recv is a blocking call, which means that a process that calls it will pause until it receives data. Because the MPI_Recv call blocks, no worker will proceed until the boss sends its piece of the array.

译注 · MPI_Send 会不会阻塞?

MPI_Send(标准模式)的语义是”返回后发送缓冲区可以安全复用”,它可能阻塞到对方开始接收,也可能先把小消息拷进内部缓冲区立即返回——这取决于实现和消息大小。所以”两个进程都先 Send 再 Recv”的代码,消息小时能跑通、消息一大就死锁,这是 MPI 初学者最经典的 bug。解决办法:调整收发顺序、用 MPI_Sendrecv,或改用非阻塞的 MPI_Isend / MPI_Irecv 再配合 MPI_Wait(非阻塞通信还能让计算与通信重叠)。

并行执行

Parallel Execution

worker 收到自己的数组片段之后,就可以开始把每个数组元素乘以标量。由于每个 worker 拿到的是数组中独有的一个子集,它们可以相互独立地并行执行,而无需通信。

After a worker has received its piece of the array, it can begin multiplying each array value by the scalar. Because each worker gets a unique subset of the array, they can execute independently, in parallel, without the need to communicate.

汇总结果

Aggregating Results

最后,worker 完成乘法后,把更新后的数组值发回给 boss,由 boss 汇总结果。如果用 MPI_Send 和 MPI_Recv 来实现,这个过程看起来与上面分发数组的代码很像,只是发送方和接收方的角色互换了:

Finally, after workers complete their multiplication, they send the updated array values back to the boss, which aggregates the results. Using MPI_Send and MPI_Recv, this process looks similar to the array distribution code above, except the roles of sender and receiver are reversed:

1
2
3
4
5
6
7
8
9
10
if (rank == 0) {
int i;

for (i = 1; i < process_count; i++) {
MPI_Recv(array + (i * local_size), local_size, MPI_INT, i, 0,
MPI_COMM_WORLD, MPI_STATUS_IGNORE);
}
} else {
MPI_Send(local_array, local_size, MPI_INT, 0, 0, MPI_COMM_WORLD);
}

回想一下,MPI_Recv 会阻塞(即暂停执行),因此 for 循环中的每次调用都会让 boss 等待,直到收到 worker i 发来的那段数组。

Recall that MPI_Recv blocks or pauses execution, so each call in the for loop causes the boss to wait until it receives a piece of the array from worker i.

分发/收集(Scatter/Gather)

Scatter/Gather

虽然上一个例子中的 for 循环用 MPI_Send 和 MPI_Recv 正确地分发了数据,但它们没有简洁地表达出背后的意图。也就是说,在 MPI 看来,它们只是一连串的发送和接收调用,看不出”把一个数组分发到各个 MPI 进程”这个明显的目标。由于并行应用经常需要像这个示例数组一样分发和收集数据,MPI 专门为此提供了函数:MPI_Scatter 和 MPI_Gather。

Although the for loops in the previous example correctly distribute data with MPI_Send and MPI_Recv, they don’t succinctly capture the intent behind them. That is, they appear to MPI as a series of send and receive calls without the obvious goal of distributing an array across MPI processes. Because parallel applications frequently need to distribute and collect data like this example array, MPI provides functions for exactly this purpose: MPI_Scatter and MPI_Gather.

这两个函数有两大好处:

These functions provide two major benefits:

  1. 它们让上面的每一整段代码都可以用一次 MPI 函数调用来表达,从而简化了代码。
  1. They allow the entire code blocks above to each be expressed as a single MPI function call, which simplifies the code.
  1. 它们把操作的意图告诉了底层的 MPI 实现,MPI 实现也许能借此更好地优化性能。
  1. They express the intent of the operation to the underlying MPI implementation, which may be able to better optimize their performance.

译注

“更好地优化”是实打实的:例如 boss 逐个 MPI_Send 给 P 个进程需要 P−1 步,而广播/分发可以用树形算法,第 1 步 0→1,第 2 步 0→2、1→3,……只需约 log₂P 步。现代 MPI 库(以及 NVIDIA NCCL 这类 GPU 集合通信库)还会根据消息大小和网络拓扑,在树形、环形(ring)等多种算法之间自动选择。

要替换上面的第一个循环,每个进程可以调用 MPI_Scatter:

To replace the first loop above, each process could call MPI_Scatter:

1
2
3
/* Boss scatters chunks of the array evenly among all the processes. */
MPI_Scatter(array, local_size, MPI_INT, local_array, local_size, MPI_INT,
0, MPI_COMM_WORLD);

译注

注释的意思:boss 把数组按块平均分发给所有进程。

这个函数会自动把从 array 开始的内存内容,按每块 local_size 个整数分成若干块,分发到目标变量 local_array 中。参数 0 指定 rank 为 0 的进程(boss)是发送者,因此它读取源数组 array 并分发给其他进程(包括给自己发送一块)。其他每个进程都充当接收者,把数据接收到自己的 local_array 目标变量中。

This function automatically distributes the contents of memory starting at array in pieces containing local_size integers to the local_array destination variable. The 0 argument specifies that the process with rank 0 (the boss) is the sender, so it reads and distributes the array source to other processes (including sending one piece to itself). Every other process acts as a receiver and receives data into its local_array destination.

在这一次调用之后,各个 worker 就可以并行地对数组做乘法了。完成后,每个进程调用 MPI_Gather,把结果汇总回 boss 的 array 变量中:

After this single call, the workers can each multiply the array in parallel. When they finish, each process calls MPI_Gather to aggregate the results back in the boss’s array variable:

1
2
3
4
/* Boss gathers the chunks from all the processes and coalesces the
* results into a final array. */
MPI_Gather(local_array, local_size, MPI_INT, array, local_size, MPI_INT,
0, MPI_COMM_WORLD);

译注

注释的意思:boss 从所有进程收集各块,把结果合并成最终的数组。

这个调用的行为与 MPI_Scatter 正好相反:这一次,参数 0 指定 rank 为 0 的进程(boss)是接收者,因此它更新 array 变量,而各个 worker 则各自从自己的 local_array 变量中发送 local_size 个整数。

This call behaves like the opposite of MPI_Scatter: this time, the 0 argument specifies that the process with rank 0 (the boss) is the receiver, so it updates the array variable, and workers each send local_size integers from their local_array variables.

MPI 标量乘法的完整代码

Full Code for MPI Scalar Multiply

下面是使用 MPI_Scatter 和 MPI_Gather 的 MPI 标量乘法完整代码清单(scalar_multiply_mpi.c):

Here’s a full MPI scalar multiply code listing that uses MPI_Scatter and MPI_Gather (scalar_multiply_mpi.c):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <stdio.h>
#include <stdlib.h>
#include "mpi.h"

#define ARRAY_SIZE (40)
#define SCALAR (10)

/* In a real application, the boss process would likely read its input from a
* data file. This example program produces a simple array and informs the
* caller of the size of the array through the array_size pointer parameter.*/
int *build_array(int *array_size) {
int i;
int *result = malloc(ARRAY_SIZE * sizeof(int));

if (result == NULL) {
exit(1);
}

for (i = 0; i < ARRAY_SIZE; i++) {
result[i] = i;
}

*array_size = ARRAY_SIZE;
return result;
}

/* Print the elements of an array, given the array and its size. */
void print_array(int *array, int array_size) {
int i;
for (i = 0; i < array_size; i++) {
printf("%3d ", array[i]);
}
printf("\n\n");
}

/* Multiply each element of an array by a scalar value. */
void scalar_multiply(int *array, int array_size, int scalar) {
int i;
for (i = 0; i < array_size; i++) {
array[i] = array[i] * scalar;
}
}

int main(int argc, char **argv) {
int rank, process_count;
int array_size, local_size;
int scalar;
int *array, *local_array;

/* Initialize MPI */
MPI_Init(&argc, &argv);

/* Determine how many processes there are and which one this is. */
MPI_Comm_size(MPI_COMM_WORLD, &process_count);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);

/* Designate rank 0 to be the boss. It sets up the problem by generating
* the initial input array and choosing the scalar to multiply it by. */
if (rank == 0) {
array = build_array(&array_size);
scalar = SCALAR;

printf("Initial array:\n");
print_array(array, array_size);
}

/* Boss sends the scalar value to every process with a broadcast.
* Worker processes receive the scalar value by making this MPI_Bcast
* call. */
MPI_Bcast(&scalar, 1, MPI_INT, 0, MPI_COMM_WORLD);

/* Boss sends the total array size to every process with a broadcast.
* Worker processes receive the size value by making this MPI_Bcast
* call. */
MPI_Bcast(&array_size, 1, MPI_INT, 0, MPI_COMM_WORLD);

/* Determine how many array elements each process will get.
* Assumes the array is evenly divisible by the number of processes. */
local_size = array_size / process_count;

/* Each process allocates space to store its portion of the array. */
local_array = malloc(local_size * sizeof(int));
if (local_array == NULL) {
exit(1);
}

/* Boss scatters chunks of the array evenly among all the processes. */
MPI_Scatter(array, local_size, MPI_INT, local_array, local_size, MPI_INT,
0, MPI_COMM_WORLD);

/* Every process (including boss) performs scalar multiplication over its
* chunk of the array in parallel. */
scalar_multiply(local_array, local_size, scalar);

/* Boss gathers the chunks from all the processes and coalesces the
* results into a final array. */
MPI_Gather(local_array, local_size, MPI_INT, array, local_size, MPI_INT,
0, MPI_COMM_WORLD);

/* Boss prints the final answer. */
if (rank == 0) {
printf("Final array:\n");
print_array(array, array_size);
}

/* Clean up. */
if (rank == 0) {
free(array);
}
free(local_array);
MPI_Finalize();

return 0;
}

译注 · 代码注释要点

  • build_array 上方注释:在真实应用中,boss 进程很可能从数据文件读取输入;这个示例程序生成一个简单数组,并通过指针参数 array_size 告诉调用者数组大小。
  • if (rank == 0) 处:指定 rank 0 为 boss,由它生成初始输入数组并选定要乘的标量来设置问题。
  • 两次 MPI_Bcast 处:boss 通过广播把标量值 / 数组总大小发送给每个进程;worker 进程通过执行同一个 MPI_Bcast 调用来接收。
  • scalar_multiply(local_array, ...) 处:每个进程(包括 boss)并行地对自己那块数组做标量乘法。
  • 注意非 boss 进程里的 array 指针从未初始化,但这是安全的:MPI_Scatter 的发送缓冲区和 MPI_Gather 的接收缓冲区只在根进程上有意义,其他进程上的这个参数会被忽略。

在 main 函数中,boss 设置问题并创建一个数组。如果是在解决一个真实问题(例如一个科学计算应用),boss 很可能会从输入文件读取初始数据。初始化数组之后,boss 需要把数组大小以及用于乘法的标量这两项信息发送给所有其他 worker 进程,因此它把这些变量广播给每个进程。

In the main function, the boss sets up the problem and creates an array. If this were solving a real problem (for example, a scientific computing application), the boss would likely read its initial data from an input file. After initializing the array, the boss needs to send information about the size of the array and the scalar to use for multiplication to all the other worker processes, so it broadcasts those variables to every process.

现在每个进程都知道了数组的大小以及一共有多少个进程,它们各自做一次除法,就能确定自己负责相乘的数组元素有多少个。为简单起见,这段代码假设数组大小能被进程数整除。

Now that each process knows the size of the array and how many processes there are, they can each divide to determine how many elements of the array they’re responsible for multiplying. For simplicity, this code assumes that the array is evenly divisible by the number of processes.

接着,boss 使用 MPI_Scatter 函数给每个 worker 进程(包括它自己)发送等量的一段数组。现在 worker 拥有了所需的全部信息,于是各自并行地对自己那段数组做乘法。最后,当 worker 完成乘法后,boss 用 MPI_Gather 收集每个 worker 的那段数组,并输出最终结果。

The boss then uses the MPI_Scatter function to send an equal portion of the array to each worker process (including itself). Now the workers have all the information they need, so they each perform multiplication over their portion of the array in parallel. Finally, as the workers complete their multiplication, the boss collects each worker’s piece of the array using MPI_Gather to report the final results.

编译并运行这个程序的过程如下:

Compiling and executing this program looks like this:

1
2
3
4
5
6
7
8
9
10
$ mpicc -o scalar_multiply_mpi scalar_multiply_mpi.c

$ mpirun -np 8 --hostfile hosts.txt ./scalar_multiply_mpi
Initial array:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

Final array:
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190
200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390

15.2.6. 分布式系统面临的挑战

15.2.6. Distributed Systems Challenges

一般来说,协调分布式系统中多个进程的行为是出了名的困难。在共享内存系统中,如果某个硬件部件(例如 CPU 或电源)发生故障,整个系统都会无法工作。但在分布式系统中,各个自治的节点可能会独立地发生故障。例如,如果一个节点消失了而其他节点仍在运行,应用必须决定接下来该怎么办。类似地,互连网络也可能发生故障,这时在每个进程看来,就好像其他所有进程都失效了一样。

In general, coordinating the behavior of multiple processes in distributed systems is notoriously difficult. If a hardware component (e.g., CPU or power supply) fails in a shared memory system, the entire system becomes inoperable. In a distributed system though, autonomous nodes can fail independently. For example, an application must decide how to proceed if one node disappears and the others are still running. Similarly, the interconnection network could fail, making it appear to each process as if all the others failed.

译注 · 延伸阅读的关键词

这一段点到的问题,就是分布式系统这门课的核心:部分失效(partial failure)、网络分区(partition,以及由此引出的 CAP 定理),以及在不可靠网络上让多个节点对某个值达成一致的共识算法(Paxos、Raft;etcd、ZooKeeper 等协调服务都建立在它们之上)。经典 MPI 程序对故障的处理很简单粗暴:任何一个进程挂了,整个作业就中止,靠定期写检查点(checkpoint)再重启来恢复。想系统学习,推荐 MIT 6.5840(原 6.824)分布式系统课程和《数据密集型应用系统设计》(DDIA)。

分布式系统还面临着因缺乏共享硬件——即时钟——而带来的挑战。由于网络传输存在不可预测的延迟,自治的节点很难确定消息发送的先后顺序。解决这些挑战(以及其他许多挑战)超出了本书的范围。幸运的是,分布式软件的设计者已经构建了若干框架,让分布式应用的开发变得更容易。我们将在下一节介绍其中的一些框架。

Distributed systems also face challenges due to a lack of shared hardware, namely clocks. Due to unpredictable delays in network transmission, autonomous nodes cannot easily determine the order in which messages are sent. Solving these challenges (and many others) is beyond the scope of this book. Fortunately, distributed software designers have constructed several frameworks that ease the development of distributed applications. We characterize some of these frameworks in the next section.

译注

关于”没有共享时钟”:经典解法是 Lamport 在 1978 年提出的逻辑时钟(只关心事件的因果先后,不关心物理时间),以及后来的向量时钟;工程上则有 NTP/PTP 时钟同步,Google Spanner 的 TrueTime 更进一步,用 GPS 和原子钟把时钟误差限定在一个已知区间内,再通过”等待误差区间过去”来保证全局顺序。

MPI 学习资源

MPI Resources

MPI 庞大而复杂,本节只是触及了皮毛。想进一步了解 MPI,我们推荐:

MPI is large and complex, and this section hardly scratches the surface. For more information about MPI, we suggest:

  • 劳伦斯·利弗莫尔国家实验室(LLNL)Blaise Barney 编写的 MPI 教程。
  • The Lawrence Livermore National Lab’s MPI tutorial, by Blaise Barney.