跳到主要内容

AllReduce

AllReduce 对所有节点的数据执行规约运算，且每个节点都获得完整的规约结果。它是分布式训练中梯度同步（DP）和张量并行（TP）的核心通信原语。

语义定义​

输入：每个节点 $i$ 持有数据 $A_i$，大小 $M$ 字节

输出：所有节点都持有规约结果：

$$\begin{equation} \forall i \in [0, N): \quad B_i = \bigoplus_{j=0}^{N-1} A_j \label{eq:allreduce-semantic} \end{equation}$$

等价分解​

AllReduce 可以分解为两种等价的子操作组合：

$$\begin{equation} \text{AllReduce} = \text{Reduce}(\text{to root}) + \text{Broadcast}(\text{from root}) \label{eq:allreduce-decomp-reduce-bcast} \end{equation}$$ $$\begin{equation} \text{AllReduce} = \text{ReduceScatter} + \text{AllGather} \label{eq:allreduce-decomp-rs-ag} \end{equation}$$

分解 2 通常更优，因为 ReduceScatter 和 AllGather 都可以用带宽最优的 Ring 算法实现。

带宽下界推导​

带宽下界的通用推导框架见 01-理论下界。

语义：$N$ 个节点各持有 $M$ 字节数据，操作完成后每个节点都持有所有数据的规约结果（$M$ 字节）。

推导（来源：Patarasuk & Yuan, JPDC 2009）：

考虑任意一个节点 $i$。操作完成后，节点 $i$ 持有的规约结果中包含了其他 $N-1$ 个节点的贡献。这些贡献必须通过网络传入节点 $i$。

将最终结果向量 $M$ 字节按位置划分，考虑每一个字节位置 $j$（$j = 1, \ldots, M$）。结果的第 $j$ 字节是所有 $N$ 个节点的第 $j$ 字节的规约。对节点 $i$ 来说，其他 $N-1$ 个节点的第 $j$ 字节信息必须通过某条路径传入节点 $i$。

现在从节点 $i$ 的角度做一个"切割"论证：将 $N$ 个节点分为两组——{节点 $i$} 和 {其他 $N-1$ 个节点}。操作完成后，节点 $i$ 持有的结果中，每个字节位置都包含了 $N-1$ 个外部节点的贡献。由于规约是不可逆的（从规约结果无法还原各节点的原始值），外部节点必须向节点 $i$ 传输足够多的信息，使得规约可以在节点 $i$ 本地完成。

关键是：节点 $i$ 不需要接收全部 $(N-1) \cdot M$ 字节的原始数据。通过中间规约（如 Ring 算法中的逐步累加），传入节点 $i$ 的可以是部分规约后的结果。但最终结果的 $M$ 个字节中，每个字节都需要外部贡献，因此节点 $i$ 至少需要接收：

$$\begin{equation} R_i \ge \frac{N-1}{N} \cdot M \label{eq:allreduce-recv-lower-bound} \end{equation}$$

这个下界的推导如下：将 $M$ 字节的结果向量分为 $N$ 份，每份 $M/N$。考虑第 $k$ 份（$k \ne i$），这份结果需要节点 $k$ 的数据参与规约。即使其他 $N-2$ 个节点的贡献已经被预先归约，节点 $k$ 的贡献仍需从外部传入节点 $i$。总共有 $N-1$ 个这样的份（排除节点 $i$ 自己可以本地计算的那 $1/N$ 份），因此接收量至少为 $\frac{N-1}{N} \cdot M$。

同理，从发送方分析：节点 $i$ 的原始数据需要传递到其他 $N-1$ 个节点的规约结果中。即使借助中间节点转发，节点 $i$ 至少需要发送：

$$\begin{equation} S_i \ge \frac{N-1}{N} \cdot M \label{eq:allreduce-send-lower-bound} \end{equation}$$

因此 AllReduce 的带宽下界为：

$$\begin{equation} T_{\beta}^{\min}(\text{AllReduce}) = \frac{(N-1) \cdot M}{N \cdot d \cdot \beta} \label{eq:allreduce-bw-lower-bound} \end{equation}$$

