Collective communication: algorithms, cost and the library that runs them集體通訊：演算法、成本與執行它們的函式庫

4.1The collectives, with sizes集體操作與它們的大小

Two patterns in the table matter for the rest of this chapter. First, an all-reduce is exactly a reduce-scatter followed by an all-gather, and its byte count is the sum of theirs. That is why ZeRO and FSDP, which split the two halves apart in time, move the same total bytes as classic data parallelism; they just move them at different moments and keep less memory. Second, the byte count per rank does not grow with $N$ for any collective in the table. What grows with $N$ is the number of dependent steps, which is the subject of the next section.

表中有兩個模式對本章其餘部分很重要。第一，all-reduce 正好是一個 reduce-scatter 接一個 all-gather，位元組數也是兩者之和。這就是為什麼把兩半在時間上拆開的 ZeRO 與 FSDP，搬動的總位元組數與傳統資料平行相同；它們只是在不同時刻搬、並佔用較少記憶體。第二，表中沒有任何集體操作的每 rank 位元組數會隨 $N$ 增長。隨 $N$ 增長的是相依步驟的數量，這是下一節的主題。

Panel 4.1 computes these byte counts for any $N$ and $S$.

面板 4.1 為任何 $N$ 與 $S$ 算出這些位元組數。

The mapping from parallelism to collective is fixed by the mathematics of the split. DP averages gradients: all-reduce in the classic form, reduce-scatter plus all-gather in ZeRO and FSDP. TP splits a weight matrix, so every layer must all-reduce the partial products, or all-gather inputs and reduce-scatter outputs under sequence parallelism. EP routes each token to the rank holding its expert: an all-to-all by definition. PP hands activations to the next stage: a point-to-point send. CP in Llama 3 gathers the keys and values of the whole sequence: an all-gather (Llama 3 §3.3). The sizes differ by orders of magnitude: for GPT-3 175B at TP=8, PP=8, DP=512, HPN's Table 3 lists 560 MB of TP, 5.5 GB of DP and 6 MB of PP traffic, without saying over what period (Chapter 5 reads the table).

平行化到集體操作的對應由切分的數學決定。DP 要平均梯度：傳統形式是 all-reduce，ZeRO 與 FSDP 是 reduce-scatter 加 all-gather。TP 切分權重矩陣，所以每一層都必須對部分乘積做 all-reduce，或在序列平行下對輸入做 all-gather、對輸出做 reduce-scatter。EP 把每個 token 送到持有其專家的 rank：依定義就是 all-to-all。PP 把激活值交給下一個階段：點對點傳送。Llama 3 的 CP 收集整個序列的 key 與 value：all-gather（Llama 3 §3.3）。大小相差好幾個數量級：GPT-3 175B 在 TP=8、PP=8、DP=512 下，HPN 的 Table 3 列出 TP 560 MB、DP 5.5 GB、PP 6 MB，但沒有說明是多長時間內的量（第 5 章會解讀這張表）。

4.2The ring all-reduce環形 all-reduce

The naive way to average gradients is to send everything to one server, add it up, and send the result back. That server's link becomes the bottleneck. The ring algorithm avoids this. The GPUs form a ring. Each GPU's data is cut into $N$ chunks. In the first phase (reduce-scatter), each GPU passes one chunk to its neighbor and adds the chunk it receives. After $N-1$ steps, every GPU holds the full sum of one chunk. In the second phase (all-gather), the complete chunks go around the ring again. After $N-1$ more steps, every GPU has everything.

把梯度取平均最直覺的做法，是把所有東西送到一台伺服器加總再送回去。那台伺服器的鏈路就會成為瓶頸。環形演算法避開了這個問題。GPU 排成一個環，每顆 GPU 的資料切成 $N$ 塊。第一階段（reduce-scatter），每顆 GPU 把一塊傳給鄰居，並把收到的那塊加上去。經過 $N-1$ 步，每顆 GPU 都持有某一塊的完整總和。第二階段（all-gather），完整的塊再繞環一圈。再經過 $N-1$ 步，每顆 GPU 都拿到全部。

The number of bytes that each GPU sends is

每顆 GPU 送出的位元組數是

