Collective communication and the alpha-beta cost model

Before this lesson: lesson 1 (what a GPU is and what HBM is); the block view of a matrix (linear algebra 1), because an all-to-all is a block transpose; the logarithm $\lg p = \log_2 p$. Time: about 65 minutes, plus the notebook.

---

Why this matters #

Every distributed training step ends in collectives. Data parallelism (DDP) all-reduces the gradients after the backward pass. FSDP and ZeRO all-gather the weights and reduce-scatter the gradients (lesson 8). Tensor parallelism all-reduces activations in every layer (lesson 9). Mixture-of-experts layers and DeepSpeed-Ulysses use all-to-all (lesson 10).

The α-β model in this lesson answers three practical questions with a few lines of arithmetic: how long will this collective take, which algorithm should a library pick for this message size, and is my measured all-reduce slow because of the network or because of a configuration problem? Every later lesson on parallelism uses its results.

1. Predict first #

2. The picture #

Words first. The GPUs (or processes) that take part in a collective are called ranks, numbered $0, \dots, p - 1$. A message is one transfer of data from one rank to another. A collective is a communication operation that all $p$ ranks call together. The vector each rank holds has $n$ bytes.

The six standard collectives, on 4 GPUs. GPU 0 holds data $A$, GPU 1 holds $B$, GPU 2 holds $C$ and GPU 3 holds $D$; each is cut into 4 chunks (the subscript).

Interactive figure: loading…

The simplest case, $p = 2$. Two GPUs hold vectors $x_0$ and $x_1$ of $n$ bytes. They want $x_0 + x_1$ on both.

• One step: each GPU sends its whole vector to the other and adds. Each GPU sends $n$ bytes.
• Two steps: GPU 0 sends the second half of $x_0$, and GPU 1 sends the first half of $x_1$. Each adds what it receives, so now GPU 0 owns the first half of the sum and GPU 1 the second half. This is a reduce-scatter. Then each GPU sends its finished half to the other. This is an all-gather. Each GPU again sends $n/2 + n/2 = n$ bytes, but in two messages.

For two GPUs the one-step method is better (one message instead of two). For many GPUs the two-phase idea wins, because it keeps every link busy with small pieces.

The ring, $p$ ranks. Put the ranks on a ring: rank $r$ sends only to rank $r + 1$ (mod $p$) and receives only from rank $r - 1$. Cut each vector into $p$ chunks of $n/p$ bytes. In every step, every rank sends one chunk to its right neighbour, so all $p$ links work at the same time.

• Reduce-scatter phase, steps $k = 1, \dots, p - 1$: rank $r$ sends its partial sum of chunk $(r - k) \bmod p$; the receiver adds it to its own copy. Each chunk travels around the ring and picks up one more contribution at each hop. After $p - 1$ hops it contains all $p$ inputs.
• All-gather phase, steps $k = 1, \dots, p - 1$: each rank forwards the finished chunk it received last. Nothing is added; the chunks are only copied.

Here is the reduce-scatter schedule for $p = 4$. The entry is the chunk that the rank sends to its right neighbour in that step:

	GPU 0 → 1	GPU 1 → 2	GPU 2 → 3	GPU 3 → 0
step 1	chunk 3	chunk 0	chunk 1	chunk 2
step 2	chunk 2	chunk 3	chunk 0	chunk 1
step 3	chunk 1	chunk 2	chunk 3	chunk 0

Follow chunk 0: GPU 1 sends it (step 1, 2 inputs: $B_0 + C_0$ arrive at GPU 2), GPU 2 forwards it (step 2, 3 inputs), GPU 3 forwards it (step 3, all 4 inputs arrive at GPU 0). So after the reduce-scatter, GPU $r$ owns the full sum of chunk $r$.

Interactive figure: loading…

Why the bytes do not grow with $p$. Each GPU sends $2(p-1)$ chunks of $n/p$ bytes: in total $\frac{2(p-1)}{p}n$. For $p = 2$ this is $n$, for $p = 8$ it is $1.75n$, and for $p = 1000$ it is $1.998n$. More GPUs give more steps, but smaller chunks.

3. Definitions and main results #

The α-β model #