Ring AllReduce 的带宽最优性

Ring AllReduce 分解为 ReduceScatter + AllGather 两个阶段（见公式 $(\ref{eq:reducescatter-bw-lower-bound})$ 和 $(\ref{eq:allgather-bw-lower-bound})$），每阶段 $N-1$ 步，每步每个节点传输 $M/N$。因此每个节点的单方向总传输量为：

$$\begin{equation} \frac{2(N-1)}{N} \cdot M \label{eq:ring-allreduce-total-transfer} \end{equation}$$

其中 ReduceScatter 和 AllGather 各贡献 $\frac{N-1}{N} \cdot M$ 的传输量，每阶段都将链路带宽跑满（无空闲），总时间恰好是带宽下界 $(\ref{eq:allreduce-bw-lower-bound})$ 的 2 倍——这正是 Ring 被称为"带宽最优"的含义：链路利用率达到 100%，不可能用更少的传输量完成 AllReduce。

NCCL 性能测试中常用的 busbw（总线带宽）指标通过修正系数 $\frac{2(N-1)}{N}$ 将算法带宽（algbw = $M/T$）换算为单链路实际承载带宽，用于和硬件峰值带宽直接对比：

$$\begin{equation} \text{busbw} = \frac{M}{T} \times \frac{2(N-1)}{N} \label{eq:busbw-correction} \end{equation}$$

当 Ring AllReduce 达到带宽最优时，busbw 趋近硬件链路带宽 $\beta$。

2-port 双向 Ring AllReduce

当硬件支持 2-port（如 SG2260 的 CDMA + VSDMA 双引擎），Ring 上每个节点可以同时向左右两个邻居发送数据。此时 AllReduce 的执行方式发生本质变化：

  • ReduceScatter：$N$ 个 chunk 分成两半，一半沿顺时针传播，另一半沿逆时针传播。每步每个节点同时左发 + 右发，$\lceil N/2 \rceil$ 步后每个节点拥有 2 个完整规约的 chunk
  • AllGather：同样双向广播，$\lceil N/2 \rceil$ 步完成

总时间（忽略延迟项）：

$$\begin{equation} T_{\beta}^{\text{2-port Ring AR}} = 2 \cdot \lceil N/2 \rceil \cdot \frac{M/N}{\beta} = \frac{\lceil N/2 \rceil}{N/2} \cdot \frac{M}{\beta} \approx \frac{M}{\beta} \label{eq:bidir-ring-allreduce-time} \end{equation}$$

与 1-port 的对比：

指标1-port Ring2-port 双向 Ring
RS 步数$N-1$$\lceil N/2 \rceil$
AG 步数$N-1$$\lceil N/2 \rceil$
总步数$2(N-1)$$N$（$\approx$ 减半）
带宽项$\frac{2(N-1)}{N} \cdot \frac{M}{\beta}$$\frac{M}{\beta}$
延迟项$2(N-1) \cdot \alpha$$N \cdot \alpha$

2-port 双向 Ring 的带宽项 $\frac{M}{\beta}$ 仍然是带宽最优的——它的总传输量不变（每个节点仍需收发 $\frac{2(N-1)}{N}M$），但利用了双向并行将时间压缩了约一半。

理论下界​

延迟下界​

每个节点需要从其他 $N-1$ 个节点获取信息。每步每个已有信息的节点最多传给 1 个新节点，$k$ 步后最多 $2^k$ 个节点获得信息，因此至少需要 $\lceil \log_2 N \rceil$ 步：

$$\begin{equation} T_{\alpha}^{\min} = \lceil \log_2 N \rceil \cdot \alpha \label{eq:ar-delay-lb} \end{equation}$$

对 Ring 拓扑（直径 $\lfloor N/2 \rfloor$），当 $N > 4$ 时拓扑约束更紧：$T_{\alpha}^{\min}(\text{Ring}) = \lfloor N/2 \rfloor \cdot \alpha$。

带宽下界​

