all-reduce 每张卡要发多少数据？
ring 和 tree 有什么区别？

英文问法How much data does each GPU send in a ring all-reduce? · Ring vs tree all-reduce: when is each better? · Implement ring all-reduce.

考过面经：国内：阿里淘天（"有4块卡，数据被切成了4份…设一次通信量是x，如果要实现一次All Reduce操作，需要多少通信量？"）、阿里（"NCCL中Ring AllReduce、Tree AllReduce的工作原理"）；其他公司：Anthropic Perf/Infra 技术电面（10 个 node、1000 个元素求 distributed mode 和 median，讨论用哪种 collective、tree 还是 ring，1p3a 1188498）

先弄清楚：每个概念是什么

All-reduce: 每张卡各有一份 gradient，加起来后每张卡都拿到总和。例：2 卡 (1, 2)、(3, 4) → 两卡都得到 (4, 6)。
Reduce-scatter 与 all-gather: reduce-scatter 求和后每张卡只留自己负责的 1/n 段，all-gather 再把各段拼回完整向量。两步连起来就是 all-reduce。
Ring: 卡围成一圈，每一步每张卡只给右邻居发 1/n 的数据。所有链路同时在用，所以 bandwidth 最优，代价是要走 \(2(n-1)\) 步。
Tree（NCCL double binary tree）: 沿二叉树往上 reduce、再往下 broadcast，只要约 \(2\log_2 n\) 步。两棵互补的树各管一半数据，带宽也能打满。
α–β 模型: 发一条消息的时间 = \(\alpha\)（固定启动 latency）+ 字节数 / \(B\)。消息小时步数（\(\alpha\)）说了算，消息大时 bandwidth 说了算。

看图：4 卡 ring 的每一步，ring 和 tree 的形状

图 1：4 张卡，每卡的数据切成 4 块，Σ = a + b + c + d。左列 reduce-scatter 的橙色格是收到后相加的块，右列 all-gather 的蓝色格是被 Σ 覆盖的块，虚线格之后会被覆盖。右下角是阿里题的 1.5x。

图 2：同样 8 张卡。ring 的步数随 n 线性增长，tree 的步数只和树高 log₂ n 有关。每步都要付一次启动延迟 α，所以卡多、message 小时 tree 快。

30 秒回答

All-reduce sums a tensor across n GPUs and leaves the result on every GPU. Ring all-reduce is a reduce-scatter followed by an all-gather, each n − 1 steps in which every GPU sends one 1/n chunk to its neighbor. So each GPU sends 2(n − 1)/n · S bytes, nearly independent of n, which is bandwidth-optimal. The catch is latency: 2(n − 1) sequential steps. A tree takes about 2 log n steps, and NCCL's double binary tree also keeps full bandwidth. NCCL picks automatically: tree for small messages at large scale, ring for large messages.

推导 / 关键公式

Ring：reduce-scatter 和 all-gather 各 \(n-1\) 步，每步发 \(S/n\)：

\[ \text{每卡发送} = 2(n-1)\cdot\frac{S}{n} \] \[ T_{\text{ring}} = 2(n-1)\,\alpha + \frac{2(n-1)}{n}\cdot\frac{S}{B} \]

下界：每个元素要 \(n-1\) 次加法、\(n\) 次赋值，至少 \(2(n-1)\) 次传输，摊到 \(n\) 条链路上，ring 正好达到。

	ring	tree（double binary）
latency 项	\(2(n-1)\,\alpha\)	\(\approx 2\log_2 n\cdot\alpha\)
每卡发送	\(2(n-1)S/n\)	\(\approx 2S\)，同样最优
适合	大 message	小、中 message，卡很多

手算例子

阿里题，4 卡、每卡 \(x\)：每卡发 \(2\cdot\tfrac34 x = 1.5x\)，全部卡合计 \(6x\)。若全发给 rank 0 再广播，rank 0 要收 \(3x\)、再发 \(3x\)，瓶颈全在它。
1B 参数、bf16 gradient \(S = 2\) GB，8 卡跨机 ring，每卡 NIC 400 Gb/s = 50 GB/s：每卡发 3.5 GB，至少 70 ms。
1024 卡、1 MB message、设 \(\alpha = 5\,\mu s\)：ring 的 latency 项 ≈ 10.2 ms，带宽项只有 40 µs；tree ≈ 0.1 ms → 小 message 用 tree。

手撕代码（NumPy 模拟 ring all-reduce）

def ring_allreduce(xs):
    # xs[r] = rank r 的向量；返回每个 rank 的结果
    n = len(xs)
    buf = [np.array_split(x.astype(float), n) for x in xs]
    # reduce-scatter：第 s 步 rank r 把 chunk (r-s)%n 发给 r+1
    for s in range(n - 1):
        msg = [buf[r][(r - s) % n].copy() for r in range(n)]
        for r in range(n):
            buf[(r + 1) % n][(r - s) % n] += msg[r]
    # 此时 rank r 的 chunk (r+1)%n 已是全体之和
    # all-gather：把求和好的 chunk 沿 ring 再转一圈
    for s in range(n - 1):
        msg = [buf[r][(r + 1 - s) % n].copy() for r in range(n)]
        for r in range(n):
            buf[(r + 1) % n][(r + 1 - s) % n] = msg[r]
    return [np.concatenate(b) for b in buf]

msg 先拷贝，模拟所有卡同时收发。

必答点

all-reduce = reduce-scatter + all-gather，各 \(n-1\) 步
每卡发 \(2(n-1)/n\cdot S\)，几乎与 \(n\) 无关 → bandwidth 最优
ring latency \(\propto n\)；tree \(\propto \log n\)，NCCL double binary tree 带宽也满
NCCL 按 message size、topology 自动选；NCCL_ALGO 可强制
reduce-scatter、all-gather 单独做：每卡 \((n-1)/n\cdot S\)

追问

busbw 和 algbw 是什么？

nccl-tests 里 algbw = \(S/t\)；all-reduce 的 busbw = algbw × \(2(n-1)/n\)，与卡数无关，可直接和 NVLink、NIC 的峰值比。all-to-all 的系数是 \((n-1)/n\)，见 MoE 页。

怎么知道 NCCL 选了哪个算法？

NCCL_DEBUG=INFO NCCL_DEBUG_SUBSYS=TUNING 会打印选中的 algorithm 和 protocol。NCCL_ALGO=Ring 或 Tree 强制一种，再用 nccl-tests 的 all_reduce_perf 对比 busbw。

跨机时 ring 有什么问题？

一圈的速度取决于最慢的那条边，机间 NIC 远慢于机内 NVLink，NCCL 会改用 tree。有 NVSwitch 的机器还能用 NVLS（NVLink SHARP），把 reduction 交给 switch 做。

Anthropic 题：10 个 node 求 distributed mode 和 median？

别搬原始数据。mode：各 node 本地计数，再 reduce 合并 counts。median：在 value range 上 binary search，每轮只 all-reduce 一个"≤ x 的个数"，消息极小、latency-bound，适合 tree。

来源NCCL User Guide Collective Operations（AllGather 节：ReduceScatter + AllGather = AllReduce）、Environment Variables（NCCL_ALGO）、Logging（Debugging Performance Issues）· nccl-tests PERFORMANCE.md（algbw、busbw、下界）· Jeaugey 2019, NCCL 2.4（double binary tree）· Thakur et al. 2005 §3（p.2）、§4.1（p.3）、§5.3（p.11）· DGX H100 User Guide Table 1（ConnectX-7 400 Gb/s）

all-reduce 每张卡要发多少数据？ring 和 tree 有什么区别？