where $S$ is the size of its data. For large $N$, this is almost exactly $2S$, and it does not grow with $N$. No algorithm can do better in bytes sent per GPU. That is what bandwidth-optimal means. The cost is latency: $2(N-1)$ sequential steps. For a ring of 1,000 GPUs, the steps add up. So NCCL uses rings for large messages and tree algorithms for small ones, and it builds hierarchical rings that stay inside a server first.

其中 $S$ 是它的資料大小。當 $N$ 很大時，這幾乎就是 $2S$，而且不隨 $N$ 增長。以每顆 GPU 送出的位元組數來看，沒有演算法能做得更好。這就是「頻寬最佳」的意思。代價是延遲：要跑 $2(N-1)$ 個連續步驟。一千顆 GPU 的環，步數會累積得很多。所以 NCCL 對大訊息用環、對小訊息用樹狀演算法，並且會先建立留在伺服器內的階層式環。

The figure shows every step for four GPUs. Each GPU $P_i$ starts with its own gradient $g_i$, cut into four segments. A colored stripe in a segment means that GPU's data has been added into it. A "sends" row shows which segment each GPU passes to its right neighbor; the "after" row below it shows the result, with a red box around each segment that was just received and added.

下圖畫出四顆 GPU 的每一步。每顆 GPU $P_i$ 一開始只有自己的梯度 $g_i$，切成四段。某一段裡出現哪個顏色的條紋，代表那顆 GPU 的資料已經加進這一段。「送出」那一列顯示每顆 GPU 把哪一段傳給右鄰；下面的「後」那一列顯示結果，剛收到並加完的段用紅框標出。

The ring, one step at a time環，一步一步來

The figure above showed the ring as a picture. Here is the index arithmetic, because it explains why every link is busy in every step, and that is the property that makes the ring bandwidth-optimal. Number the ranks $0$ to $N-1$ and cut each rank's buffer into $N$ chunks, also numbered $0$ to $N-1$. Rank $i$ always sends to rank $i+1 \pmod{N}$ and receives from rank $i-1$.

上圖把環畫成一張圖。這裡給出索引算術，因為它解釋了為什麼每一步每條鏈路都在忙，而這正是讓環達到頻寬最佳的性質。把 rank 編號 $0$ 到 $N-1$，把每個 rank 的緩衝區切成 $N$ 塊，同樣編號 $0$ 到 $N-1$。rank $i$ 永遠送給 rank $i+1 \pmod{N}$，並從 rank $i-1$ 接收。

1. Reduce-scatter, step $s$ ($s = 0, \dots, N-2$). Rank $i$ sends chunk $(i - s) \bmod N$, which it has partly summed, to its right neighbor. The neighbor adds its own copy of that chunk to what arrives. After step $s$, the chunk that rank $i$ has just received contains the contributions of $s+2$ ranks. After $N-1$ steps, rank $i$ holds the complete sum of exactly one chunk, number $(i + 1) \bmod N$, and partial sums of the others that it no longer needs.Reduce-scatter，第 $s$ 步（$s = 0, \dots, N-2$）。rank $i$ 把它已部分加總的第 $(i - s) \bmod N$ 塊送給右鄰。鄰居把自己那一塊加到收到的資料上。第 $s$ 步之後，rank $i$ 剛收到的那塊包含 $s+2$ 個 rank 的貢獻。$N-1$ 步之後，rank $i$ 持有恰好一塊的完整總和（第 $(i + 1) \bmod N$ 塊），以及其他不再需要的部分和。
2. All-gather, step $s$ ($s = 0, \dots, N-2$). Rank $i$ sends the complete chunk $(i + 1 - s) \bmod N$ to its right neighbor, which overwrites its partial sum with the finished one. After $N-1$ steps every rank has every complete chunk.All-gather，第 $s$ 步（$s = 0, \dots, N-2$）。rank $i$ 把完整的第 $(i + 1 - s) \bmod N$ 塊送給右鄰，右鄰用完成品覆寫自己的部分和。$N-1$ 步之後每個 rank 都有每一塊完整的總和。

Count the traffic: in each of the $2(N-1)$ steps, all $N$ links carry one chunk of $S/N$ bytes at the same time, and no link is idle while another works. The bytes per rank are $2(N-1) \times S/N$, as in the table. Count the latency too: a step cannot start until the previous chunk has fully arrived and been added, so the ring pays $\alpha$ a total of $2(N-1)$ times. NCCL pipelines several chunks through each ring, which hides part of each $\alpha$, but the dependent chain still grows linearly with $N$.