节点 $i$ 最终持有的 $M$ 字节规约结果中，每个字节都包含其他 $N-1$ 个节点的贡献。将结果分为 $N$ 份，其中 $N-1$ 份需要外部数据传入，因此节点 $i$ 至少接收 $\frac{N-1}{N}M$；对称地，至少发送 $\frac{N-1}{N}M$（详细推导见 01-理论下界）：

$$\begin{equation} T_{\beta}^{\min} = \frac{(N-1)M}{N\beta} \label{eq:ar-bw-lb} \end{equation}$$

综合下界​

$$\begin{equation} T_{\text{AllReduce}}^{\min} = \max\left(\lceil \log_2 N \rceil \cdot \alpha, \quad \frac{(N-1)M}{N\beta}\right) \label{eq:ar-combined-lb} \end{equation}$$

算法一：Ring AllReduce​

Ring AllReduce 是最重要的带宽最优算法，将 AllReduce 分解为 ReduceScatter + AllGather 两个阶段。

前提​

  • $N$ 个节点组成 Ring：$0 \to 1 \to 2 \to ... \to N-1 \to 0$
  • 消息均分为 $N$ 个 chunk，每 chunk 大小 $M/N$

阶段 1：ReduceScatter​

目标：$N-1$ 步后，节点 $i$ 拥有 chunk $(i+1) \bmod N$ 的完全规约结果。

第 $s$ 步（$s = 0, ..., N-2$），每个节点 $i$：

  1. 将当前持有的 chunk $(i-s) \bmod N$ 发送给节点 $(i+1) \bmod N$
  2. 从节点 $(i-1) \bmod N$ 接收 chunk $(i-1-s) \bmod N$
  3. 将收到的数据与本地对应 chunk 执行规约

4 节点 Step 1：Node 0 发 chunk 0 → Node 1（Node 1 规约），Node 1 发 chunk 1 → Node 2，依此类推。经 $N-1$ 步后每节点持有一个 chunk 的完全规约结果。

阶段 2：AllGather​

将每个节点的完全规约 chunk 沿 Ring 传播，$N-1$ 步后所有节点持有完整结果。

代价推导​

ReduceScatter 阶段：共 $N-1$ 步，每步每个节点发送 1 个 chunk（$M/N$ 字节）给右邻，从左邻接收 1 个 chunk 并本地规约。每步的代价为启动延迟 $\alpha$ 加上传输 $M/N$ 字节的时间 $\frac{M/N}{\beta}$，$N-1$ 步累加：

$$\begin{equation} T_{\text{RS}} = (N-1) \cdot \left(\alpha + \frac{M/N}{\beta}\right) = (N-1)\alpha + \frac{(N-1)M}{N\beta} \label{eq:allreduce-ring-rs-cost} \end{equation}$$

AllGather 阶段：同样 $N-1$ 步，每步传输 $M/N$ 字节（已规约的 chunk 沿 Ring 传播），代价结构与 ReduceScatter 完全对称：

$$\begin{equation} T_{\text{AG}} = (N-1)\alpha + \frac{(N-1)M}{N\beta} \label{eq:allreduce-ring-ag-cost} \end{equation}$$

合计（两阶段串行）：

$$\begin{equation} T_{\text{Ring}} = T_{\text{RS}} + T_{\text{AG}} = 2(N-1)\alpha + \frac{2(N-1)}{N} \cdot \frac{M}{\beta} \label{eq:ring-allreduce} \end{equation}$$

带宽最优性验证：每个节点在 ReduceScatter 阶段发送 $(N-1) \cdot M/N = \frac{(N-1)M}{N}$，AllGather 阶段同样发送 $\frac{(N-1)M}{N}$。每个阶段的发送量恰好等于带宽下界 $\eqref{eq:ar-bw-lb}$ 要求的最小值，因此 Ring AllReduce 是带宽最优的。

延迟非最优：延迟项 $2(N-1)\alpha$ 远大于下界 $\eqref{eq:ar-delay-lb}$ 的 $\lceil\log_2 N\rceil \cdot \alpha$，在 $N$ 大且消息小时退化严重。

