Collective communication: all-reduce, reduce-scatter, all-gather
When a model trains on many GPUs, the GPUs must keep exchanging numbers: gradients, weights, activations. A small set of patterns, called collectives, covers almost all of this traffic. This session shows what each collective does, why the ring all-reduce is built from a reduce-scatter and an all-gather, how to predict its time from bandwidth and latency, what hardware carries the bytes, and how training hides the communication behind computation.
What you will learn
- What broadcast, reduce, all-reduce, reduce-scatter, all-gather and all-to-all do, with the same four GPUs and the same numbers
- How the ring all-reduce works step by step, and why it is a reduce-scatter followed by an all-gather
- The alpha-beta cost model: why each GPU sends 2(N−1)/N of the data, and when latency matters more than bandwidth
- Ring versus tree, algorithm bandwidth versus bus bandwidth, and how to read an nccl-tests result
- The hardware: NVLink and NVSwitch inside a node, PCIe, InfiniBand and Ethernet between nodes, and hierarchical all-reduce
- Which parallel method uses which collective: DDP, ZeRO and FSDP, tensor and sequence parallelism, mixture of experts
- How gradient buckets let communication run during the backward pass, and how to estimate the time that is still exposed
Why this matters
One GPU cannot train a modern LLM in a reasonable time. Llama-class models are trained on thousands of GPUs at once. Those GPUs only help if they can share their work: every step, each GPU must give its gradients to the others and get theirs back. If this sharing is slow, the GPUs sit idle and you pay for hardware that does nothing.
The sharing happens through a small set of standard patterns called collective operations, or collectives. A collective is a communication step in which all GPUs of a group take part at the same time, each with its own piece of data. The most important ones are all-reduce (everyone ends with the sum of everyone’s data), reduce-scatter (everyone ends with one slice of the sum) and all-gather (everyone ends with all the slices). Every parallel training method in the next sessions is built from these: data parallelism uses all-reduce, ZeRO and FSDP use reduce-scatter and all-gather, tensor parallelism uses all-reduce inside each layer, and mixture-of-experts models use all-to-all. [Certain]
In session 42 we asked whether a kernel is limited by compute or by memory bandwidth. This session asks the same question one level up: is a training step limited by compute or by the network between GPUs? By the end you will be able to estimate, on paper, how long an all-reduce of 16 GB takes on 8 GPUs inside a server or on 64 GPUs across servers, and whether that time can be hidden.
The vocabulary: ranks, groups and the six collectives
Some words first. Each GPU runs one copy of the training program, called a process. Each process has a number, its rank, from 0 to \(N-1\), where \(N\) is the world size (the number of processes). A collective runs inside a process group: a chosen set of ranks, for example all 64, or only the 8 GPUs inside one server. All ranks of the group must call the same collective, with buffers of matching size; if one rank does not call it, the others wait forever.
Take four GPUs. Each holds a vector of four numbers, split into four chunks (here one number per chunk). GPU 0 holds \([1, 2, 3, 4]\), GPU 1 holds \([5, 6, 7, 8]\), and so on. In a real job each “number” would be a chunk of millions of gradient values; the patterns are the same.
| Collective | Input on each rank | Output on each rank | Typical use in training |
|---|---|---|---|
| Broadcast | rank 0 has \(x\) | everyone has \(x\) | send the initial weights from rank 0 to all ranks |
| Reduce | rank \(r\) has \(x_r\) | rank 0 has \(\sum_r x_r\) | sum a metric on one rank for logging |
| All-reduce | rank \(r\) has \(x_r\) | everyone has \(\sum_r x_r\) | average gradients in data parallelism; tensor-parallel layers |
| Reduce-scatter | rank \(r\) has \(x_r\) (\(N\) chunks) | rank \(r\) has chunk \(r\) of \(\sum_r x_r\) | gradients in ZeRO-2/3 and FSDP; sequence parallelism |
| All-gather | rank \(r\) has chunk \(r\) | everyone has all \(N\) chunks | gather sharded weights in ZeRO-3 and FSDP; sequence parallelism |
| All-to-all | rank \(r\) has \(N\) chunks, one for each rank | rank \(r\) has chunk \(r\) from every rank | send tokens to their experts in mixture of experts |
“Reduce” means combine with an operation such as sum, max or average. Sum is by far the most common. Figure 1 shows each collective with real numbers. Click through them before you read on.
How to read Figure 1
Each row is one GPU; each box is one chunk. Compare all-reduce with reduce-scatter: reduce-scatter computes the same sums, 28, 32, 36 and 40, but each rank keeps only one of them. Then look at all-gather: it takes one chunk per rank and gives every rank all four. If you run reduce-scatter and then all-gather on its output, you get exactly the all-reduce result. All-to-all is a transpose: chunk \(c\) of rank \(r\) moves to rank \(c\), at position \(r\). No values are added.
The naive way: send everything to one GPU
How would you build an all-reduce from simple sends and receives? The first idea is a parameter server: every rank sends its full vector of \(M\) bytes to rank 0. Rank 0 adds them and sends the result back to everyone. It works, but rank 0 receives \((N-1)M\) bytes and then sends \((N-1)M\) bytes. All other links sit idle while rank 0’s link carries everything. For 8 GPUs and 16 GB of gradients, rank 0 must receive 112 GB and send 112 GB. The time grows linearly with \(N\): add more GPUs and the all-reduce gets slower.
The better idea is to give every GPU the same amount of work and to use every link at the same time. The ring algorithm does exactly that.
Ring all-reduce, step by step
Put the \(N\) GPUs in a circle. Each GPU sends only to its right neighbour and receives only from its left neighbour. Cut each vector into \(N\) chunks. The algorithm has two phases.
- Reduce-scatter phase (\(N-1\) steps). In each step, every GPU sends one chunk to the right. The receiver adds it to its own copy of that chunk. The chunk indices are chosen so that a partial sum keeps travelling around the circle and picks up one more GPU’s contribution at each hop. After \(N-1\) steps, every chunk has visited every GPU, and GPU \(r\) holds the complete sum of chunk \(r\).
- All-gather phase (\(N-1\) steps). Now each GPU owns one finished chunk. In each step, every GPU passes a finished chunk to the right, and the receiver simply copies it (no addition). After \(N-1\) more steps, everyone has all \(N\) finished chunks.
Figure 2 runs this algorithm in your browser on the numbers of Figure 1 (Algorithm 1 below writes it out). Each row is one GPU and each box is one chunk. In a send step, every GPU lifts one chunk out of its buffer and the chunk travels to its right neighbour: the GPU one row below, and the last GPU wraps around to GPU 0. In the next step the receiver adds it (reduce-scatter) or copies it (all-gather). The program on the left highlights the line that runs; the panel on the right writes that line with the live values, the bytes each GPU has sent so far, and the cost formula (43.4) of the next section with the numbers filled in. Change the number of GPUs \(N\) or the buffer size \(M\) and play it again.
- input: \(x\) split into chunks \(x[0..N-1]\); right neighbour \(r+1 \bmod N\)
- for \(s = 0, \dots, N-2\) // reduce-scatter
- send \(x[(r-1-s) \bmod N]\) to the right
- \(x[c] \leftarrow x[c] + \text{received}\) // add
- // now \(x[r]\) is the full sum of chunk \(r\)
- for \(s = 0, \dots, N-2\) // all-gather
- send \(x[(r-s) \bmod N]\) to the right
- \(x[c] \leftarrow \text{received}\) // copy
- return \(x\) // the same sum on every GPU
How to read Figure 2
Press Play with \(N = 4\) and follow chunk 0 (the first column). In ring step 1, GPU 1 sends its 5 to GPU 2, which now has \(9 + 5 = 14\). In ring step 2, GPU 2 sends 14 to GPU 3: \(13 + 14 = 27\). In ring step 3, GPU 3 sends 27 to GPU 0, which wraps around the ring: \(1 + 27 = 28\), the full sum, and it lands on GPU 0. The starting chunks are chosen so that GPU \(r\) finishes with chunk \(r\), as PyTorch’s reduce_scatter_tensor does. After step 3, each GPU holds one green value, on the diagonal. Then the green values travel around and are copied. Watch the bars: all GPUs send exactly one chunk per step, so they always have the same height. After 6 steps each GPU has sent 6 chunks of size \(M/4\), which is \(1.5M\) = \(2(N-1)/N \cdot M\): 6 GB for \(M = 4\) GB. Now try \(N = 6\): 10 steps of \(M/6\), so \(1.67M\). The total per GPU grows only a little with \(N\).
- input: buffer \(x\) of \(M\) bytes, split into chunks \(x[0], \dots, x[N-1]\); right neighbour \(r+1 \bmod N\), left neighbour \(r-1 \bmod N\)
- for \(s = 0, \dots, N-2\) // reduce-scatter phase
- send \(x[(r - 1 - s) \bmod N]\) to the right; receive chunk \(c = (r - 2 - s) \bmod N\) from the left
- \(x[c] \leftarrow x[c] + \text{received}\) // one more rank added into this partial sum
- // now \(x[r]\) is the full sum over all ranks
- for \(s = 0, \dots, N-2\) // all-gather phase
- send \(x[(r - s) \bmod N]\) to the right; receive chunk \(c = (r - 1 - s) \bmod N\) from the left
- \(x[c] \leftarrow \text{received}\) // copy, no addition
- return \(x\) // every rank holds the same summed buffer
Two remarks. First, the send and the receive in one step happen at the same time, over the two directions of the links. Second, real libraries split each chunk further into small pieces and pipeline them, so a GPU can forward the first piece while the next one is still arriving. [Certain] The formulas below assume this.
What a collective costs: the alpha-beta model
To predict the time of a collective we need a model of one message. The standard one is the alpha-beta model (also called the latency-bandwidth model): sending a message of \(n\) bytes over one link takes
- Read the symbols
- \(\alpha\)
- the latency: fixed time per message, paid even for 1 byte (launching the transfer, crossing switches, synchronizing). Microseconds on GPU links. [Likely]
- \(\beta\)
- the bandwidth of the link in bytes per second, in one direction
- \(n\)
- the message size in bytes
Small messages are latency-bound (\(\alpha\) dominates). Large messages are bandwidth-bound (\(n/\beta\) dominates). Example: with \(\alpha = 5\) µs and \(\beta = 50\) GB/s, a 1 MB message takes \(5 + 20 = 25\) µs; a 1 KB message takes about 5 µs, almost all latency.
Reduce-scatter and all-gather
In the ring reduce-scatter, there are \(N-1\) steps, and in each step every GPU sends one chunk of \(M/N\) bytes. All GPUs send at the same time on different links, so a step costs one message time:
The all-gather has the same pattern of steps and chunk sizes (only “add” becomes “copy”), so it costs the same:
Here \(M\) is the size of the full vector: for reduce-scatter, the input on each rank; for all-gather, the output on each rank (each rank contributes \(M/N\)).
All-reduce
The ring all-reduce is a reduce-scatter followed by an all-gather, so its time is the sum:
- Read the symbols
- \(N\)
- the number of GPUs in the ring
- \(M\)
- the size of the buffer being summed, in bytes (for example all gradients: 2 bytes × parameters in BF16)
- \(2(N-1)\)
- the number of ring steps; each pays one latency \(\alpha\)
- \(2(N-1)/N \cdot M\)
- the bytes each GPU sends (and receives) in total
Look at the bandwidth term. As \(N\) grows, \(2(N-1)/N\) goes to 2, not to infinity. Each GPU sends about \(2M\) bytes no matter how many GPUs there are. With 8 GPUs it is \(1.75M\); with 1,024 GPUs it is \(1.998M\). This is why the ring scaled data parallelism to many GPUs, and why Baidu and then Horovod (2017–2018) made it the standard for deep learning. [Certain] It is also the best possible: in any all-reduce algorithm, each GPU must send at least \(2(N-1)/N \cdot M\) bytes (Patarasuk and Yuan, 2009), so the ring is bandwidth-optimal. [Certain]
Compare the naive parameter server: \(T \approx 2(N-1)(\alpha + M/\beta)\) on rank 0. Its bandwidth term grows with \(N\); the ring’s does not.
An 8B-parameter model has \(8 \times 10^9 \times 2 = 16\) GB of BF16 gradients. Ignore latency, which is tiny for such a big buffer.
8 GPUs inside one H100 server, NVLink at 450 GB/s per direction: each GPU sends \(2 \cdot \tfrac{7}{8} \cdot 16 = 28\) GB, so \(T = 28 / 450 = 62\) ms.
64 GPUs in one flat ring across 8 servers, where the slowest links are InfiniBand at 50 GB/s per GPU: each GPU sends \(2 \cdot \tfrac{63}{64} \cdot 16 = 31.5\) GB, so \(T = 31.5 / 50 = 630\) ms. A ring is as slow as its slowest link.
Is 630 ms a lot? With 4M tokens per step spread over 64 GPUs, each GPU processes 65,536 tokens, which costs \(6 \cdot 8\times10^9 \cdot 65{,}536 = 3.1 \times 10^{15}\) FLOPs. At 40% of the H100’s 989 dense BF16 TFLOP/s that takes about 8.0 s. So the all-reduce is about 8% of the step if it is not hidden, and close to 0% if it overlaps with the backward pass. With a smaller batch per GPU the ratio grows fast.
Latency, trees, and algorithm bandwidth vs bus bandwidth
The ring has one weak point: \(2(N-1)\) steps, each paying \(\alpha\). With 1,024 GPUs that is 2,046 latencies; at 5 µs each, over 10 ms, even for a 1 KB message. For small messages and many GPUs, tree algorithms are better. In a tree, partial sums flow up to a root and the result flows back down, so the number of steps grows with \(\log_2 N\) instead of \(N\). NCCL uses a double binary tree: two trees at once, so that each GPU is an inner node in one and a leaf in the other, and both halves of the data are busy. [Certain] A simple model for it is
This is a rough model. Its bandwidth term is close to the ring’s, but its latency term is much smaller: 20 steps instead of 2,046 for \(N = 1{,}024\). [Likely] NCCL picks the algorithm (ring, tree, and others such as NVLS, which lets the NVSwitch do the additions) and the protocol for each call from the message size and the topology. [Certain]
Measuring a collective: algbw and busbw
The standard benchmark is nccl-tests (all_reduce_perf and friends). It reports two numbers. The algorithm bandwidth is the buffer size divided by the time, \(\text{algbw} = M / t\). The bus bandwidth corrects for how many bytes the algorithm really has to move per GPU, so you can compare it directly with the link speed:
Formula (43.6) is (43.4) solved for \(\beta\) with \(\alpha = 0\). Example: a 1 GB all-reduce on 8 GPUs in 5 ms gives algbw 200 GB/s and busbw 350 GB/s. If the link is 450 GB/s per direction, you reach 78% of it. Busbw is what you should compare across GPU counts and with the hardware spec. [Certain]
How to read Figure 3
On the left of the plot (small buffers), the lines are flat: time is all latency, and the tree wins because it has fewer steps. On the right (large buffers), the lines rise with slope 1: time is all bandwidth, and ring and tree are almost equal. Move \(N\) up to 1,024 and watch the ring’s flat part rise, since it pays \(2(N-1)\) latencies. Then switch from NVLink to 100 GbE: everything on the right moves up by a factor of 36. The readout gives the busbw you would measure if the model were exact.
The hardware that carries the bytes
The \(\beta\) in the formulas is not one number. A training cluster has a hierarchy of links, each about an order of magnitude apart.
- NVLink and NVSwitch (inside a server). NVLink is NVIDIA’s direct GPU-to-GPU link. On H100, each GPU has 18 NVLink 4 links with 900 GB/s in total, which is 450 GB/s in each direction. In an 8-GPU server such as DGX H100, the links go to NVSwitch chips, so every pair of GPUs can talk at full speed at the same time. Blackwell (NVLink 5) doubles this to 1,800 GB/s per GPU. [Certain]
- PCIe (GPU to CPU, and to network cards). PCIe Gen5 x16 gives about 63 GB/s per direction; Gen4 x16 about 32 GB/s. [Certain] GPUs without NVLink (many workstation and cloud cards) do all-reduce over PCIe, often through the CPU’s root complex, and are much slower.
- InfiniBand (between servers). A low-latency network built for clusters. An NDR port runs at 400 Gb/s, which is 50 GB/s. DGX H100 has eight such ports, one per GPU. [Certain] With GPUDirect RDMA, the network card reads and writes GPU memory directly, without a copy through the CPU. [Certain] Some InfiniBand switches can also do the additions themselves (SHARP), which halves the data each GPU must send. [Likely]
- Ethernet with RoCE (between servers). RDMA over Converged Ethernet runs the same kind of direct transfers on Ethernet at 100, 200 or 400 Gb/s. Many large clusters use it instead of InfiniBand. Plain TCP Ethernet works too but has higher latency and uses CPU time. [Likely]
Hierarchical all-reduce
The worked example showed that a flat 64-GPU ring runs at InfiniBand speed. A hierarchical all-reduce uses the fast links for most of the work. With \(G\) GPUs per server and \(K\) servers:
- Reduce-scatter inside each server over NVLink: each GPU now holds the server’s sum of \(1/G\) of the buffer.
- All-reduce across servers, \(K\) GPUs per ring, one ring per GPU index, all \(G\) rings in parallel over their own ports. Each ring carries only \(M/G\) bytes.
- All-gather inside each server over NVLink.
For the same 16 GB on \(K = 8\) servers of \(G = 8\) GPUs: \(62\) ms on NVLink plus \(2 \cdot \tfrac{7}{8} \cdot 2 / 50 = 70\) ms on InfiniBand, about 132 ms in total instead of 630 ms. NCCL builds this kind of schedule automatically from the topology it detects. [Likely]
Figure 5 runs the three phases on a small cluster: \(K = 2\) servers with \(G = 4\) GPUs each, so 8 GPUs in total. GPU \(g\) of server A starts with \([1+4g, \dots, 4+4g]\); server B continues the count from 17. Inside each server the ring of Figure 2 runs over NVLink. Between the servers, GPU \(g\) of A and GPU \(g\) of B form a ring of two over their own network port. With \(K = 2\) the cross-server all-reduce is one exchange: each GPU sends its chunk to its partner and adds what it receives. That is \(M/G\) bytes, exactly the \(\frac{2(K-1)}{K} \cdot \frac{M}{G}\) of (43.7).
- input: GPU \(g\) of server \(k\); \(x\) split into \(G\) chunks
- for \(s = 0, \dots, G-2\): send \(x[(g-1-s) \bmod G]\) to GPU \(g+1\) // NVLink
- \(x[c] \leftarrow x[c] + \text{received}\) // reduce-scatter
- send \(x[g]\) to GPU \(g\) of the other server; \(x[g] \leftarrow x[g] + \text{received}\) // network
- for \(s = 0, \dots, G-2\): send \(x[(g-s) \bmod G]\) to GPU \(g+1\) // NVLink
- \(x[c] \leftarrow \text{received}\) // all-gather
- return \(x\) // the sum over all \(KG\) GPUs
How to read Figure 5
Press Play. For the first three ring steps, the two servers run the ring of Figure 2 side by side, at the same time. After them, server A holds its own sums 28, 32, 36, 40 on the diagonal, and server B holds 92, 96, 100, 104. Then each diagonal value crosses the network once (purple) and is added: \(28 + 92 = 120\), \(32 + 96 = 128\), \(36 + 100 = 136\), \(40 + 104 = 144\). These are the sums over all 8 GPUs. Three more NVLink steps copy them to everyone. Now look at the bytes in the panel: each GPU sends \(1.5M\) over NVLink but only \(M/4\) over the network. With \(M = 16\) GB that is 53.3 ms on NVLink plus 80 ms on the network, 133.3 ms in total. A flat ring of all 8 GPUs would run at network speed: \(2 \cdot \tfrac{7}{8} \cdot 16 / 50 = 560\) ms.
NCCL: the library under PyTorch
NCCL (NVIDIA Collective Communications Library, pronounced “nickel”) implements all of the collectives above for NVIDIA GPUs. PyTorch calls it when you create a process group with the "nccl" backend; AMD GPUs use RCCL, a port with the same interface, and CPUs use Gloo. [Certain] A few facts that matter in practice:
- Collectives are GPU kernels. NCCL runs its copies and additions as CUDA kernels on a few SMs. So communication uses some GPU compute, and it is ordered on a CUDA stream like any kernel. [Certain]
- Topology detection. At start-up NCCL finds NVLink, PCIe switches and network cards and builds rings and trees that use the fastest paths. [Certain]
- Algorithms and protocols.
NCCL_ALGOcan force Ring, Tree, NVLS, CollNet or PAT;NCCL_PROTOchooses LL, LL128 or Simple (the low-latency protocols are for small messages). Normally you leave both to NCCL’s tuner. [Certain] - Debugging.
NCCL_DEBUG=INFOprints the topology and the chosen rings; it is the first thing to look at when multi-node training is slow. A rank that never reaches a collective causes a hang, not an error, until a timeout fires. [Certain]
The PyTorch calls map one to one onto the collectives. The first listing simulates Algorithm 1 on four “GPUs” in one process, so you can check the ring logic. The second runs the real collectives on four CPU processes with the Gloo backend; change "gloo" to "nccl" and move the tensors to the GPU to run on GPUs.
import torch def ring_all_reduce(bufs): """Simulate a ring all-reduce. bufs: N equal 1-D tensors, one per GPU. Sums in place.""" N = len(bufs) ch = [list(b.chunk(N)) for b in bufs] # ch[r][c] is a view of chunk c on rank r for s in range(N - 1): # phase 1: reduce-scatter, N-1 steps msgs = [(r, (r - 1 - s) % N, ch[r][(r - 1 - s) % N].clone()) for r in range(N)] for r, c, data in msgs: # all ranks send at the same time ch[(r + 1) % N][c] += data # the right neighbour adds it # now rank r holds the full sum of chunk r for s in range(N - 1): # phase 2: all-gather, N-1 steps msgs = [(r, (r - s) % N, ch[r][(r - s) % N].clone()) for r in range(N)] for r, c, data in msgs: ch[(r + 1) % N][c].copy_(data) # the right neighbour overwrites it return bufs torch.manual_seed(0) grads = [torch.randn(12) for _ in range(4)] expected = torch.stack(grads).sum(0) out = ring_all_reduce([g.clone() for g in grads]) print(all(torch.allclose(o, expected, atol=1e-6) for o in out)) # True fig2 = [torch.arange(4.) + 1 + 4 * r for r in range(4)] # the numbers of Figure 2 print(ring_all_reduce(fig2)[2]) # tensor([28., 32., 36., 40.])
import os, torch, torch.distributed as dist, torch.multiprocessing as mp def worker(rank, world): os.environ["MASTER_ADDR"], os.environ["MASTER_PORT"] = "127.0.0.1", "29515" dist.init_process_group("gloo", rank=rank, world_size=world) # "nccl" on GPUs x = torch.arange(4.) + 1 + 4 * rank # rank 0: [1,2,3,4], rank 1: [5,6,7,8], ... ar = x.clone(); dist.all_reduce(ar) # sum, on every rank rs = torch.zeros(1); dist.reduce_scatter_tensor(rs, x) # rank r gets the sum of chunk r ag = torch.zeros(4 * world); dist.all_gather_into_tensor(ag, x) # everyone gets everything bc = x.clone(); dist.broadcast(bc, src=0) # everyone gets rank 0's copy # all-reduce = reduce-scatter + all-gather ag2 = torch.zeros(world); dist.all_gather_into_tensor(ag2, rs) # overlap: start the collective, do other work, wait only when the result is needed w = x.clone(); work = dist.all_reduce(w, async_op=True) busy = (x @ x) # compute runs meanwhile work.wait() if rank == 1: print("all_reduce ", ar.tolist()) # [28.0, 32.0, 36.0, 40.0] print("reduce_scatter ", rs.tolist()) # [32.0] (chunk 1 of the sum) print("all_gather ", ag.tolist()) # [1.0, 2.0, ..., 16.0] print("broadcast ", bc.tolist()) # [1.0, 2.0, 3.0, 4.0] print("RS then AG ", ag2.tolist(), torch.equal(ag2, ar)) # [28.0, ...] True print("async ", w.tolist()) # [28.0, 32.0, 36.0, 40.0] dist.destroy_process_group() if __name__ == "__main__": mp.spawn(worker, args=(4,), nprocs=4)
Gloo does not implement all_to_all; it needs the NCCL (or MPI) backend. [Certain, checked with PyTorch 2.8]
Which parallel method uses which collective
The next sessions are all built from these pieces, so it helps to see the bill for each method now. Let \(\Psi\) be the number of bytes of one full copy of the gradients (or weights), and \(N\) the number of data-parallel GPUs. Each GPU sends:
| Method | Collectives per step | Bytes sent per GPU |
|---|---|---|
| DDP (session 44) | all-reduce of gradients | \(2\frac{N-1}{N}\Psi\) |
| ZeRO-1 and ZeRO-2 (session 45) | reduce-scatter of gradients, all-gather of updated weights | \(2\frac{N-1}{N}\Psi\), the same as DDP |
| ZeRO-3 and FSDP (session 46) | all-gather weights in forward, again in backward; reduce-scatter gradients | \(3\frac{N-1}{N}\Psi\), 1.5 times DDP |
| Tensor parallelism (session 48) | 2 all-reduces of activations per layer in forward, 2 in backward (Megatron-LM) | depends on batch × sequence × hidden size, not on parameters |
| Sequence parallelism | each all-reduce becomes a reduce-scatter plus an all-gather | the same bytes, but activations between them are split |
| Mixture of experts | 2 all-to-alls per MoE layer in forward (send tokens to experts, bring results back), 2 in backward | \(\frac{N-1}{N}\) of the routed activations per all-to-all |
| Pipeline and context parallelism (session 49) | point-to-point send and receive between neighbours; ring attention passes K and V around a ring | activations at stage borders; K and V blocks |
The ZeRO paper makes this exact accounting: stages 1 and 2 keep the DDP volume, and stage 3 adds one more all-gather. [Certain] That table is also the reason for the identity in Figure 1: since all-reduce = reduce-scatter + all-gather, ZeRO can stop after the reduce-scatter, update only its own slice of the weights, and all-gather the result. It moves the same bytes as DDP but keeps only \(1/N\) of the optimizer state.
Overlapping communication with compute
Even a fast all-reduce is wasted time if the GPU waits for it. The fix is overlap: run the communication on a separate CUDA stream while the compute stream keeps working. GPUs can do this because the NCCL kernels use only a few SMs and the copy engines and network cards work in parallel with the math. [Likely]
For data parallelism the opportunity is in the backward pass. The gradients of the last layer are ready first, long before the backward pass reaches the first layer. So we do not need to wait for all gradients: as soon as a group of gradients is ready, we start its all-reduce. PyTorch DDP groups gradients into buckets (25 MB by default, with a smaller first bucket of 1 MB) and launches one all-reduce per bucket from a hook that fires when the bucket is full. [Certain, checked in PyTorch 2.8 source] If the network is fast enough, only the last bucket’s all-reduce is left after the backward pass ends:
- Read the symbols
- \(T_{\text{comm}}\)
- the total time of all bucket all-reduces, from (43.4)
- \(T_{\text{tail}}\)
- the part that cannot be hidden: mostly the all-reduce of the last bucket, which can only start when the backward pass ends
Bucket size is a trade-off. Small buckets start early and leave a short tail, but each one pays the latency \(2(N-1)\alpha\), and many small calls use the links badly. One huge bucket is efficient per byte but starts only at the end, so nothing overlaps. Figure 6 lets you try it.
How to read Figure 6
The top row is the compute stream; the bottom row is the communication stream. With the defaults (100 MB buckets, 50 GB/s), the all-reduces run under the backward pass and only about 4 ms remain after it. Turn overlap off: the step grows by the full 91 ms of communication. Set the bucket size to 2,400 MB: one bucket, which can only start at the end, so overlap does nothing. Now drop the bandwidth to 12.5 GB/s: the communication (343 ms) is longer than the whole backward pass (240 ms), so even perfect overlap leaves over 100 ms exposed. Then the step is communication-bound, and the fixes are a faster network, gradient compression, or fewer bytes (for example, larger batches per GPU, so communication happens less often per token).
- before training: split the parameters into buckets of about \(B\) bytes, in reverse order of the forward pass
- for each parameter, register a hook that fires when its gradient is ready
- in the hook: mark the gradient ready; if all gradients of its bucket are ready then
- launch
all_reduce(bucket, async_op=True)on the communication stream // the backward pass keeps running - after the backward pass: wait for all outstanding all-reduces
- divide each gradient by \(N\) // sum to average; often folded into the all-reduce
- run the optimizer step // every rank has the same gradients, so the weights stay identical
The same idea shows up everywhere. FSDP prefetches: it starts the all-gather of the next layer’s weights while the current layer computes. Tensor parallelism can split matrix multiplications into pieces so that one piece’s all-reduce overlaps with the next piece’s math. [Likely] The cost of overlap is that the communication kernels take some SMs and memory bandwidth away from compute, so the compute runs a little slower while they run. [Likely]
Where this is used
| Setting | Collective | Why |
|---|---|---|
| LLM pretraining with data parallelism | all-reduce of gradients, bucketed and overlapped | every replica must apply the same update (session 44) |
| LLM pretraining with FSDP or ZeRO-3 | all-gather of weights, reduce-scatter of gradients | each GPU keeps only \(1/N\) of weights, gradients and optimizer state |
| Serving a 70B model on 8 GPUs with tensor parallelism | all-reduce of activations, twice per layer, for every generated token | small messages, so latency (\(\alpha\)) and NVLink matter more than bandwidth [Likely] |
| Mixture-of-experts training and serving | all-to-all to send tokens to experts and back | experts live on different GPUs (session 29) |
| Contrastive training of video–text retrieval models (CLIP-style) | all-gather of embeddings from all GPUs | each clip is compared with the texts of the whole global batch, not only the local one, so there are many more negatives |
| Long-video understanding with very long context | point-to-point ring passing of K and V blocks (ring attention) | the sequence of frame tokens is split across GPUs; each GPU must see every key |
| Distributed evaluation (video classification, action recognition) | all-reduce of counts, or all-gather of predictions | each GPU scores a shard of the test set; the final accuracy needs all of them |
| Sharded video fingerprint or Video-RAG index search | all-gather of each shard’s top-k results, then a merge | the index is too large for one GPU; each GPU searches its part |
Common mistakes
- Mixing up bits and bytes, or one and two directions. 400 Gb/s InfiniBand is 50 GB/s; NVLink 4’s “900 GB/s” is 450 GB/s each way. A factor of 8 or 2 in a capacity plan is a real money mistake.
- Reading algbw as link speed. An all-reduce algbw of 200 GB/s on 8 GPUs means busbw 350 GB/s. Compare busbw with the hardware, formula (43.6).
- Forgetting that a ring runs at its slowest link. One slow server, one bad cable, or one GPU on the wrong PCIe switch slows down the whole job. A flat ring across servers runs at network speed, not NVLink speed.
- Ranks calling collectives in different orders or with different sizes. The result is a hang, not an error message. A typical cause is an
if rank == 0:block that contains a collective, or data-dependent control flow that differs between ranks. - Summing instead of averaging. All-reduce with SUM gives \(N\) times the gradient. DDP divides by \(N\); in hand-written code you must do it yourself, or the effective learning rate is \(N\) times too large.
- Too many tiny collectives. Reducing each parameter tensor separately pays \(2(N-1)\alpha\) hundreds of times. Bucket them (or flatten them into one buffer).
- Reducing in low precision without care. Summing BF16 gradients across many ranks loses precision; many setups reduce in FP32, or at least accumulate in FP32. [Likely]
- Expecting overlap without checking. If you call
wait()or read the result right after launching, or run everything on one stream, nothing overlaps. Confirm in a profiler trace that the NCCL kernels run under the backward kernels (session 52).
Interview questions
What is the difference between all-reduce, reduce-scatter and all-gather?basic
Explain ring all-reduce and derive its cost.core
Why is the ring bandwidth-optimal? Why not always use it?advanced
An 8-GPU node all-reduces 1 GB in 5 ms. What are algbw and busbw, and is this good?core
Why does ZeRO-3 / FSDP communicate 1.5 times as much as DDP?core
Compare NVLink, PCIe, InfiniBand and Ethernet for training.basic
How does DDP overlap communication with the backward pass?core
How do you choose the bucket size?advanced
Your 64-GPU job is much slower per GPU than the 8-GPU job. What do you check?advanced
NCCL_DEBUG=INFO for the topology (is it using InfiniBand or falling back to TCP sockets? GPUDirect RDMA?). Look for one slow node or link, since a ring runs at its slowest link. In a profiler, check that NCCL kernels overlap with compute. Fixes: hierarchical or sharded schemes, larger per-GPU batch (more compute per byte), better bucketing, or moving a parallel dimension inside the server.What is all-to-all, and why is it hard for mixture-of-experts models?advanced
Exercises
- In Figure 2’s ring with \(N = 4\), how many chunks does each GPU send in total, and what fraction of \(M\) is that? Repeat for \(N = 8\).
- Using (43.4) with \(\alpha = 0\): how long does an all-reduce of 2 GB take on 8 GPUs over PCIe Gen5 (63 GB/s)? And on NVLink 4 (450 GB/s)?
- With \(\alpha = 5\) µs and \(\beta = 50\) GB/s, at what buffer size \(M\) is the ring’s latency term equal to its bandwidth term for \(N = 64\)?
- nccl-tests reports a reduce-scatter on 16 GPUs with algbw 40 GB/s. What is the busbw?
- A ZeRO-3 job with 70B parameters in BF16 runs on 64 GPUs. How many bytes does each GPU send per step for weights and gradients?
- Show that running a reduce-scatter and then an all-gather costs exactly (43.4).
Answerscheck
Key takeaways
- Six collectives cover nearly all training traffic: broadcast, reduce, all-reduce, reduce-scatter, all-gather and all-to-all. All-reduce = reduce-scatter + all-gather.
- Message time is \(\alpha + n/\beta\) (43.1). The ring all-reduce costs \(2(N-1)\alpha + 2\frac{N-1}{N}\frac{M}{\beta}\) (43.4): each GPU sends about \(2M\), whatever \(N\) is, which is optimal.
- For small messages and many GPUs, latency dominates and trees (43.5) or NVSwitch reductions win. Measure with nccl-tests and compare busbw (43.6) with the one-direction link speed.
- Links form a hierarchy: NVLink (450 GB/s per direction on H100) inside a server, PCIe (63 GB/s), InfiniBand or RoCE (50 GB/s per 400 Gb/s port) between servers. Hierarchical all-reduce (43.7) keeps most bytes on the fast links.
- DDP sends \(2\Psi\) per GPU per step, ZeRO-3 and FSDP \(3\Psi\); tensor parallelism all-reduces activations; MoE uses all-to-all.
- Bucketing and async collectives hide communication behind the backward pass (43.8), as long as it is shorter than the backward pass.
Key formulas
References for this session
- Hugging Face (Nanotron team) (2025). The Ultra-Scale Playbook: Training LLMs on GPU Clusters
- Austin et al., Google DeepMind (2025). How to Scale Your Model
- Hugging Face (Nanotron team) (2025). The Ultra-Scale Playbook: Training LLMs on GPU Clusters
- Austin et al., Google DeepMind (2025). How to Scale Your Model
- NVIDIA (docs). nccl-tests: Performance reported by NCCL tests (algbw and busbw)
- NVIDIA (docs). NCCL User Guide: Collective Operations and Environment Variables
- Patarasuk and Yuan (2009). Bandwidth optimal all-reduce algorithms for clusters of workstations
- Thakur, Rabenseifner and Gropp (2005). Optimization of Collective Communication Operations in MPICH
- Sergeev and Del Balso (2018). Horovod: fast and easy distributed deep learning in TensorFlow
- Li et al. (2020). PyTorch Distributed: Experiences on Accelerating Data Parallel Training
- Rajbhandari et al. (2019). ZeRO: Memory Optimizations Toward Training Trillion Parameter Models
- Zhao et al. (2023). PyTorch FSDP: Experiences on Scaling Fully Sharded Data Parallel
- Shoeybi et al. (2019). Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism
- Fedus et al. (2021). Switch Transformers
- Liu et al. (2023). Ring Attention with Blockwise Transformers for Near-Infinite Context
- NVIDIA (web). NVLink and NVLink Switch