算一算流量：在 $2(N-1)$ 步的每一步，全部 $N$ 條鏈路同時各承載一塊 $S/N$ 位元組，沒有鏈路在別人工作時閒著。每 rank 的位元組數是 $2(N-1) \times S/N$，與表中一致。也算一算延遲：前一塊完整到達並相加之後下一步才能開始，所以環要付 $\alpha$ 共 $2(N-1)$ 次。NCCL 會讓數個 chunk 在每個環中管線化，隱藏每個 $\alpha$ 的一部分，但相依鏈仍隨 $N$ 線性增長。

The figure below writes the two index rules as a table of the chunk that each rank sends in each step.

下圖把兩條索引規則寫成一張表：每個 rank 在每一步送出哪個 chunk。

The figure below records the whole run for $N = 4$ as seven snapshots of the grid of ranks and chunks. Panel 4.2 then animates the same rules for 4, 6 or 8 ranks.

下圖把 $N = 4$ 的整個過程記成 rank 與 chunk 網格的七張快照。面板 4.2 則用同樣的規則為 4、6 或 8 個 rank 做動畫。

Animation 4.1 plays the same index rules on a physical ring of 3 to 8 ranks. Every link carries one chunk in every step, and each chunk fills as partial sums arrive.

動畫 4.1 在 3 到 8 個 rank 的實體環上播放同樣的索引規則。每一步每條鏈路都承載一塊，每塊隨著部分和抵達而逐漸填滿。

4.3The α–β cost modelα–β 成本模型

The oldest and still most useful model of message passing, the α–β model, has two parameters. $\alpha$ is the latency of one message, from the decision to send until the receiver can act on the data, independent of size. $\beta$ is the time per byte, $1/B$ for a link of bandwidth $B$. A message of $m$ bytes costs $\alpha + m/B$. A collective is a sequence of rounds in which every rank sends and receives at once, so its cost is

訊息傳遞最古老、也仍然最有用的模型——α–β 模型——有兩個參數。$\alpha$ 是一則訊息的延遲，從決定發送到接收端能使用資料，與大小無關。$\beta$ 是每個位元組的時間，對頻寬為 $B$ 的鏈路就是 $1/B$。一則 $m$ 位元組的訊息成本為 $\alpha + m/B$。集體操作是一連串每個 rank 同時發送與接收的回合，所以它的成本是

The two terms come from different physics. $\alpha$ is set by software overhead, the NIC, and the propagation and switching delay of the path: tens of microseconds across several switch hops. Meta measured a round trip of about 22 µs across its training fabric, against the under-10 µs that NCCL's defaults assume (Meta RoCE paper, §6.1). $\beta$ is set by the slowest link: 400 Gb/s is 50 GB/s, so one gigabyte costs 20 ms. Everything in collective design is a trade between these two terms.

兩項來自不同的物理。$\alpha$ 由軟體開銷、NIC，以及路徑的傳播與交換延遲決定：跨數個交換器跳數時是數十微秒。Meta 量到跨訓練網路的往返約 22 µs，而 NCCL 的預設假設是低於 10 µs（Meta RoCE 論文，§6.1）。$\beta$ 由最慢的鏈路決定：400 Gb/s 是 50 GB/s，所以一 GB 要 20 ms。集體通訊設計中的一切都是這兩項之間的取捨。

The figure below takes the formula apart for the two algorithms that the next subsections derive, a ring and a tree on 4 ranks. The ring pays $\alpha$ six times and sends a small piece each time; the tree pays $\alpha$ twice and sends the whole buffer each time.

下圖把這條公式拆開，用的是接下來兩小節要推導的兩種演算法：4 個 rank 上的環與樹。環付六次 $\alpha$、每次送一小片；樹只付兩次 $\alpha$，但每次都送整個緩衝區。

Ring: bandwidth-optimal, latency-poor環：頻寬最佳，延遲不佳

In the ring all-reduce every rank sends $S/N$ bytes in each of $2(N-1)$ steps. Its cost is therefore

在環形 all-reduce 中，每個 rank 在 $2(N-1)$ 步的每一步送出 $S/N$ 位元組。所以成本是

