CS267 · 第 8 课 · Aydin Buluc

高级 MPI 与集合通信算法

集合通信（Collective Communication）是 MPI 的核心功能，包括广播、归约、全收集等。理解其底层算法（Ring、Recursive Doubling、Bruck 等）对于实现可扩展的并行程序至关重要。

授课教师：Aydin Buluc

日期：2025-02-13

难度：高级

视频：Lecture 8 Video

分布式深度学习全靠集合通信

现代分布式深度学习框架（如 Horovod、NCCL）高度依赖集合通信：

AllReduce：梯度同步
AllGather：分布式推理
Broadcast：参数分发

集合通信操作

数据移动

操作	描述
Broadcast	一个进程发送数据给所有进程
Scatter	一个进程分发数据块给所有进程
Gather	从所有进程收集数据到一个进程
AllGather	所有进程收集完整数据
Alltoall	每个进程向每个进程发送不同数据

数据移动 + 计算

操作	描述
Reduce	归约（sum、max 等）到一个进程
AllReduce	归约到所有进程
Reduce_scatter	归约后分散
Scan	前缀和

MPI 集合例程

MPI 提供大量集合例程：

MPI_Allgather, MPI_Allgatherv, MPI_Allreduce, MPI_Alltoall, MPI_Alltoallv,
MPI_Bcast, MPI_Gather, MPI_Gatherv, MPI_Reduce, MPI_Reduce_scatter,
MPI_Scan, MPI_Scatter, MPI_Scatterv

所有版本将结果交付给所有参与进程
v 版本允许变长块
AllReduce、Reduce、Reduce_scatter、Scan 支持用户定义的 combiner 函数

SUMMA 矩阵乘法

算法描述

SUMMA (Scalable Universal Matrix Multiply) 是分布式内存矩阵乘法的经典算法：

// 假设 pr × pc 处理器网格
for k = 0 to n-1 (或 n/b-1)
  for all I = 1 to pr in parallel
    A(I,k) 的拥有者广播到整行
  for all J = 1 to pc in parallel
    B(k,J) 的拥有者广播到整列
  C(myproc, myproc) += Acol * Brow

MPI 实现

void SUMMA(double *mA, double *mB, double *mC, int p_c) {
  int row_color = rank / p_c;
  MPI_Comm row_comm;
  MPI_Comm_split(MPI_COMM_WORLD, row_color, rank, &row_comm);

  int col_color = rank % p_c;
  MPI_Comm col_comm;
  MPI_Comm_split(MPI_COMM_WORLD, col_color, rank, &col_comm);

  for (int k = 0; k < p_c; ++k) {
    if (col_color == k) memcpy(Atemp, mA, size);
    if (row_color == k) memcpy(Btemp, mB, size);
    MPI_Bcast(Atemp, size, MPI_DOUBLE, k, row_comm);
    MPI_Bcast(Btemp, size, MPI_DOUBLE, k, col_comm);
    SimpleDGEMM(Atemp, Btemp, mC, N/p, N/p, N/p);
  }
}

使用非阻塞通信重叠

for (int k = 0; k < p_c-1; ++k) {
  // 启动下一次迭代的广播
  MPI_Ibcast(Atemp2, ..., &reqs2[0]);
  MPI_Ibcast(Btemp2, ..., &reqs2[1]);

  // 等待当前迭代的广播完成
  MPI_Waitall(reqs1, MPI_STATUS_IGNORE);
  // 计算
  SimpleDGEMM(Atemp1, Btemp1, mC, ...);

  // 交换缓冲区
  swap(Atemp1, Atemp2);
  swap(Btemp1, Btemp2);
  swap(reqs1, reqs2);
}

集合通信算法

AllGather

Ring 算法

时间 t: 将 t-1 时刻收到的数据发给右边，从左边接收新数据
时间 0: 发送自己的原始数据

Tring = α(P-1) + βn(P-1)/P

最优带宽，高延迟
流水线化后效果不错
NCCL 独家使用流水线 Ring 算法

Recursive Doubling 算法

时间 t: 进程 i 与进程 i+2^t 交换所有当前数据
每步交换数据量: n/P, 2n/P, 4n/P, ...

Trec-dbl = α log₂(P) + βn(P-1)/P

低延迟，高带宽
非 2 的幂时较复杂

Bruck 算法

时间 t: 进程 i 从 i+2^t 接收，向 i-2^t 发送
⌊log₂(P)⌋ 步后完成

Tbrock = α ⌈log₂(P)⌉ + βn(P-1)/P

适用于任意 P
比 Recursive Doubling 更适合非 2 的幂

Broadcast

Binomial Tree 算法

时间 0: root 发送给 P/2
时间 1: root 和 P/2 同时发送给 P/4 和 3P/4
...
深度 log₂(P)

Tbcast = α log₂(P) + βn log₂(P)

Scatter + AllGather

// 先用 binomial tree Scatter n 个字
// 再用 recursive doubling AllGather n/P 个字
Tbcast = α 2log₂(P) + β2n(P-1)/P  (当 n ≥ P)

集合通信复杂度对比