双向 Ring 优化​

双向 Ring 将 $N$ 个 chunk 分两半分别沿顺/逆时针传播，步数减半：

$$\begin{equation} T_{\text{bidir-Ring}} \approx (N-1)\alpha + \frac{(N-1)}{N} \cdot \frac{M}{\beta} \label{eq:bidir-ring-allreduce} \end{equation}$$

SCCL 4 芯 AllReduce 实测（131072 FP16）：ReduceScatter 6.509 $\mu s$ + AllGather 5.752 $\mu s$ + 同步 3.496 $\mu s$ = 总 15.757 $\mu s$。

算法二：Recursive Halving-Doubling​

适合节点数为 $2^k$ 的场景，兼顾延迟和带宽，是大规模场景的最均衡选择。

核心思想​

分为两个阶段，每步通信距离翻倍/减半：

阶段 1（Recursive Halving = ReduceScatter）：将数据对半分，每步每个节点与翻转最高位对应的节点交换并规约：

步骤（$N=8$）通信对交换量
1(0,4)(1,5)(2,6)(3,7)$M/2$
2(0,2)(1,3)(4,6)(5,7)$M/4$
3(0,1)(2,3)(4,5)(6,7)$M/8$

阶段 2（Recursive Doubling = AllGather）：阶段 1 的逆过程，每步数据量翻倍。

代价推导​

ReduceScatter 阶段（Recursive Halving）：共 $\log_2 N$ 步。第 $j$ 步（$j=1,\ldots,\log_2 N$），每个节点与距离 $2^{\log_2 N - j}$ 的对手交换并规约当前持有数据的一半。交换量逐步减半：第 1 步 $M/2$，第 2 步 $M/4$，...，第 $j$ 步 $M/2^j$。

每步启动延迟 $\alpha$，带宽项为 $M/(2^j \beta)$。总代价：

$$\begin{equation} T_{\text{RS}} = \sum_{j=1}^{\log_2 N} \left(\alpha + \frac{M}{2^j \beta}\right) = \log_2 N \cdot \alpha + \frac{M}{\beta} \sum_{j=1}^{\log_2 N} \frac{1}{2^j} \label{eq:allreduce-hd-rs-sum} \end{equation}$$

等比级数求和：$\sum_{j=1}^{p} \frac{1}{2^j} = 1 - \frac{1}{2^p} = 1 - \frac{1}{N} = \frac{N-1}{N}$，因此：

$$\begin{equation} T_{\text{RS}} = \log_2 N \cdot \alpha + \frac{(N-1)M}{N\beta} \label{eq:allreduce-hd-rs-simplified} \end{equation}$$

AllGather 阶段（Recursive Doubling）：逆向过程，第 $j$ 步每节点发送 $M \cdot 2^{j-1} / N$ 字节（从 $M/N$ 开始逐步翻倍）。总带宽项之和同样为 $\frac{(N-1)M}{N\beta}$（等比级数和相同）。

合计：

$$\begin{equation} T_{\text{HD}} = 2\log_2 N \cdot \alpha + \frac{2(N-1)M}{N\beta} \label{eq:halving-doubling-allreduce} \end{equation}$$
指标Ring AllReduceHalving-Doubling下界
延迟项$2(N-1)\alpha$$2\log_2 N \cdot \alpha$$\lceil\log_2 N\rceil \alpha$
带宽项$\frac{2(N-1)M}{N\beta}$$\frac{2(N-1)M}{N\beta}$$\frac{(N-1)M}{N\beta}$
  • 延迟项是下界的 2 倍（两个阶段各占 $\log_2 N$ 步），但远优于 Ring 的 $2(N-1)$
  • 带宽项与 Ring AllReduce 相同，同为带宽最优
  • Halving-Doubling 在延迟和带宽两个维度都接近最优，是大规模集群的首选

拓扑要求：天然映射到 Hypercube（第 $j$ 步沿维度 $d-j$ 通信，每步通信对直接相连）。在 Ring 拓扑上某些步骤需要多跳路由，实际性能退化。