The second term is as small as it can be: each rank must receive the other $N-1$ contributions to the slice it will own, $\tfrac{N-1}{N}\,S$ bytes, and then the $N-1$ finished slices it does not own, another $\tfrac{N-1}{N}\,S$. No algorithm can deliver an all-reduce with fewer bytes into the busiest rank. The first term is the price. With 1,024 ranks and $\alpha = 22\,\mu\text{s}$ the ring spends $2{,}046 \times 22\,\mu\text{s} = 45\,\text{ms}$ in pure latency; for a 1 GB buffer the bandwidth term at 50 GB/s is 40 ms, so the ring is already more latency than data.

第二項已經小到不能再小：每個 rank 必須收到其他 $N-1$ 個對它將持有那一片的貢獻，即 $\tfrac{N-1}{N}\,S$ 位元組，然後再收到它不持有的 $N-1$ 片完成品，又是 $\tfrac{N-1}{N}\,S$。沒有演算法能用更少進入最忙 rank 的位元組完成 all-reduce。第一項是代價。1,024 個 rank、$\alpha = 22\,\mu\text{s}$ 時，環花 $2{,}046 \times 22\,\mu\text{s} = 45\,\text{ms}$ 的純延遲；對 1 GB 的緩衝區，50 GB/s 下的頻寬項是 40 ms，所以環的延遲已經多於資料。

Trees: latency-optimal, bandwidth-poor樹：延遲最佳，頻寬不佳

The opposite design is recursive doubling. In step $k$ each rank exchanges its whole buffer with the rank whose index differs in bit $k$, and adds. After $\log_2 N$ steps every rank holds the full sum. The cost is

相反的設計是遞迴倍增。在第 $k$ 步，每個 rank 與索引第 $k$ 位元不同的 rank 交換整個緩衝區並相加。$\log_2 N$ 步之後每個 rank 都持有完整的總和。成本是

For 1,024 ranks that is 10 steps instead of 2,046, but each rank now sends $S$ bytes ten times, five times more than the ring. Rabenseifner's algorithm (recursive halving for the reduce-scatter, doubling for the all-gather) gets the best of both in the model, $2(\log_2 N)\,\alpha + \tfrac{2(N-1)}{N} \cdot S/B$, but needs a power-of-two $N$ and a fabric where every pair can talk at full rate at once. NCCL's own "tree" is a pipelined double binary tree that, in NVIDIA's description, keeps the byte count near the ring's while cutting the dependent steps to a logarithm. Treat the two formulas above as the ends of a spectrum and real implementations as points between them.

對 1,024 個 rank，那是 10 步而非 2,046 步，但現在每個 rank 要送 $S$ 位元組十次，是環的五倍。Rabenseifner 演算法（reduce-scatter 用遞迴減半，all-gather 用倍增）在模型中兼得兩者之長：$2(\log_2 N)\,\alpha + \tfrac{2(N-1)}{N} \cdot S/B$，但要求 $N$ 是 2 的冪，且網路要讓每一對都能同時以全速通訊。NCCL 自己的「tree」是管線化的雙二元樹，依 NVIDIA 的描述，它把位元組數維持在接近環的水準，同時把相依步驟減到對數級。把上面兩條公式當成一條光譜的兩端，真實實作則是中間的點。

The butterfly below shows both tree schemes on 8 ranks. The exchange pattern is the same in both: in step $k$ each rank pairs with the rank whose index differs in one bit. Recursive doubling sends the whole buffer in every step; recursive halving sends half of what is left.

下方的蝶形圖在 8 個 rank 上畫出這兩種樹狀方案。兩者的交換模式相同：第 $k$ 步每個 rank 與索引差一個位元的 rank 配對。遞迴倍增每一步都送整個緩衝區；遞迴減半只送剩下的一半。

Animation 4.2 plays both schemes on 4 or 8 ranks. In recursive halving the partner distance doubles while the message halves; the all-gather then runs the same pairs in reverse order.

動畫 4.2 在 4 或 8 個 rank 上播放這兩種方案。遞迴減半時夥伴距離加倍、訊息減半；接著 all-gather 以相反順序走同樣的配對。

NCCL's double binary tree is built so that two trees can work at the same time (figure below). Each tree is an ordinary binary tree over the nodes, but no node is an inner node in both trees, so no node has to forward data in both. Inside a node the GPUs form a chain, and the tree branches only between nodes (Demystifying NCCL, HOTI 2025).

