跳到主要内容

集合通信算法延迟公式

本文是集合通信算法的 $\alpha$-$\beta$ 延迟公式手册。所有公式基于 Hockney $\alpha$-$\beta$ 模型，符号统一如下：

  • $N$：参与通信的节点数
  • $M$：消息总大小（字节）
  • $\alpha$：启动延迟（μs，实际取值通常在 1–10 μs 量级）
  • $\beta$：链路带宽（字节/秒；代入时需统一单位，如 $\alpha$ 取 μs 则 $M/\beta$ 也应换算为 μs）

AllReduce​

AllReduce 是最常用的集合通信原语，用于 TP 梯度合并和 DP 梯度同步。

Ring AllReduce（带宽最优）​

来源：Thakur et al., IJHPCA 2005

推导思路：$N$ 个节点排成逻辑环，数据等分为 $N$ 个 chunk（每个 $M/N$）。分两个阶段：

阶段 1 — ReduceScatter（$N-1$ 步）：每步节点 $i$ 将一个 chunk 发给 $(i+1) \bmod N$，同时接收来自 $(i-1) \bmod N$ 的 chunk 并归约。$N-1$ 步后每节点持有 $1/N$ 的完整归约结果。

$T_{\text{RS}} = (N-1)\alpha + \frac{N-1}{N} \cdot \frac{M}{\beta}$

阶段 2 — AllGather（$N-1$ 步）：逆向传播归约结果，每步 $M/N$ 字节。

$T_{\text{AG}} = (N-1)\alpha + \frac{N-1}{N} \cdot \frac{M}{\beta}$

合计：

$\boxed{T_{\text{Ring-AR}} = 2(N-1)\alpha + \frac{2(N-1)}{N} \cdot \frac{M}{\beta}}$

渐进分析：

  • 延迟项 $2(N-1)\alpha$：$O(N)$，$N=8$ 时 $14\alpha$，$N=1024$ 时 $2046\alpha$
  • 带宽系数 $\frac{2(N-1)}{N} \to 2$（$N \to \infty$）：理论最优带宽利用率
  • 适用：大消息（带宽 bound）场景

Recursive Halving-Doubling AllReduce（延迟与带宽均衡）​

也称 Rabenseifner 算法。来源：Rabenseifner, ICCS 2004（LNCS 3036）。要求 $N$ 为 2 的幂。

推导思路：分两个阶段，每阶段 $\log_2 N$ 轮。

阶段 1 — Recursive Halving（ReduceScatter）：第 $k$ 轮节点与距离 $2^k$ 的对手交换数据，每轮交换量为当前数据的一半：第 $k$ 轮交换 $M/2^{k+1}$ 字节。

$T_{\text{RS}} = \log_2 N \cdot \alpha + \frac{M}{\beta} \sum_{k=0}^{\log_2 N - 1} \frac{1}{2^{k+1}} = \log_2 N \cdot \alpha + \frac{N-1}{N} \cdot \frac{M}{\beta}$

阶段 2 — Recursive Doubling（AllGather）：逆向过程，第 $k$ 轮每节点发送 $M \cdot 2^k / N$ 字节（从 $M/N$ 开始翻倍），总量相同。

$T_{\text{AG}} = \log_2 N \cdot \alpha + \frac{N-1}{N} \cdot \frac{M}{\beta}$

合计：

$\boxed{T_{\text{RHD-AR}} = 2\log_2 N \cdot \alpha + \frac{2(N-1)}{N} \cdot \frac{M}{\beta}}$

渐进分析：

  • 延迟项 $2\log_2 N \cdot \alpha$：$O(\log N)$，$N=64$ 时 $12\alpha$（Ring 为 $126\alpha$）
  • 带宽系数 $\frac{2(N-1)}{N}$：与 Ring 完全相同，理论最优
  • 适用：兼具两者优点；缺点：要求 $N$ 为 2 的幂，每轮通信对手不固定（非环形拓扑不友好）

Double Binary Tree AllReduce（延迟最优）​

NCCL 默认的小消息算法。来源：Patarasuk & Yuan, JPDC 2009。

推导思路：使用两棵互补二叉树同时操作，数据对半分，两棵树使用不同的父子关系以利用双向带宽。

每棵树有 $\log_2 N$ 层，各处理 $M/2$ 字节：

  • Reduce 阶段：每层从叶到根，传输 $M/2$，共 $\log_2 N$ 步
  • Broadcast 阶段：每层从根到叶，传输 $M/2$，共 $\log_2 N$ 步

两棵树并行操作，每轮传输 $M/2$（两棵树合计 $M$）：

$\boxed{T_{\text{DBT-AR}} = 2\log_2 N \cdot \alpha + \log_2 N \cdot \frac{M}{\beta}}$

推导说明：Tree 算法中每轮传输的是完整数据 $M$（或 Double Tree 的 $M/2$），而非 Ring 的 $M/N$ 分块。因此带宽项不含 $1/N$ 因子，带宽系数为 $\log_2 N$。

渐进分析：

  • 延迟项 $2\log_2 N \cdot \alpha$：与 RHD 相同，$O(\log N)$
  • 带宽系数 $\log_2 N$：$N=8$ 时为 3，远高于 Ring 的 1.75——带宽效率差
  • 适用：小消息（延迟 bound）场景

算法对比与交叉点​

算法延迟项带宽系数（$N=8$）适用场景
Ring$2(N-1)\alpha = 14\alpha$1.75大消息，带宽 bound
Halving-Doubling$2\log_2 N \cdot \alpha = 6\alpha$1.75理论最优（需 $N$ 为 2 的幂）
Double Binary Tree$2\log_2 N \cdot \alpha = 6\alpha$3.0小消息，延迟 bound