操作	算法	时间
Broadcast	Binomial Tree	\(\alpha \log P + \beta n \log P\)
Broadcast	Scatter+AllGather	\(\alpha 2\log P + \beta 2n(P-1)/P\)
Reduce	Binomial Tree	\(\alpha \log P + \beta n \log P\)
AllReduce	Ring	\(2\alpha(P-1)/P + 2\beta n(P-1)/P\)
AllReduce	Recursive Doubling	\(\alpha \log P + \beta n \log P\)
AllGather	Ring	\(\alpha(P-1) + \beta n(P-1)/P\)
AllGather	Recursive Doubling	\(\alpha \log P + \beta n(P-1)/P\)
Alltoall	Bruck	\(\alpha \log P + \beta n(P-1)/P\)

非阻塞集合通信

MPI 4.0 引入非阻塞集合操作：

MPI_Ibcast(&buf, count, datatype, root, comm, &req);
MPI_Iallreduce(sendbuf, recvbuf, count, datatype, op, comm, &req);
// ...

语义优势

启用异步推进（软件流水线）
解耦数据传输和同步
抗噪声能力
允许重叠 communicator

限制

无 tag，顺序匹配
发送/向量缓冲区在操作期间不能被修改
不能与阻塞集合操作混合

混合编程：MPI + Threads

为什么需要混合编程？

现代集群的节点通常有多核 CPU：

模式	描述
All MPI	节点间和节点内都用 MPI
MPI + OpenMP	节点内用 OpenMP，节点间用 MPI
MPI + Pthreads	节点内用 Pthreads，节点间用 MPI

MPI 线程安全级别

级别	描述
`MPI_THREAD_SINGLE`	只有一个线程
`MPI_THREAD_FUNNELED`	多线程，只有主线程调用 MPI
`MPI_THREAD_SERIALIZED`	多线程，但一次只有一个调用 MPI
`MPI_THREAD_MULTIPLE`	多线程，任何线程随时可调用 MPI

注意：

所有实现都支持 MPI_THREAD_SINGLE
大多数支持 MPI_THREAD_FUNNELED
许多支持 MPI_THREAD_MULTIPLE（但实现效率不同）
简单的 OpenMP 程序只需 FUNNELED 级别

MPI_THREAD_MULTIPLE 的语义

Ordering：多个线程并发调用 MPI，结果如同顺序执行（任意顺序）
Blocking：阻塞调用只阻塞调用线程，不阻止其他线程
用户必须确保同一 communicator 上的集合操作正确排序

单边通信 (One-sided Communication / RMA)

基本概念

单边通信将数据移动与进程同步解耦：

每个进程暴露一部分内存给其他进程
其他进程可以直接读写这部分内存
不需要远程进程同步

与双边通信对比

双边 (Two-sided)	单边 (One-sided)
SEND(data) / RECV(data)	PUT(data) / GET(data)
发送进程被延迟	源进程不被延迟
需要同步	无需同步

MPI RMA 操作

操作	描述
`MPI_Win_create`	创建可远程访问的内存区域（window）
`MPI_Put`	写入远程内存
`MPI_Get`	读取远程内存
`MPI_Accumulate`	原子累加到远程内存
`MPI_Win_fence`	同步（active target）
`MPI_Win_lock/unlock`	同步（passive target）

Window 创建模型

模型	描述
`MPI_WIN_CREATE`	已有 buffer，使其可远程访问
`MPI_WIN_ALLOCATE`	创建 buffer 并使其可远程访问
`MPI_WIN_CREATE_DYNAMIC`	创建空 window，动态 attach/detach
`MPI_WIN_ALLOCATE_SHARED`	节点内多进程共享 buffer

同步模型

模型	描述
Fence	Active target，集体同步
Post-Start-Complete-Wait	Generalized active target
Lock/Unlock	Passive target，单边异步

测验

Q1：SUMMA 算法中，每个处理器负责计算哪个子矩阵？

Q2：AllGather 的 Ring 算法的时间复杂度是多少？

Q3：MPI_THREAD_MULTIPLE 的主要限制是什么？

Q4：单边通信（RMA）相比双边通信的主要优点是什么？

Q5：Broadcast 的 Binomial Tree 算法的时间复杂度是多少？

要点总结

SUMMA 是经典

SUMMA 算法通过行/列广播实现分布式矩阵乘法，易于泛化和重叠。

集合通信有讲究

Ring、Recursive Doubling、Bruck 等算法各有优劣，适用于不同规模和操作。

非阻塞集合通信

MPI 4.0 的非阻塞集合操作允许软件流水线和异步推进。

混合编程是趋势

MPI + OpenMP/Pthreads 混合编程是现代多核集群的标准做法。

高级 MPI 与集合通信算法

分布式深度学习全靠集合通信

集合通信操作

数据移动

数据移动 + 计算

MPI 集合例程

SUMMA 矩阵乘法

算法描述

MPI 实现

使用非阻塞通信重叠

集合通信算法

AllGather

Ring 算法

Recursive Doubling 算法

Bruck 算法

Broadcast

Binomial Tree 算法

Scatter + AllGather

集合通信复杂度对比

非阻塞集合通信

语义优势

限制

混合编程：MPI + Threads

为什么需要混合编程？

MPI 线程安全级别

MPI_THREAD_MULTIPLE 的语义

单边通信 (One-sided Communication / RMA)

基本概念

与双边通信对比

MPI RMA 操作

Window 创建模型

同步模型

测验

要点总结

SUMMA 是经典

集合通信有讲究

非阻塞集合通信

混合编程是趋势

延伸阅读