NCCL 的雙二元樹是為了讓兩棵樹能同時運作而建的（見下圖）。每棵樹都是節點上一棵普通的二元樹，但沒有節點同時是兩棵樹的內部節點，所以沒有節點必須在兩棵樹裡都轉送資料。在一個節點內，GPU 串成一條鏈，樹只在節點之間分支（Demystifying NCCL，HOTI 2025）。

The crossover交叉點

Set the ring and doubling costs equal and solve for $S$. The message size at which they tie is

令環與倍增的成本相等並解出 $S$。兩者打平的訊息大小是

Below $S^*$ the tree wins; above it the ring wins. The product $\alpha B$, the bytes a link carries during one latency, appears in every formula in this chapter. For $N = 128$, $\alpha = 22\,\mu\text{s}$ and $B = 50\GBs$, $S^*$ is about $49 \times 1.1\,\text{MB} \approx 54\,\text{MB}$. Double the latency and the crossover doubles, so a library tuned for a 5 µs fabric chooses the wrong algorithm on a 22 µs one: its table is off by four times.

$S^*$ 以下樹勝出；以上環勝出。乘積 $\alpha B$——鏈路在一個延遲期間能承載的位元組數——出現在本章的每一條公式中。$N = 128$、$\alpha = 22\,\mu\text{s}$、$B = 50\GBs$ 時，$S^*$ 約為 $49 \times 1.1\,\text{MB} \approx 54\,\text{MB}$。延遲加倍，交叉點就加倍，所以為 5 µs 網路調校的函式庫在 22 µs 的網路上會選錯演算法：它的表差了四倍。

The figure below plots both formulas for these values. For small messages each curve is flat at its latency term, $254\,\alpha$ for the ring and $7\,\alpha$ for the tree. For large messages each curve rises with its byte term, and the ring's curve is lower because the ring sends fewer bytes.

下圖畫出這組數值下的兩條公式。小訊息時每條曲線平在它的延遲項：環是 $254\,\alpha$，樹是 $7\,\alpha$。大訊息時每條曲線隨它的位元組項上升，而環的曲線較低，因為環送的位元組較少。

Two worked examples兩個算例

A data-parallel gradient exchange. Llama 3 405B has 405 billion parameters; in bf16 the gradients are 810 GB. As a first estimate, let 128 data-parallel ranks each hold a full copy and all-reduce it over 400 Gb/s (50 GB/s) links with $\alpha = 22\,\mu\text{s}$. In the real run (Llama 3 Table 4, row 2) the model is also split by TP = 8 and PP = 16, so each DP rank owns only a shard, and FSDP's reduce-scatter plus all-gather moves that shard. Both are compared with one step of compute at 400 TFLOP/s per GPU on 16,384 GPUs with a 16M-token batch. The arithmetic, one question per row:

一次資料平行的梯度交換。Llama 3 405B 有 4,050 億個參數；bf16 的梯度是 810 GB。先做第一個估計：讓 128 個資料平行 rank 各持有一份完整副本，在 400 Gb/s（50 GB/s）鏈路上以 $\alpha = 22\,\mu\text{s}$ 做 all-reduce。在真實運行中（Llama 3 Table 4 第二行）模型還被 TP = 8 與 PP = 16 切分，所以每個 DP rank 只持有一個分片，由 FSDP 的 reduce-scatter 加 all-gather 搬動。兩者都與一步的計算量比較：16,384 顆 GPU、每顆 400 TFLOP/s、16M token 批次。逐列計算如下：

The full-copy all-reduce would spend about 32 s per step on bandwidth, and its 5.6 ms latency term is nothing beside that. With the real layout the exchange is about 0.25 s, 4% of a 5.9 s step if nothing hides it; most of it is hidden (Section 4.7).

完整副本的 all-reduce 每步要花約 32 s 在頻寬上，它 5.6 ms 的延遲項相比之下微不足道。換成真實的配置，交換約 0.25 s；若沒有任何隱藏，占 5.9 s 一步的 4%；大部分都被隱藏了（第 4.7 節）。

A small tensor-parallel all-reduce. Take a 1 MB all-reduce among the 8 GPUs of one server, joined by NVSwitch at about 450 GB/s per GPU, and assume $\alpha = 5\,\mu\text{s}$ inside the server (the exact value depends on the protocol). The ring takes 14 dependent steps and the doubling tree 3. The arithmetic, one question per row:

