CS267 · 第 7 课 · Aydin Buluc

分布式内存机器与 MPI 编程

分布式内存系统通过高速网络连接独立的节点。MPI（Message Passing Interface）是分布式内存编程的工业标准，通过消息传递实现进程间通信。

授课教师：Aydin Buluc

日期：2025-02-11

难度：中等

视频：Lecture 7 Video

分布式内存架构

架构演进

TOP500 中系统架构的演进：

早期：单机、SMP、Cluster、MPP、SIMD
现在：Cluster 和 MPP 占主导

历史视角

早期分布式内存机器：

微处理器集合
通过双向队列在最近邻之间通信
消息由路径上的处理器转发（"store and forward" 网络）
强调拓扑以最小化跳数

通信网络

网络类比

网络就像街道系统：

Link = 街道
Switch = 十字路口
距离 (hops) = 经过的街区数
Routing algorithm = 行程规划

网络属性

属性	描述
Topology	连接方式（crossbar、ring、mesh、torus、hypercube、tree、butterfly、dragonfly）
Routing	路由算法（避免死锁）
Switching	Circuit switching vs Packet switching
Flow control	拥塞控制（stall、buffer、reroute、halt）

延迟 (Latency)

Diameter：任意两节点间最长最短路径
Latency：发送和接收之间的延迟
软件延迟 >> 硬件延迟（1-10 μs vs 10-100 ns/hop）
延迟随时间改善不大（不像摩尔定律）

带宽 (Bandwidth)

链路带宽 = 线数 / 每比特时间
有效带宽 < 物理带宽（包头开销）
带宽取决于软件栈，不只是硬件

Bisection Bandwidth（对分带宽）

将对网络切成两半的最小割的带宽：

拓扑	Bisection BW
Linear Array	1
Ring	2
2D Mesh	\(\sqrt{n}\)
2D Torus	\(2\sqrt{n}\)
Hypercube	\(n/2\)

网络拓扑

拓扑	Diameter	Bisection BW	特点
Linear/Ring	\(O(n)\) / \(O(n)\)	1 / 2	简单，但可扩展性差
2D Mesh	\(2(\sqrt{n}-1)\)	\(\sqrt{n}\)	适合 2D 数组
2D Torus	\(\sqrt{n}\)	\(2\sqrt{n}\)	Cray XT (Hopper) 使用 3D Torus
Hypercube	\(\log n\)	\(n/2\)	早期机器（Intel iPSC, NCUBE）
Tree	\(\log n\)	1	Fat Tree 解决带宽瓶颈
Butterfly	\(\log n\)	\(n\)	Hypercube 的展开版本
Dragonfly	~5 hops	-	Edison、Cori 使用

Dragonfly 拓扑

利用光互连（机柜间）和电互连（机柜内）的成本/性能差异：

多个 group 全连接
每个 group 内部可以是任意拓扑
使用随机路由算法（Valiant, 1982）
程序员通常可以忽略拓扑

性能模型

α-β 模型

发送长度为 n 的消息的时间：

\[T = \alpha + n \cdot \beta\]

\(\alpha\)：延迟（启动开销）
\(\beta\)：每字传输时间的倒数（带宽的倒数）
通常 \(\alpha \gg \beta \gg\) 每 flop 时间

教训：一条长消息比许多短消息便宜。需要大的计算/通信比才能高效。

PRAM 模型

Parallel Random Access Memory：

所有内存操作在一个时钟周期完成
忽略内存层次和通信成本
适合判断算法是否有足够的并行性
更现实的变体：CREW PRAM、Work-span model

MPI 编程

Message Passing Libraries

历史上多种消息传递库：

PVM、CMMD、Express、MPL、NX、Chameleon
MPI (Message Passing Interface) 现在是工业标准

MPI 的特性

Communicators：封装通信空间，保证库安全
Datatypes：减少拷贝成本，支持异构
Multiple communication modes：精确缓冲管理
Extensive collective operations：可扩展的全局通信
Process topologies：有效的进程布局

Hello World in MPI

#include "mpi.h"
#include <stdio.h>

int main(int argc, char *argv[]) {
  int rank, size;
  MPI_Init(&argc, &argv);
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  MPI_Comm_size(MPI_COMM_WORLD, &size);
  printf("I am %d of %d\n", rank, size);
  MPI_Finalize();
  return 0;
}

运行：mpirun -np 4 a.out

核心函数

大多数 MPI 程序只需 6 个函数：

Point-to-point	Collective
MPI_INIT	MPI_INIT
MPI_FINALIZE	MPI_FINALIZE
MPI_COMM_SIZE	MPI_COMM_SIZE
MPI_COMM_RANK	MPI_COMM_RANK
MPI_SEND	MPI_BCAST
MPI_RECV	MPI_REDUCE

基本 Send/Receive

// 发送
MPI_Send(start, count, datatype, dest, tag, comm);

// 接收
MPI_Recv(start, count, datatype, source, tag, comm, status);

示例：计算 π

// 每个进程计算自己的部分
h = 1.0 / n;
sum = 0.0;
for (i = myid + 1; i <= n; i += numprocs) {
  x = h * (i - 0.5);
  sum += 4.0 * sqrt(1.0 - x*x);
}
mypi = h * sum;

// 归约
MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);

阻塞与非阻塞通信

阻塞通信

MPI_Send：返回时数据已交付系统，但可能未被接收
MPI_Recv：返回时缓冲区已满

死锁问题

// "Unsafe" 代码 — 依赖系统缓冲
Process 0: Send(1)  Recv(1)
Process 1: Send(0)  Recv(0)
// 大消息时可能死锁！

解决方案

方案	描述
MPI_Sendrecv	同时发送和接收
MPI_Bsend	用户提供的缓冲
MPI_Isend/Irecv	非阻塞操作

非阻塞通信

MPI_Request request;
MPI_Status status;

// 非阻塞发送
MPI_Isend(start, count, datatype, dest, tag, comm, &request);
// 非阻塞接收
MPI_Irecv(start, count, datatype, source, tag, comm, &request);

// 等待完成
MPI_Wait(&request, &status);

// 或测试是否完成
MPI_Test(&request, &flag, &status);

通信模式

模式	描述
`MPI_Send`	标准模式（实现决定缓冲）
`MPI_Ssend`	同步模式（等待接收开始）
`MPI_Bsend`	缓冲模式（用户提供缓冲）
`MPI_Rsend`	就绪模式（接收已发布）

测验

Q1：α-β 模型中，\(\alpha\) 和 \(\beta\) 分别代表什么？

Q2：2D Torus 的直径是多少？

Q3：非阻塞通信的主要优点是什么？

Q4：MPI 中，大多数程序最少需要几个函数？

Q5：Dragonfly 拓扑使用什么路由算法？

要点总结

网络拓扑很重要

不同拓扑有不同的直径、对分带宽和成本。现代系统（Dragonfly）使用层次化拓扑。

α-β 模型指导优化

延迟 \(\alpha\) 远大于带宽倒数 \(\beta\)。需要大的计算/通信比才能高效。

MPI 是标准

MPI 提供了丰富的通信原语。大多数程序只需 6 个函数。

非阻塞通信隐藏延迟

MPI_Isend/Irecv 允许重叠通信和计算，是高性能的关键。