集合通信算法延迟公式
核心要点：
- Ring AllReduce：延迟 $O(N)$，带宽系数 $2(N-1)/N \to 2$ 最优，适合大消息
- Halving-Doubling：延迟 $O(\log N)$，带宽系数与 Ring 相同，需 $N$ 为 2 的幂
- Double Binary Tree：延迟 $O(\log N)$，带宽系数 $\log_2 N$ 较差，适合小消息
- AllToAll: Pairwise / Ring 延迟 $O(N)$, Bruck $O(\log N)$，带宽系数都是 $(N-1)/N$
- 算法交叉点：Ring vs DBT 在 NVLink 8 GPU 下 $M^* \approx 14$ MB, NCCL 自动切换
本文是集合通信算法的 $\alpha$-$\beta$ 延迟公式手册。所有公式基于 Hockney $\alpha$-$\beta$ 模型，符号统一：
- $N$：参与通信的节点数
- $M$：消息总大小 （字节）
- $\alpha$：启动延迟 ($\mu s$，实际取值通常在 1–10 $\mu s$ 量级)
- $\beta$：链路带宽 (B/s，代入时需统一单位；$\alpha$ 取 $\mu s$ 则 $M/\beta$ 也应换算为 $\mu s$)
AllReduce 的三种算法是怎么推导的
核心问题：Ring / Halving-Doubling / Double Binary Tree 三种 AllReduce 在 $\alpha$-$\beta$ 下分别是什么形式？怎么选？
Ring AllReduce：带宽最优
来源：[Thakur et al., IJHPCA 2005][1].
推导思路：$N$ 个节点排成逻辑环，数据等分为 $N$ 个 chunk (每个 $M/N$)。分两个阶段。
阶段 1 — ReduceScatter ($N-1$ 步)：每步节点 $i$ 将一个 chunk 发给 $(i+1) \bmod N$，同时接收来自 $(i-1) \bmod N$ 的 chunk 并归约。$N-1$ 步后每节点持有 $1/N$ 的完整归约结果。
$$\begin{equation} T_{\text{RS}} = (N-1)\alpha + \frac{N-1}{N} \cdot \frac{M}{\beta} \label{eq:model-algo-ring-rs} \end{equation}$$阶段 2 — AllGather ($N-1$ 步)：逆向传播归约结果，每步 $M/N$ 字节：
$$\begin{equation} T_{\text{AG}} = (N-1)\alpha + \frac{N-1}{N} \cdot \frac{M}{\beta} \label{eq:model-algo-ring-ag} \end{equation}$$合计：
$$\begin{equation} \boxed{T_{\text{Ring-AR}} = 2(N-1)\alpha + \frac{2(N-1)}{N} \cdot \frac{M}{\beta}} \label{eq:model-algo-ring-ar} \end{equation}$$渐进分析：
- 延迟项 $2(N-1)\alpha$: $O(N)$, $N=8$ 时 $14\alpha$, $N=1024$ 时 $2046\alpha$
- 带宽系数 $2(N-1)/N \to 2$ ($N \to \infty$): 理论最优带宽利用率
- 适用：大消息 （带宽 bound） 场景
Recursive Halving-Doubling：延迟与带宽均衡
也称 Rabenseifner 算法 (Rabenseifner, ICCS 2004, LNCS 3036)，要求 $N$ 为 2 的幂。
推导思路：分两阶段，每阶段 $\log_2 N$ 轮。
阶段 1 — Recursive Halving (ReduceScatter)：第 $k$ 轮节点与距离 $2^k$ 的对手交换数据，每轮交换量为当前数据的一半 (第 $k$ 轮交换 $M/2^{k+1}$ 字节):
$$\begin{equation} 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} \label{eq:model-algo-rhd-rs} \end{equation}$$阶段 2 — Recursive Doubling (AllGather)：逆向过程，第 $k$ 轮每节点发送 $M \cdot 2^k / N$ 字节 (从 $M/N$ 开始翻倍)，总量相同：
$$\begin{equation} T_{\text{AG}} = \log_2 N \cdot \alpha + \frac{N-1}{N} \cdot \frac{M}{\beta} \label{eq:model-algo-rhd-ag} \end{equation}$$合计：
$$\begin{equation} \boxed{T_{\text{RHD-AR}} = 2\log_2 N \cdot \alpha + \frac{2(N-1)}{N} \cdot \frac{M}{\beta}} \label{eq:model-algo-rhd-ar} \end{equation}$$渐进分析：
- 延迟项 $2\log_2 N \cdot \alpha$: $O(\log N)$, $N=64$ 时 $12\alpha$ (Ring 为 $126\alpha$)
- 带宽系数 $2(N-1)/N$：与 Ring 完全相同，理论最优
- 适用：兼具两者优点；缺点是要求 $N$ 为 2 的幂，每轮通信对手不固定 （非环形拓扑不友好）
Double Binary Tree：延迟最优
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$):
$$\begin{equation} \boxed{T_{\text{DBT-AR}} = 2\log_2 N \cdot \alpha + \log_2 N \cdot \frac{M}{\beta}} \label{eq:model-algo-dbt-ar} \end{equation}$$推导说明：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 |
@tbl-model-algo-allreduce-compare AllReduce 三种算法的延迟项 / 带宽系数对比
Ring 与 DBT 的交叉点 ($N=8$, $\alpha = 5\ \mu s$, $\beta = 450$ GB/s):
$$\begin{equation} 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} \label{eq:model-algo-ring-dbt-crossover} \end{equation}$$消息 < 14.4 MB 时 DBT 更快，> 14.4 MB 时 Ring 更快。NCCL 内部有类似的自动切换逻辑。
AllGather / ReduceScatter 的公式是什么
核心问题：这两个原语是 Ring AllReduce 的分量，公式跟 AllReduce 是什么关系？
这两个原语是 Ring AllReduce 的组成部分，也独立用于 SP （序列并行） 和 ZeRO 优化。
Ring AllGather ($N-1$ 步)
每个节点初始持有 $M/N$ 的本地分片，目标是所有节点拥有完整 $M$。
$$\begin{equation} \boxed{T_{\text{Ring-AG}} = (N-1)\alpha + \frac{N-1}{N} \cdot \frac{M}{\beta}} \label{eq:model-algo-ring-allgather} \end{equation}$$推导：$N-1$ 步，每步在环上传递一个 $M/N$ 的 chunk。
Ring ReduceScatter ($N-1$ 步)
每个节点初始持有完整 $M$，目标是每个节点持有 $1/N$ 的归约结果：
$$\begin{equation} \boxed{T_{\text{Ring-RS}} = (N-1)\alpha + \frac{N-1}{N} \cdot \frac{M}{\beta}} \label{eq:model-algo-ring-reducescatter} \end{equation}$$与 AllGather 公式相同 （对称性）。额外的归约操作与数据接收重叠 （归约吞吐远高于通信带宽时可忽略归约时间）。
恒等关系：$T_{\text{Ring-AR}} = T_{\text{Ring-RS}} + T_{\text{Ring-AG}}$。
busbw 修正系数
来源：nccl-tests PERFORMANCE.md.
| 操作 | busbw 系数 | 含义 |
|---|---|---|
| AllReduce | $2(N-1)/N$ | Ring 双向传输效率 |
| AllGather / ReduceScatter | $(N-1)/N$ | 单向传输效率 |
| AllToAll | $(N-1)/N$ | 单向传输效率 |
| Broadcast / Reduce | 1 | 单流传输 |
@tbl-model-algo-busbw-coef 各集合通信操作的 busbw 修正系数
AllToAll 算法怎么选
核心问题：AllToAll 用于 MoE EP 路由，Pairwise / Bruck / Ring 三种算法差异在哪？
AllToAll 用于 MoE 的 EP 路由，每个节点向所有其他节点发送不同的数据块 (每对节点之间 $M/N$ 字节)。
Pairwise: $N-1$ 轮直接交换
来源：[Thakur et al., IJHPCA 2005][1].
推导思路：$N-1$ 轮，第 $k$ 轮节点 $i$ 与节点 $(i+k) \bmod N$ 交换 $M/N$ 字节：
$$\begin{equation} \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}} \label{eq:model-algo-a2a-pairwise} \end{equation}$$渐进分析：延迟项 $O(N)$，带宽系数 $(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$:
$$\begin{equation} \boxed{T_{\text{A2A-Bruck}} = \lceil\log_2 N\rceil \cdot \alpha + \frac{N-1}{N} \cdot \frac{M}{\beta}} \label{eq:model-algo-a2a-bruck} \end{equation}$$渐进分析：延迟项 $O(\log N)$，带宽系数与 Pairwise 完全相同。
Ring：环形拓扑友好
与 Pairwise 公式相同，但通信模式不同 — Ring 每轮只与相邻节点通信 （适合环形拓扑）：
$$\begin{equation} \boxed{T_{\text{A2A-Ring}} = (N-1)\alpha + \frac{N-1}{N} \cdot \frac{M}{\beta}} \label{eq:model-algo-a2a-ring} \end{equation}$$三种 AllToAll 算法对比
| 算法 | 延迟项 | 带宽系数 | 适用场景 |
|---|---|---|---|
| Pairwise | $(N-1)\alpha$ | $(N-1)/N$ | 全连接拓扑，小 $N$，均匀分布 |
| Bruck | $\lceil\log_2 N\rceil \alpha$ | $(N-1)/N$ | 小消息，延迟敏感 |
| Ring | $(N-1)\alpha$ | $(N-1)/N$ | 环形拓扑，大消息 |
@tbl-model-algo-alltoall-compare AllToAll 三种算法的延迟项 / 带宽系数对比
关键观察：AllToAll 的所有算法带宽系数都是 $(N-1)/N$。差异仅在延迟项 — Bruck 用 $O(\log N)$ 优于其他两者的 $O(N)$。但 Bruck 需要额外的本地数据重排，大消息时这个开销可能抵消延迟优势。
Broadcast / Reduce 怎么用 Tree 算法
核心问题：单根 / 单汇集合操作的最优算法是什么？
Tree Broadcast ($\log_2 N$ 步，延迟最优):
$$\begin{equation} \boxed{T_{\text{Bcast}} = \log_2 N \cdot \left(\alpha + \frac{M}{\beta}\right)} \label{eq:model-algo-bcast-tree} \end{equation}$$推导：二叉树从根到叶，每层传输完整消息 $M$，共 $\log_2 N$ 层。
Tree Reduce ($\log_2 N$ 步)：对称操作，公式相同：
$$\begin{equation} \boxed{T_{\text{Reduce}} = \log_2 N \cdot \left(\alpha + \frac{M}{\beta}\right)} \label{eq:model-algo-reduce-tree} \end{equation}$$注意：Broadcast / Reduce 的 busbw 系数为 1 （单流传输，只有根节点或叶节点发送 / 接收全部数据）。
Takeaway
| 知识点 | 核心结论 |
|---|---|
| Ring AllReduce | $T = 2(N-1)\alpha + 2(N-1)/N \cdot M/\beta$，带宽最优，适合大消息 |
| Halving-Doubling | $T = 2\log_2 N \cdot \alpha + 2(N-1)/N \cdot M/\beta$，延迟 + 带宽双最优，需 $N=2^k$ |
| Double Binary Tree | $T = 2\log_2 N \cdot \alpha + \log_2 N \cdot M/\beta$，延迟最优，带宽差 |
| 交叉点 | Ring vs DBT 在 NVLink 8-GPU 下 $M^* \approx 14$ MB, NCCL 自动切换 |
| AllToAll | Pairwise / Ring $O(N)\alpha$, Bruck $O(\log N)\alpha$；带宽系数都是 $(N-1)/N$ |
| Broadcast / Reduce | Tree 算法 $\log_2 N \cdot (\alpha + M/\beta)$, busbw 系数 = 1 |
参考资料
- Thakur et al., Optimization of Collective Communication Operations in MPICH, IJHPCA 2005. https://journals.sagepub.com/doi/10.1177/1094342005051521