一次小的張量平行 all-reduce。取一台伺服器內 8 顆 GPU 之間 1 MB 的 all-reduce，GPU 由 NVSwitch 連接、每顆約 450 GB/s，並假設伺服器內 $\alpha = 5\,\mu\text{s}$（精確值取決於協定）。環要走 14 個相依步驟，倍增樹 3 個。逐列計算如下：

The tree is more than three times faster, and 95% of the ring's time is latency. Small collectives are latency problems, and the link speed is almost irrelevant to them. That is the whole reason NCCL has more than one algorithm and protocol.

樹快了三倍多，而環的時間有 95% 是延遲。小的集體操作是延遲問題，鏈路速度對它們幾乎無關。這就是 NCCL 擁有多種演算法與協定的全部理由。

4.4Hierarchical collectives and in-network reduction階層式集體操作與網內歸約

A training server is two networks in one. Inside it, 8 GPUs share an NVSwitch fabric at about 3.6 Tb/s per GPU. Outside it, each GPU has a 400 Gb/s NIC. The gap is about 9× (Rail-only paper, §II). A flat ring across 1,024 GPUs ignores this: 7 of every 8 links in the ring would be NVLink and 1 of every 8 would be a NIC, and the ring runs at the pace of the slowest link, so the NVLink bandwidth is wasted.

一台訓練伺服器是兩個網路合在一起。在內部，8 顆 GPU 共用每顆約 3.6 Tb/s 的 NVSwitch 網路。在外部，每顆 GPU 有一張 400 Gb/s 的 NIC。差距約 9 倍（Rail-only 論文，§II）。跨 1,024 顆 GPU 的平面環忽略了這點：環中每 8 條鏈路有 7 條是 NVLink、1 條是 NIC，而環以最慢鏈路的速度前進，所以 NVLink 的頻寬被浪費。

The hierarchical all-reduce does the operation in three phases. First, a reduce-scatter inside each server over NVSwitch: 7 steps, $\tfrac{7}{8}\,S$ bytes per GPU, at NVLink speed. Each GPU now owns one eighth of the server's partial sum. Second, an all-reduce across servers, but only among the GPUs that own the same eighth: GPU $k$ of every server forms a group of $N/8$ ranks and all-reduces $S/8$ bytes over the network. Third, an all-gather inside each server, again 7 steps at NVLink speed. The network now carries $2 \times \tfrac{N/8 - 1}{N/8} \times S/8 \approx S/4$ bytes per GPU instead of $2S$: eight times less. The rail-only paper's analysis found this for 16 DGX GH200 systems, where the high-bandwidth domain holds 256 GPUs: 98% of the all-reduce bytes crossed NVSwitch and 2% crossed the network.

階層式 all-reduce分三個階段做這件事。第一，在每台伺服器內透過 NVSwitch 做 reduce-scatter：7 步、每顆 GPU $\tfrac{7}{8}\,S$ 位元組、NVLink 速度。現在每顆 GPU 持有該伺服器部分和的八分之一。第二，跨伺服器做 all-reduce，但只在持有同一個八分之一的 GPU 之間：每台伺服器的 GPU $k$ 組成 $N/8$ 個 rank 的群組，在網路上對 $S/8$ 位元組做 all-reduce。第三，在每台伺服器內做 all-gather，同樣 7 步、NVLink 速度。網路現在每顆 GPU 承載 $2 \times \tfrac{N/8 - 1}{N/8} \times S/8 \approx S/4$ 位元組而非 $2S$：少了八倍。Rail-only 論文分析 16 台 DGX GH200 系統時發現這一點，那裡的高頻寬 domain 容納 256 顆 GPU：all-reduce 有 98% 的位元組跨 NVSwitch、2% 跨網路。

The figure below draws the three phases on two servers. Follow the slice that each GPU owns: only slice $k$ of GPU $k$ leaves the server, and it travels only to GPU $k$ of the other server.

下圖在兩台伺服器上畫出這三個階段。追蹤每顆 GPU 持有的那一片：只有 GPU $k$ 的第 $k$ 片會離開伺服器，而且只送到另一台伺服器的 GPU $k$。