Definition (α-β model; Hockney's model, used by Thakur, Rabenseifner and Gropp 2005). Sending a message of $m$ bytes from one rank to another takes

$\alpha$ is the latency per message, in seconds: the start-up cost of a transfer, paid even for one byte. $\beta$ is the time per byte, in seconds per byte: one over the link bandwidth. For a link of 50 GB/s, $\beta = 1/(50 \times 10^9) = 2 \times 10^{-11}$ s/byte.

Assumptions. Keep them in mind; section 3 ends with what happens when they fail.

1. Single port, full duplex: a rank sends at most one message and receives at most one message at the same time. Sending and receiving can overlap.
2. Flat network: every pair of ranks has the same $\alpha$ and $\beta$, and different pairs do not slow each other down.
3. No compute cost: the local additions of a reduction are free.

Notation: $p$ ranks, $n$ bytes per rank, $\lg p = \log_2 p$. The cost of an algorithm is the time until the last rank is done. When all ranks send in parallel in a step, the step costs one message time.

The six collectives #

Collective	Before (each rank)	After
broadcast	the root has $x$	every rank has $x$
reduce	rank $r$ has $x_r$	the root has $\sum_r x_r$
all-reduce	rank $r$ has $x_r$	every rank has $\sum_r x_r$
reduce-scatter	rank $r$ has $x_r$	rank $r$ has chunk $r$ of $\sum_r x_r$ ($n/p$ bytes)
all-gather	rank $r$ has a shard $s_r$ ($n/p$ bytes)	every rank has $(s_0, \dots, s_{p-1})$
all-to-all	rank $r$ has blocks $b_{r,0}, \dots, b_{r,p-1}$	rank $j$ has $b_{0,j}, \dots, b_{p-1,j}$

The sum is elementwise. Libraries also offer max, min and product, with the same costs.

All-to-all is a transpose. Put the blocks in a $p \times p$ block matrix: row $r$ is what rank $r$ holds, so block $(r, j)$ is $b_{r,j}$. After the all-to-all, rank $j$ holds column $j$. So the all-to-all replaces the block matrix by its block transpose (linear algebra 1). Unlike a reduction, every block is different and goes to one place, so nothing can be added up on the way.

All-reduce = reduce-scatter + all-gather. After a reduce-scatter, rank $r$ holds chunk $r$ of the sum. An all-gather of these chunks gives every rank every chunk of the sum, which is the all-reduce result. This identity is how the ring works, and it is how ZeRO and FSDP place the optimizer step between the two halves (lesson 8).

Ring all-reduce #

Theorem (ring all-reduce cost). On a ring of $p$ ranks, all-reduce of $n$ bytes takes

and each rank sends $\frac{2(p-1)}{p}n$ bytes.

Proof.

1. Split each vector into $p$ chunks of $n/p$ bytes.
2. Reduce-scatter. In step $k = 1, \dots, p-1$, rank $r$ sends its partial sum of chunk $(r - k) \bmod p$ to rank $r + 1$, which adds it. Each rank sends one message and receives one, so the step costs $\alpha + (n/p)\beta$.
3. Follow chunk $c$. In step 1 it leaves rank $c + 1$ (because $(c + 1) - 1 = c$) with that rank's input. In step $k$ it leaves rank $c + k$, which received it in step $k - 1$ and added its own input. So after step $k$ the chunk contains $k + 1$ inputs. After step $p - 1$ it arrives at rank $c + p \equiv c$ with all $p$ inputs. So rank $r$ owns the full sum of chunk $r$.
4. All-gather. In step $k = 1, \dots, p - 1$, rank $r$ sends chunk $(r - k + 1) \bmod p$: in step 1 its own finished chunk, later the chunk it received in the step before. After $p - 1$ steps every finished chunk has visited every rank. Each step again costs $\alpha + (n/p)\beta$.
5. Total: $2(p-1)$ steps of $\alpha + (n/p)\beta$, which is the formula. Each rank sends $2(p-1)$ chunks of $n/p$ bytes. $\blacksquare$

The two phases alone: a ring reduce-scatter or a ring all-gather costs $(p-1)\alpha + \frac{p-1}{p}n\beta$, and each rank sends $\frac{p-1}{p}n$ bytes.

The cost has two parts. The latency term $2(p-1)\alpha$ grows linearly with $p$. The bandwidth term $\frac{2(p-1)}{p}n\beta$ is almost $2n\beta$ for any $p$.

Recursive doubling #

Algorithm (recursive doubling, $p$ a power of two). In step $k = 0, 1, \dots, \lg p - 1$, rank $r$ exchanges its whole current vector with rank $r \oplus 2^k$ ($\oplus$ = bitwise XOR, which flips bit $k$ of $r$), and both add.

Claim. After step $k$, rank $r$ holds the sum over the $2^{k+1}$ ranks that agree with $r$ in all bits above bit $k$. Proof by induction. Before step 0, rank $r$ holds its own input. In step $k$, $r$ and its partner $r \oplus 2^k$ agree in all bits above bit $k$ and differ only in bit $k$. Each holds the sum over its own group of $2^k$ ranks (bits above bit $k - 1$ equal), and these two groups are disjoint. Their union is the group of $2^{k+1}$ ranks of the claim. After $\lg p$ steps the group is all $p$ ranks. $\blacksquare$

Each step sends the whole vector, so

Few steps (a small latency term), but every byte is sent $\lg p$ times (a large bandwidth term). Rabenseifner's algorithm combines both strengths: a reduce-scatter by recursive halving, then an all-gather by recursive doubling, with cost $2\lg p\,\alpha + \frac{2(p-1)}{p}n\beta$ (Thakur et al. 2005, §4.5). MPI libraries use it for long messages when $p$ is a power of two.

The crossover message size #

Set $T_{\text{ring}} = T_{\text{rd}}$ and solve for $n$:

Below $n^*$ recursive doubling is faster: the latency regime. Above $n^*$ the ring is faster: the bandwidth regime. For $p = 4$: $n^* = (6 - 2)\alpha / ((2 - 1.5)\beta) = 8\alpha/\beta$. For $p = 2$ both bandwidth terms are $n\beta$, so recursive doubling (1 step) always wins.

Interactive figure: loading…

Why the ring's bandwidth term is optimal #

Theorem (lower bound; Patarasuk and Yuan 2009). Assume that messages carry values or partial sums of elements, and that nothing is compressed. Then in any all-reduce algorithm the busiest rank sends at least $\frac{2(p-1)}{p}n$ bytes. With one port per rank this takes at least $\frac{2(p-1)}{p}n\beta$.

Proof (sketch, one element at a time).

1. Fix one element. Order all messages that carry it in time (break ties in any order).
2. Let $X$ be the first rank that holds the full sum of this element, right after message $m^*$.
3. Every other rank $j$ must have sent at least one message with this element at or before $m^*$: its input must reach $X$, and only $j$ can send it first. That is $p - 1$ messages.
4. Right after $m^*$, no rank other than $X$ holds the full sum ($m^*$ has one receiver). So each of the other $p - 1$ ranks must receive at least one message after $m^*$: $p - 1$ more.
5. Every element needs at least $2(p-1)$ messages. Summed over all elements, the ranks send at least $2(p-1)n$ bytes together, so the busiest rank sends at least $\frac{2(p-1)}{p}n$. $\blacksquare$

The ring reaches this bound. For all-gather the bound is simpler: each rank must receive the $\frac{p-1}{p}n$ bytes it does not have, and with one port this takes $\frac{p-1}{p}n\beta$.

All-to-all #

Proposition (all-to-all cost). In an all-to-all, rank $r$ holds $p$ blocks of $n/p$ bytes ($n$ bytes in total) and must send $p - 1$ of them, $\frac{p-1}{p}n$ bytes, to the other ranks. The pairwise exchange algorithm uses $p - 1$ steps; in step $k$ rank $r$ sends block $b_{r,\,r \oplus k}$ to rank $r \oplus k$ (for $p$ a power of two; other orders work for any $p$). Its cost is

and the bandwidth term is optimal, because every rank must send $\frac{p-1}{p}n$ bytes of its own data. Bruck's algorithm needs only $\lg p$ steps but sends about $n/2$ bytes in each: $\lg p\,(\alpha + \tfrac{n}{2}\beta)$ for $p$ a power of two (Thakur et al. 2005, §4.3). It is used for small blocks.

All-to-all is harder to scale than all-reduce. In a ring, each rank talks only to its neighbours. In an all-to-all, every pair exchanges different data, so on a real network the traffic must cross the middle of the network: its bisection bandwidth (the bandwidth across a cut that splits the ranks into two halves) sets the speed. And when the blocks have unequal sizes (uneven expert loads in mixture-of-experts), the largest one sets the time.

Algorithm bandwidth and bus bandwidth #

nccl-tests (NVIDIA's benchmark programs such as all_reduce_perf) reports the time $t$ and two bandwidths:

• Algorithm bandwidth $\text{algbw} = S/t$, where $S$ is the buffer size in bytes. For all-gather and reduce-scatter, $S$ is the full (gathered) size.
• Bus bandwidth $\text{busbw} = \text{algbw} \times f$, with the factor

collective	$f$
all-reduce	$2(p-1)/p$
reduce-scatter, all-gather, all-to-all	$(p-1)/p$
broadcast, reduce	$1$

Why this factor. For an algorithm that reaches the lower bound, $t \approx f \cdot S\beta$, so $\text{busbw} = f S/t \approx 1/\beta$: the speed of the slowest link, for any $p$. So busbw can be compared with the link's hardware bandwidth and across different numbers of GPUs. algbw cannot: for all-reduce it is about half the link speed. The factor assumes a flat network; on several nodes, busbw can be higher than one network card's bandwidth (worked example (d)).

Reading one line. An all_reduce_perf line (made-up numbers, in the tool's format) on 8 GPUs:

#       size         count    type   redop    time   algbw   busbw
  1073741824     268435456   float     sum    4500  238.61  417.57

The size is $S = 2^{30}$ bytes (1 GiB, 268,435,456 floats of 4 bytes), the time is in microseconds, and the bandwidths are in GB/s ($10^9$ bytes/s). Check: $S/t = 1{,}073{,}741{,}824 / 0.0045\text{ s} = 238.6$ GB/s, and $238.6 \times 2 \cdot 7/8 = 417.6$ GB/s. Compared with the 450 GB/s NVLink of an H100 node, the all-reduce reaches 93% of the link speed.

Topology: fast links inside a node, slower links between nodes #

Real clusters are not flat. Two numbers for an 8-GPU H100 SXM server (2022):

• Inside a node, GPUs talk over NVLink through NVSwitch: 450 GB/s per direction per GPU.
• Between nodes, each GPU usually has its own network card: InfiniBand NDR, 400 Gb/s $= 50$ GB/s per direction. The network is 9× slower than NVLink and has a higher latency.

(An A100 server: 300 GB/s NVLink and 25 GB/s per GPU on 200 Gb/s InfiniBand.)

• Flat ring. All ranks move in lockstep, so each step waits for the slowest link. A single ring that visits all GPUs of all nodes crosses the network at each node boundary and runs at network speed for every step.

• Hierarchical all-reduce, $g$ GPUs per node and $N$ nodes:

  1. reduce-scatter inside each node over NVLink: each GPU now holds $1/g$ of its node's sum;
  2. all-reduce across nodes: GPU $k$ of every node joins a ring with GPU $k$ of the other nodes, on its $n/g$ bytes. The $g$ rings run in parallel, each on its own network card;
  3. all-gather inside each node over NVLink.

  Each network card carries $\frac{2(N-1)}{N}\cdot\frac{n}{g}$ bytes, and only $2(N-1)$ steps pay the network latency.

• Lower bound across nodes. Treat each node as one super-rank (messages inside a node are free). The argument above shows that some node must send at least $\frac{2(N-1)}{N}n$ bytes over its $g$ network cards. The hierarchical scheme reaches this.

Interactive figure: loading…

NCCL (the NVIDIA Collective Communications Library) detects the topology, builds rings and trees over NVLink and the network, uses several rings in parallel (one per network card), and picks the algorithm and protocol for each call from its own cost model of size, rank count and topology. The environment variable NCCL_DEBUG=INFO logs what it built. Before a long run on a new cluster, measure it with nccl-tests and compare busbw with the link speeds.

Trees in NCCL

For very many ranks, the ring's latency term $2(p-1)\alpha$ becomes large even for medium messages. NCCL 2.4 added double binary trees (NVIDIA developer blog, 2019). In a binary tree, at most half of the ranks are inner nodes; the others are leaves. So a second tree can be built in which the leaves of the first tree are the inner nodes: no rank is an inner node in both trees. Each tree reduces and broadcasts half of the data. Then each rank receives and sends at most half of the data twice, which is as good as the ring in bytes, while the depth of a tree grows only like $\lg p$. NVIDIA reported up to 180× lower latency than rings at 24,576 GPUs. NCCL chooses between rings and trees per call.

When the assumptions fail. A real network is not flat (topology, above). Links can be shared (two flows through one switch port each get half). The reduction is not free on the GPU, which uses some SMs for the copy and add kernels. And $\alpha$ is not a single number: it depends on the protocol the library chooses. The model is still the right first estimate: if a measured time is far above it, look for a configuration problem before blaming the hardware.

Answers to section 1. (1) 1.75 GB. The busiest GPU must send at least $\frac{2(p-1)}{p}n = 2 \cdot \frac{7}{8} \cdot 1\text{ GB} = 1.75$ GB, and the ring sends exactly this. 0.125 GB is the size of one chunk and 1 GB is one copy of the vector; neither is enough, because every element needs $2(p-1)$ messages. (2) About the same. The bandwidth term grows from $1.75\,n\beta$ to $1.875\,n\beta$ (+7%); only the latency term grows, from $14\alpha$ to $30\alpha$.

4. Worked example #

(a) Ring all-reduce by hand, $p = 3$. $x_0 = (1, 2, 3)$, $x_1 = (10, 20, 30)$, $x_2 = (100, 200, 300)$; one element per chunk; the sum is $(111, 222, 333)$. Rule: in reduce-scatter step $k$, GPU $r$ sends chunk $(r - k) \bmod 3$; in all-gather step $k$, chunk $(r - k + 1) \bmod 3$.

step	GPU 0 → 1	GPU 1 → 2	GPU 2 → 0	state after the step (GPU 0; GPU 1; GPU 2)
start				$(1, 2, 3)$; $(10, 20, 30)$; $(100, 200, 300)$
RS 1	chunk 2: 3	chunk 0: 10	chunk 1: 200	$(1, 202, 3)$; $(10, 20, 33)$; $(110, 200, 300)$
RS 2	chunk 1: 202	chunk 2: 33	chunk 0: 110	$(\mathbf{111}, 202, 3)$; $(10, \mathbf{222}, 33)$; $(110, 200, \mathbf{333})$
AG 1	chunk 0: 111	chunk 1: 222	chunk 2: 333	$(111, 202, \mathbf{333})$; $(\mathbf{111}, 222, 33)$; $(110, \mathbf{222}, 333)$
AG 2	chunk 2: 333	chunk 0: 111	chunk 1: 222	$(111, 222, 333)$ on every GPU

Check RS 1 on GPU 1: it receives chunk 2 from GPU 0 (value 3) and adds its own 30: 33. Check RS 2 on GPU 0: it receives chunk 0 from GPU 2 (value 110, which is $10 + 100$) and adds its own 1: 111. After RS 2, GPU $r$ owns the finished chunk $r$ (bold). There were $2(p-1) = 4$ steps, and each GPU sent 4 elements $= \frac{2(p-1)}{p} \cdot 3$. ✓

(b) Ring or recursive doubling? $p = 16$, $\alpha = 10$ µs, 50 GB/s ($\beta = 2 \times 10^{-11}$ s/byte).

• $n = 1$ MB: ring $= 2 \cdot 15\,\alpha + \frac{30}{16} n\beta = 300 + 1.875 \cdot 20 = 300 + 37.5 = 337.5$ µs. Recursive doubling $= \lg 16\,(\alpha + n\beta) = 4\,(10 + 20) = 120$ µs. Recursive doubling is 2.8× faster.
• $n = 1$ GB: ring $= 0.3$ ms $+ 1.875 \cdot 20$ ms $= 37.8$ ms. Recursive doubling $= 4\,(0.01 + 20)$ ms $= 80.04$ ms. The ring is 2.1× faster.
• Crossover: $n^* = \dfrac{(30 - 4)\,\alpha}{(4 - 1.875)\,\beta} = \dfrac{26}{2.125}\cdot\dfrac{\alpha}{\beta} = 12.24 \cdot 5 \times 10^5 \text{ bytes} \approx 6.1$ MB. PyTorch DDP's default gradient bucket of 25 MB is above it: gradients are all-reduced in the bandwidth regime.

(c) Bus bandwidth of (b). For the 1 GB ring all-reduce: $\text{algbw} = 1\text{ GB}/37.8\text{ ms} = 26.5$ GB/s, and $\text{busbw} = 26.5 \times 1.875 = 49.6$ GB/s, close to the 50 GB/s link. The 0.8% gap is the latency term.

(d) Hierarchical all-reduce on 4 nodes. $N = 4$ nodes of $g = 8$ H100s, $n = 1$ GB. NVLink: 450 GB/s, $\alpha = 3$ µs (assumed). Network: 50 GB/s per GPU, $\alpha = 10$ µs (assumed).

1. Flat single ring over $P = 32$ GPUs. Every step crosses a network link somewhere, so each step takes $10\text{ µs} + \frac{1\text{ GB}}{32} / 50\text{ GB/s} = 10 + 625 = 635$ µs. There are $2 \cdot 31 = 62$ steps: $T = 39.4$ ms.
2. Hierarchical. Reduce-scatter in the node: $7 \cdot (3\text{ µs} + 125\text{ MB}/450\text{ GB/s}) = 7 \cdot 280.8$ µs $= 1.97$ ms. All-reduce across the 4 nodes on 125 MB per GPU: $6 \cdot (10\text{ µs} + 31.25\text{ MB}/50\text{ GB/s}) = 6 \cdot 635$ µs $= 3.81$ ms. All-gather in the node: 1.97 ms. Total: $T = 7.74$ ms, 5.1× faster than the flat ring.
3. Lower bound for the network part: $\frac{2 \cdot 3}{4} \cdot \frac{1\text{ GB}}{8 \cdot 50\text{ GB/s}} = 3.75$ ms. The hierarchical scheme is within 2% of it (the gap is the latency).
4. What nccl-tests would print: $\text{algbw} = 1\text{ GB}/7.74\text{ ms} = 129$ GB/s, and $\text{busbw} = 129 \times 2 \cdot 31/32 = 250$ GB/s. This is 5× the bandwidth of one network card. Nothing is wrong: the busbw factor assumes a flat network, and here most bytes travel over NVLink.

5. In code #

A simulated ring: $p$ NumPy vectors, messages collected first and delivered together (one step), and a counter of the elements each rank sends. It checks the worked example and the byte count.

import numpy as np

def ring_allreduce(xs):
    """Ring all-reduce of p vectors; returns results and elements sent."""
    p = len(xs)
    chunks = [np.array_split(np.array(x, dtype=float), p) for x in xs]  # copies
    sent = [0] * p
    for k in range(1, p):                          # reduce-scatter
        msgs = [(r, (r - k) % p) for r in range(p)]
        data = [chunks[r][c].copy() for r, c in msgs]
        for (r, c), d in zip(msgs, data):
            chunks[(r + 1) % p][c] += d
            sent[r] += d.size
    for k in range(1, p):                          # all-gather
        msgs = [(r, (r - k + 1) % p) for r in range(p)]
        data = [chunks[r][c].copy() for r, c in msgs]
        for (r, c), d in zip(msgs, data):
            chunks[(r + 1) % p][c] = d
            sent[r] += d.size
    return [np.concatenate(ch) for ch in chunks], sent

out, sent = ring_allreduce([[1, 2, 3], [10, 20, 30], [100, 200, 300]])
print(out[0], out[2], sent)     # [111. 222. 333.] [111. 222. 333.] [4, 4, 4]

rng = np.random.default_rng(0)
xs = [rng.standard_normal(8000) for _ in range(8)]
out, sent = ring_allreduce(xs)
print(all(np.allclose(o, sum(xs)) for o in out))   # True
print(sent[0], 2 * 7 / 8 * 8000)                    # 14000 14000.0

The cost formulas, the crossover and the busbw factor of the worked example:

from math import log2

def t_ring(p, a, b, n):
    return 2 * (p - 1) * a + 2 * (p - 1) / p * n * b

def t_rd(p, a, b, n):
    return log2(p) * (a + n * b)

def n_star(p, a, b):
    return (2 * (p - 1) - log2(p)) * a / ((log2(p) - 2 * (p - 1) / p) * b)

a, b = 10e-6, 1 / 50e9                  # 10 µs, 50 GB/s
for n in (1e6, 1e9):
    print(f"{n:.0e} B: ring {t_ring(16, a, b, n) * 1e3:.4f} ms,"
          f" rd {t_rd(16, a, b, n) * 1e3:.4f} ms")
# 1e+06 B: ring 0.3375 ms, rd 0.1200 ms
# 1e+09 B: ring 37.8000 ms, rd 80.0400 ms
print(f"n* = {n_star(16, a, b) / 1e6:.2f} MB")         # n* = 6.12 MB
print(f"p = 4: {n_star(4, a, b) / (a / b):.1f} a/b")    # p = 4: 8.0 a/b
algbw = 1e9 / t_ring(16, a, b, 1e9)
print(f"algbw {algbw / 1e9:.1f} GB/s, busbw {algbw * 30 / 16 / 1e9:.1f} GB/s")
# algbw 26.5 GB/s, busbw 49.6 GB/s

On a machine with PyTorch, torch.distributed gives the real collectives: dist.all_reduce(x), dist.reduce_scatter(out, chunks), dist.all_gather(outs, x) and dist.all_to_all(outs, ins). With the CPU backend gloo they run on a laptop; on GPUs the backend is NCCL. The notebook builds them from point-to-point messages instead.

6. Where it shows up #

• Data parallelism (lesson 8). DDP all-reduces gradient buckets while the backward pass runs. ZeRO-3 and FSDP all-gather the weights before the forward and before the backward pass and reduce-scatter the gradients: 3 collectives of $\frac{p-1}{p}$ times the weight bytes, against 2 for DDP's all-reduce, so 1.5× the traffic.
• Tensor and sequence parallelism (lesson 9, lesson 10). Activation all-reduces in every layer, or a reduce-scatter plus an all-gather with sequence parallelism. They sit on the critical path of every layer, so they run inside a node over NVLink.
• All-to-all. Expert parallelism in mixture-of-experts layers (dispatch tokens to experts and combine the results) and DeepSpeed-Ulysses (switch from sequence sharding to head sharding).
• Measuring a cluster. nccl-tests on 2, 4, 8, 16, … GPUs, with busbw compared against NVLink and network speeds, finds broken links, wrong network plugins (a fallback to TCP sockets gives a busbw many times lower) and bad topology settings before they waste a long training run.
• Scientific computing. Conjugate gradients and other Krylov solvers need global dot products in every iteration: all-reduces of a few bytes, purely in the latency regime. Large weather and climate models, which split a global grid over many GPUs, exchange halo regions with neighbours and reduce global quantities (energy, mass) the same way.

7. Common mistakes #

• Comparing algbw with the link speed. For all-reduce, algbw is lower than the link speed by the factor $\frac{2(p-1)}{p}$. Compare busbw.
• Comparing busbw of a multi-node run with one network card and concluding that something is impossible or broken. The busbw factor assumes a flat network; a hierarchical algorithm moves most bytes over NVLink.
• Counting an all-reduce as $n$ bytes per GPU. It is $\frac{2(p-1)}{p}n \approx 2n$.
• Using the ring for tiny messages. Its latency term $2(p-1)\alpha$ dominates. Very small DDP buckets pay it many times.
• Expecting a large all-reduce to slow down in proportion to $p$. The bandwidth term is almost constant in $p$; only the latency term grows.
• Applying recursive doubling to any $p$. It needs $p$ to be a power of two, or extra steps.

8. Check yourself #

1. $p = 4$ ranks, 400 MB per rank. How many bytes does each rank send in a ring all-reduce, a ring reduce-scatter and a ring all-gather (400 MB result)?
   Answer

   All-reduce: $2 \cdot \tfrac34 \cdot 400 = 600$ MB. Reduce-scatter: $\tfrac34 \cdot 400 = 300$ MB. All-gather: 300 MB.
2. nccl-tests on 8 GPUs: an all-reduce of 2 GB takes 20 ms, and an all-gather of 2 GB (full size) takes 10 ms. Give algbw and busbw for each.
   Answer

   All-reduce: algbw 100 GB/s, busbw $100 \cdot 1.75 = 175$ GB/s. All-gather: algbw 200 GB/s, busbw $200 \cdot 0.875 = 175$ GB/s. The same busbw: the same links, and both algorithms are bandwidth-optimal.
3. $p = 4$, $\alpha = 5$ µs, 100 GB/s. At which message size do the ring and recursive doubling take the same time?
   Answer

   Ring: $6\alpha + 1.5n\beta$. Recursive doubling: $2\alpha + 2n\beta$. Equal when $4\alpha = 0.5n\beta$, so $n^* = 8\alpha/\beta = 8 \cdot 5 \times 10^{-6} \cdot 10^{11} = 4$ MB.
4. Why do all ranks hold bitwise identical results after a ring all-reduce, and why does data parallelism need this?
   Answer

   Each chunk's sum is formed once, on one rank, in one fixed order, and is then only copied. (In recursive doubling, partners compute $a + b$ and $b + a$, which IEEE addition makes equal.) If replicas received slightly different gradients, their weights would drift apart, step by step.
5. A flat ring grows from 64 to 128 GPUs with the same links. What happens to the time of a 1 GB all-reduce?
   Answer

   The bandwidth term goes from $1.969\,n\beta$ to $1.984\,n\beta$ (+0.8%). The latency term goes from $126\alpha$ to $254\alpha$. For 1 GB the time stays almost the same.
6. All-gather needs only about $n$ bytes per rank. Why does all-reduce need about $2n$?
   Answer

   For each element, $p - 1$ messages are needed before the first rank can hold the full sum (every other input must leave its rank), and $p - 1$ more after it (every other rank must still receive the sum). $2(p-1)$ messages per element give $\frac{2(p-1)}{p}n$ bytes for the busiest rank. In an all-gather nothing must be combined first, so only the second half is needed.

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. What does the α-β model say about one message of $m$ bytes?

   Show answer

2. Cost of a ring all-reduce of $n$ bytes on $p$ ranks?

   Show answer

3. How is all-reduce built from two other collectives?

   Show answer

4. Cost of recursive doubling all-reduce?

   Show answer

5. How many bytes does each rank send in a ring reduce-scatter (or ring all-gather) with $n$-byte full buffers?

   Show answer

6. Compute the ring/recursive-doubling crossover for $p = 4$.

   Show answer

7. Why does a large ring all-reduce not get slower with more GPUs?

   Show answer

8. How do you get bus bandwidth from algorithm bandwidth for an all-reduce?

   Show answer

9. What does an all-to-all do?

   Show answer

10. What is a hierarchical all-reduce?

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "Explain ring all-reduce and its cost." — Reduce-scatter then all-gather, $2(p-1)$ steps of $n/p$ bytes: $2(p-1)\alpha + \frac{2(p-1)}{p}n\beta$. Bandwidth-optimal; the latency is linear in $p$.
• "When is a tree or recursive doubling better than a ring?" — Small messages or very many ranks: $\lg p$ latency instead of $2(p-1)$. Give the crossover $n^*$.
• "DDP scales well on one node and badly across 8 nodes. What do you check?" — busbw with nccl-tests against the network card speed; the network plugin and transport (a TCP fallback); overlap of the all-reduce with the backward pass; bucket size; which algorithm NCCL chose (NCCL_DEBUG=INFO).
• "Why does FSDP send 1.5× the bytes of DDP?" — Two all-gathers (forward and backward) and one reduce-scatter, against one reduce-scatter and one all-gather inside DDP's all-reduce.
• "Why is all-to-all hard to scale?" — Different data for every pair, so it needs bisection bandwidth, and uneven block sizes (expert load) make the largest block set the time.

10. Practice #

The notebook for this lesson runs in Colab, with NumPy only. A small SimRing class counts the steps and the bytes each simulated GPU sends. Five exercises, each with a check cell and a folded solution:

1. Ring reduce-scatter and ring all-gather on SimRing, checked against sum and against the expected step and byte counts.
2. Ring all-reduce built from exercise 1, for $p = 2, \dots, 9$ and vector lengths that $p$ does not divide.
3. Recursive doubling for $p$ a power of two, with the same checks.
4. The α-β cost functions and the crossover size $n^*$, checked against the simulator's step and byte counts.
5. Convert a table of nccl-tests results (algbw) to busbw and find the run with the slowest link.

11. Watch and read #

EfficientML.ai Lecture 19 - Distributed Training Part 1 (MIT 6.5940, Fall 2024)Song Han · MIT HAN Lab · 70 min

Data parallelism and the communication primitives (all-reduce, ring, tree), then ZeRO, pipeline and tensor parallelism.

Lecture 17: NCCLGPU MODE · 60 min

How NCCL implements collectives on real GPUs and how to call them.

MultiGPU + NCCL from the authorsJeff Hammond · GPU MODE · 101 min

Multi-GPU communication and NCCL's algorithms, explained by people who build it.

• Thakur, Rabenseifner and Gropp (2005), Optimization of Collective Communication Operations in MPICH: §3 (the cost model), §4.1 (all-gather: ring, recursive doubling, Bruck), §4.3 (all-to-all), §4.5 (reduce and all-reduce, Rabenseifner's algorithm).
• Patarasuk and Yuan (2009), Bandwidth optimal all-reduce algorithms for clusters of workstations: §3 (the lower bound), §4 (the ring algorithm).
• NVIDIA nccl-tests, Performance reported by NCCL tests: time, algbw, busbw and the factor of each collective.
• NVIDIA NCCL documentation, Collective operations, with pictures of each collective; and the blog post Massively Scale Your Deep Learning Training with NCCL 2.4 on double binary trees.
• Andrew Gibiansky (2017), Bringing HPC Techniques to Deep Learning: the ring all-reduce, step by step, with pictures.
• Hugging Face, The Ultra-Scale Playbook: the appendix on collective operations and the data-parallelism chapter.
• Stanford CS336 (2025), lecture 7 Parallelism 1 (on YouTube): collectives and their costs in the context of LLM training.