非 $2^k$ 节点处理：选 $r = N - 2^{\lfloor\log_2 N\rfloor}$ 个"多余"节点，先将数据发给伙伴，在 $2^{\lfloor\log_2 N\rfloor}$ 节点上执行标准 Halving-Doubling，最后回传。额外开销 $2\alpha + 2M/\beta$。

算法三：Double Binary Tree​

NCCL 中使用的算法，通过两棵互补二叉树实现 $O(\log N)$ 延迟。

核心思想​

构造两棵结构互补的二叉树 $T_1$ 和 $T_2$——$T_1$ 的叶子是 $T_2$ 的内部节点，反之亦然。消息分为两半，一半在 $T_1$ 上做 Reduce+Broadcast，另一半在 $T_2$ 上同时进行，利用全双工链路（两棵树分别使用上行和下行链路）。

代价推导​

两棵互补二叉树各处理 $M/2$ 字节数据。每棵树有 $\log_2 N$ 层。

Reduce 阶段（叶 -> 根）：每层中，子节点向父节点发送 $M/2$ 字节并规约。共 $\log_2 N$ 步，每步代价 $\alpha + \frac{M/2}{\beta}$：

$$\begin{equation} T_{\text{reduce}} = \log_2 N \cdot \left(\alpha + \frac{M/2}{\beta}\right) \label{eq:allreduce-dbt-reduce} \end{equation}$$

Broadcast 阶段（根 -> 叶）：对称操作，每步同样传输 $M/2$ 字节：

$$\begin{equation} T_{\text{broadcast}} = \log_2 N \cdot \left(\alpha + \frac{M/2}{\beta}\right) \label{eq:allreduce-dbt-broadcast} \end{equation}$$

两棵树并行操作（利用全双工链路），但 Reduce 和 Broadcast 两个阶段串行。两棵树各处理 $M/2$，每步合计传输 $M$（两棵树各 $M/2$），因此：

$$\begin{equation} T_{\text{DBT}} = 2\log_2 N \cdot \alpha + \log_2 N \cdot \frac{M}{\beta} \label{eq:dbt-allreduce} \end{equation}$$

关键观察：带宽项 $\log_2 N \cdot M/\beta$。与 Ring 的 $\frac{2(N-1)}{N} \cdot M/\beta \approx 2M/\beta$ 对比，当 $N > 4$ 时 $\log_2 N > 2$，DBT 的带宽效率劣于 Ring。原因是 Tree 算法每步传输完整数据 $M$（或 $M/2$），而非 Ring 的 $M/N$ 分块——没有利用多节点并行传输的流水线效应。

Double Binary Tree 的实际优势仅在小消息延迟场景（$O(\log N)$ 步 vs Ring 的 $O(N)$ 步）。NCCL 实际策略：Tree 处理跨节点通信（小消息，延迟优先），Ring 处理节点内通信（大消息，带宽优先）。

算法综合对比​

算法延迟项带宽项延迟接近最优？带宽最优？适用场景
Naive（Reduce + Broadcast）$2\lceil\log_2 N\rceil \alpha$$2\lceil\log_2 N\rceil M/\beta$否否不推荐
Ring AllReduce$2(N-1)\alpha$$\frac{2(N-1)M}{N\beta}$否（大 $N$ 差）是小规模大消息
Halving-Doubling$2\log_2 N \cdot \alpha$$\frac{2(N-1)M}{N\beta}$接近（2倍下界）是大规模通用
Double Binary Tree$2\log_2 N \cdot \alpha$$\log_2 N \cdot M/\beta$接近否（大 $N$ 差）小消息

消息大小与算法选择​

  • $M$ 小（延迟主导）：Halving-Doubling 或 Double Binary Tree（$O(\log N)$ 步）
  • $M$ 大（带宽主导）：Ring AllReduce 或 Halving-Doubling（带宽最优）
  • 大规模集群（$N > 64$）：Halving-Doubling（Ring 的 $O(N)$ 延迟不可接受）

参考资料​