Ring 与 DBT 的交叉点（$N=8$，$\alpha = 5\ \mu s$，$\beta = 450\ \text{GB/s}$）：

$M^* = \frac{2\alpha\beta \cdot [(N-1) - \log_2 N]}{\log_2 N - \frac{2(N-1)}{N}} = \frac{2 \times 5 \times 10^{-6} \times 450 \times 10^9 \times 4}{1.25} \approx 14.4\ \text{MB}$

消息 < 14.4 MB 时 DBT 更快，> 14.4 MB 时 Ring 更快。NCCL 内部有类似的自动切换逻辑。

AllGather 与 ReduceScatter​

这两个原语是 Ring AllReduce 的组成部分，也独立用于 SP（序列并行）和 ZeRO 优化。

Ring AllGather（$N-1$ 步）​

每个节点初始持有 $M/N$ 的本地分片，目标是所有节点拥有完整 $M$。

$\boxed{T_{\text{Ring-AG}} = (N-1)\alpha + \frac{N-1}{N} \cdot \frac{M}{\beta}}$

推导：$N-1$ 步，每步在环上传递一个 $M/N$ 的 chunk。

Ring ReduceScatter（$N-1$ 步）​

每个节点初始持有完整 $M$，目标是每个节点持有 $1/N$ 的归约结果。

$\boxed{T_{\text{Ring-RS}} = (N-1)\alpha + \frac{N-1}{N} \cdot \frac{M}{\beta}}$

与 AllGather 公式相同（对称性）。额外的归约操作与数据接收重叠（归约吞吐远高于通信带宽时可忽略归约时间）。

恒等关系：$T_{\text{Ring-AR}} = T_{\text{Ring-RS}} + T_{\text{Ring-AG}}$。

busbw 修正系数（来源：nccl-tests PERFORMANCE.md）：

操作busbw 系数含义
AllReduce$\frac{2(N-1)}{N}$Ring 双向传输效率
AllGather / ReduceScatter$\frac{N-1}{N}$单向传输效率
AllToAll$\frac{N-1}{N}$单向传输效率
Broadcast / Reduce1单流传输

AllToAll​

AllToAll 用于 MoE 的 EP 路由，每个节点向所有其他节点发送不同的数据块（每对节点之间 $M/N$ 字节）。

Pairwise 算法（$N-1$ 轮直接交换）​

来源：Thakur et al., IJHPCA 2005

推导思路：$N-1$ 轮，第 $k$ 轮节点 $i$ 与节点 $(i+k) \bmod N$ 交换 $M/N$ 字节。

$\boxed{T_{\text{A2A-Pair}} = (N-1)\left(\alpha + \frac{M}{N\beta}\right) = (N-1)\alpha + \frac{N-1}{N} \cdot \frac{M}{\beta}}$

渐进分析：延迟项 $O(N)$，带宽系数 $\frac{N-1}{N}$。

注意：在全互联网络（如 NVSwitch）中，所有 $N-1$ 轮可以并行（每对使用独立链路），此时 $T = \alpha + M/(N\beta)$。但共享链路拓扑无法实现此理想值。

Bruck 算法（小消息延迟最优）​

来源：Bruck et al., IEEE TPDS 1997。递归倍增策略，$\lceil\log_2 N\rceil$ 轮完成。

推导思路：第 $k$ 轮每节点向距离 $2^k$ 的目标打包发送多个 chunk，总带宽开销与 Pairwise 相同，但延迟项从 $(N-1)\alpha$ 降到 $\lceil\log_2 N\rceil \cdot \alpha$。

$\boxed{T_{\text{A2A-Bruck}} = \lceil\log_2 N\rceil \cdot \alpha + \frac{N-1}{N} \cdot \frac{M}{\beta}}$

渐进分析：延迟项 $O(\log N)$，带宽系数与 Pairwise 完全相同。

Ring 算法（环形拓扑友好）​

与 Pairwise 公式相同，但通信模式不同：Ring 每轮只与相邻节点通信（适合环形拓扑）：

$\boxed{T_{\text{A2A-Ring}} = (N-1)\alpha + \frac{N-1}{N} \cdot \frac{M}{\beta}}$

AllToAll 算法对比​

算法延迟项带宽系数适用场景
Pairwise$(N-1)\alpha$$\frac{N-1}{N}$全连接拓扑、小 $N$、均匀分布
Bruck$\lceil\log_2 N\rceil \alpha$$\frac{N-1}{N}$小消息、延迟敏感
Ring$(N-1)\alpha$$\frac{N-1}{N}$环形拓扑、大消息

关键观察：AllToAll 的所有算法带宽系数都是 $\frac{N-1}{N}$。差异仅在延迟项——Bruck 用 $O(\log N)$ 优于其他两者的 $O(N)$。但 Bruck 需要额外的本地数据重排，大消息时这个开销可能抵消延迟优势。

Broadcast / Reduce​

Tree Broadcast（$\log_2 N$ 步，延迟最优）：

$\boxed{T_{\text{Bcast}} = \log_2 N \cdot \left(\alpha + \frac{M}{\beta}\right)}$

推导：二叉树从根到叶，每层传输完整消息 $M$，共 $\log_2 N$ 层。

Tree Reduce（$\log_2 N$ 步）：对称操作，公式相同：

$\boxed{T_{\text{Reduce}} = \log_2 N \cdot \left(\alpha + \frac{M}{\beta}\right)}$

注意：Broadcast/Reduce 的 busbw 系数为 1（单流传输，只有根节点或叶节点发送/接收全部数据）。

参考文献​