LLM & VLM courseBlog
43Track 3: Pretraining and scale · session 13 of 22

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.

Time: 3 to 4 hours (reading 2 hours, exercises 1 to 2 hours)Level: IntermediateBefore this: Sessions 38 and 42 (memory math for training, GPU architecture for ML)

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.

CollectiveInput on each rankOutput on each rankTypical use in training
Broadcastrank 0 has \(x\)everyone has \(x\)send the initial weights from rank 0 to all ranks
Reducerank \(r\) has \(x_r\)rank 0 has \(\sum_r x_r\)sum a metric on one rank for logging
All-reducerank \(r\) has \(x_r\)everyone has \(\sum_r x_r\)average gradients in data parallelism; tensor-parallel layers
Reduce-scatterrank \(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-gatherrank \(r\) has chunk \(r\)everyone has all \(N\) chunksgather sharded weights in ZeRO-3 and FSDP; sequence parallelism
All-to-allrank \(r\) has \(N\) chunks, one for each rankrank \(r\) has chunk \(r\) from every ranksend 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.

original data of this rankreduced (summed) datadata copied from another rankempty or not needed
Figure 1. The six collectives on four GPUs. Left: what each rank holds before. Right: what it holds after. Colors show where each value came from.
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.

  1. 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\).
  2. 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.

  1. input: \(x\) split into chunks \(x[0..N-1]\); right neighbour \(r+1 \bmod N\)
  2. for \(s = 0, \dots, N-2\) // reduce-scatter
  3. send \(x[(r-1-s) \bmod N]\) to the right
  4. \(x[c] \leftarrow x[c] + \text{received}\) // add
  5. // now \(x[r]\) is the full sum of chunk \(r\)
  6. for \(s = 0, \dots, N-2\) // all-gather
  7. send \(x[(r-s) \bmod N]\) to the right
  8. \(x[c] \leftarrow \text{received}\) // copy
  9. return \(x\) // the same sum on every GPU
own original valuepartial sum (some ranks added)final sum of all ranks
Figure 2. Ring all-reduce computed live on \(N\) GPUs (4 by default). The first \(N-1\) ring steps are the reduce-scatter phase (orange packets carry partial sums); the next \(N-1\) are the all-gather phase (green packets carry finished sums). Each ring step is shown as two moves: the send, then the add or copy. The dots inside a box count how many ranks have been added into that value. The small ring repeats the same messages on the links, and the bars show the bytes sent by each GPU. Times assume \(\alpha = 5\) µs and \(\beta = 450\) GB/s (NVLink 4, one direction).
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\).

Algorithm 1: ring all-reduce on rank \(r\) of \(N\)
  1. 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\)
  2. for \(s = 0, \dots, N-2\) // reduce-scatter phase
  3.   send \(x[(r - 1 - s) \bmod N]\) to the right; receive chunk \(c = (r - 2 - s) \bmod N\) from the left
  4.   \(x[c] \leftarrow x[c] + \text{received}\) // one more rank added into this partial sum
  5. // now \(x[r]\) is the full sum over all ranks
  6. for \(s = 0, \dots, N-2\) // all-gather phase
  7.   send \(x[(r - s) \bmod N]\) to the right; receive chunk \(c = (r - 1 - s) \bmod N\) from the left
  8.   \(x[c] \leftarrow \text{received}\) // copy, no addition
  9. 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

\[ T(n) = \alpha + \frac{n}{\beta} \tag{43.1} \]
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:

\[ T_{\text{RS}} = (N-1)\,\alpha + \frac{N-1}{N} \cdot \frac{M}{\beta} \tag{43.2} \]

The all-gather has the same pattern of steps and chunk sizes (only “add” becomes “copy”), so it costs the same:

\[ T_{\text{AG}} = (N-1)\,\alpha + \frac{N-1}{N} \cdot \frac{M}{\beta} \tag{43.3} \]

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:

\[ T_{\text{AR}} = 2(N-1)\,\alpha + \frac{2(N-1)}{N} \cdot \frac{M}{\beta} \tag{43.4} \]
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.

Worked example: all-reducing 16 GB of gradients

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

\[ T_{\text{tree}} \approx 2 \lceil \log_2 N \rceil\, \alpha + \frac{2M}{\beta} \tag{43.5} \]

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:

\[ \text{busbw}_{\text{AR}} = \frac{M}{t} \cdot \frac{2(N-1)}{N}, \qquad \text{busbw}_{\text{RS}} = \text{busbw}_{\text{AG}} = \frac{M}{t} \cdot \frac{N-1}{N} \tag{43.6} \]

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]

ring (43.4)tree (43.5)parameter server
Figure 3. Predicted all-reduce time from the alpha-beta model, on a log-log plot. The buttons set \(\beta\), the per-direction bandwidth in GB/s of each GPU’s slowest link. These are ideal link speeds; real collectives reach only part of them.
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]
Figure 4. The link hierarchy of a typical H100 cluster. Inside a server, every GPU reaches every other GPU through NVSwitch at 450 GB/s per direction. Between servers, GPU \(i\) of each server uses its own 50 GB/s InfiniBand port, and ports with the same index usually share a switch (a “rail”). [Likely] The step from NVLink to the network is about 9 times.

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:

  1. Reduce-scatter inside each server over NVLink: each GPU now holds the server’s sum of \(1/G\) of the buffer.
  2. 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.
  3. All-gather inside each server over NVLink.
\[ T_{\text{hier}} \approx \frac{2(G-1)}{G} \cdot \frac{M}{\beta_{\text{NVLink}}} + \frac{2(K-1)}{K} \cdot \frac{M/G}{\beta_{\text{net}}} \tag{43.7} \]

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).

  1. input: GPU \(g\) of server \(k\); \(x\) split into \(G\) chunks
  2. for \(s = 0, \dots, G-2\): send \(x[(g-1-s) \bmod G]\) to GPU \(g+1\) // NVLink
  3. \(x[c] \leftarrow x[c] + \text{received}\) // reduce-scatter
  4. send \(x[g]\) to GPU \(g\) of the other server; \(x[g] \leftarrow x[g] + \text{received}\) // network
  5. for \(s = 0, \dots, G-2\): send \(x[(g-s) \bmod G]\) to GPU \(g+1\) // NVLink
  6. \(x[c] \leftarrow \text{received}\) // all-gather
  7. return \(x\) // the sum over all \(KG\) GPUs
own valuepartial sumsent over the networkfinal sum of all 8 GPUs
Figure 5. Hierarchical all-reduce, computed live on 2 servers × 4 GPUs. Rows are GPUs, boxes are chunks, and the dots in a box count how many of the 8 GPUs have been added into it. Purple packets cross the network; all other packets stay on NVLink inside a server. Times use (43.7) with \(\beta_{\text{NVLink}} = 450\) GB/s, \(\beta_{\text{net}} = 50\) GB/s and no latency term.
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_ALGO can force Ring, Tree, NVLS, CollNet or PAT; NCCL_PROTO chooses LL, LL128 or Simple (the low-latency protocols are for small messages). Normally you leave both to NCCL’s tuner. [Certain]
  • Debugging. NCCL_DEBUG=INFO prints 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:

MethodCollectives per stepBytes 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 parallelismeach all-reduce becomes a reduce-scatter plus an all-gatherthe same bytes, but activations between them are split
Mixture of experts2 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 ringactivations 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:

\[ T_{\text{step}} \approx T_{\text{fwd}} + \max\big(T_{\text{bwd}},\ T_{\text{comm}}\big) + T_{\text{tail}} \tag{43.8} \]
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.

forwardbackwardbucket all-reduce
Figure 6. One data-parallel training step on 8 GPUs. A toy model with 24 layers: 5 ms forward and 10 ms backward per layer, 100 MB of BF16 gradients per layer (2.4 GB in total), produced in pieces of 25 MB. Each bucket’s all-reduce follows (43.4) with an assumed \(\alpha = 20\) µs. The numbers are a model, not a measurement.
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).

Algorithm 2: backward pass with bucketed, overlapped all-reduce (the idea behind DDP)
  1. before training: split the parameters into buckets of about \(B\) bytes, in reverse order of the forward pass
  2. for each parameter, register a hook that fires when its gradient is ready
  3. in the hook: mark the gradient ready; if all gradients of its bucket are ready then
  4.   launch all_reduce(bucket, async_op=True) on the communication stream // the backward pass keeps running
  5. after the backward pass: wait for all outstanding all-reduces
  6. divide each gradient by \(N\) // sum to average; often folded into the all-reduce
  7. 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

SettingCollectiveWhy
LLM pretraining with data parallelismall-reduce of gradients, bucketed and overlappedevery replica must apply the same update (session 44)
LLM pretraining with FSDP or ZeRO-3all-gather of weights, reduce-scatter of gradientseach GPU keeps only \(1/N\) of weights, gradients and optimizer state
Serving a 70B model on 8 GPUs with tensor parallelismall-reduce of activations, twice per layer, for every generated tokensmall messages, so latency (\(\alpha\)) and NVLink matter more than bandwidth [Likely]
Mixture-of-experts training and servingall-to-all to send tokens to experts and backexperts live on different GPUs (session 29)
Contrastive training of video–text retrieval models (CLIP-style)all-gather of embeddings from all GPUseach 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 contextpoint-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 predictionseach GPU scores a shard of the test set; the final accuracy needs all of them
Sharded video fingerprint or Video-RAG index searchall-gather of each shard’s top-k results, then a mergethe 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
All three start with one buffer per rank. All-reduce leaves every rank with the elementwise sum (or another reduction) of all buffers. Reduce-scatter computes the same sum but leaves rank \(r\) with only chunk \(r\) of it. All-gather starts with one chunk per rank and leaves every rank with all chunks concatenated. All-reduce = reduce-scatter followed by all-gather.
Explain ring all-reduce and derive its cost.core
Arrange \(N\) ranks in a ring and split the buffer into \(N\) chunks. In the reduce-scatter phase, in each of \(N-1\) steps, every rank sends one chunk to its right neighbour, which adds it; afterwards each rank owns one fully reduced chunk. In the all-gather phase, \(N-1\) more steps pass the finished chunks around. Each step moves \(M/N\) bytes per rank, all links in parallel, so \(T = 2(N-1)\alpha + 2\frac{N-1}{N}\frac{M}{\beta}\). The bandwidth term approaches \(2M/\beta\) and does not grow with \(N\).
Why is the ring bandwidth-optimal? Why not always use it?advanced
Every rank must send its data to be combined with all others, and must receive the result; a counting argument shows that each rank must send at least \(2\frac{N-1}{N}M\) bytes, which the ring achieves (Patarasuk and Yuan). But it has \(2(N-1)\) sequential steps, so its latency term grows linearly with \(N\). For small messages or very large \(N\), trees (\(\log N\) steps) or hierarchical schemes are faster. NCCL chooses per call.
An 8-GPU node all-reduces 1 GB in 5 ms. What are algbw and busbw, and is this good?core
algbw \(= 1\text{ GB} / 5\text{ ms} = 200\) GB/s. busbw \(= 200 \times 2 \cdot 7/8 = 350\) GB/s. On H100 NVLink (450 GB/s per direction) that is about 78% of the link speed, which is reasonable for a real collective; you would compare it with nccl-tests on the same machine.
Why does ZeRO-3 / FSDP communicate 1.5 times as much as DDP?core
DDP does one all-reduce of gradients per step, which is a reduce-scatter plus an all-gather: \(2\frac{N-1}{N}\Psi\) per GPU. ZeRO-3 keeps weights sharded, so it all-gathers them before the forward pass, all-gathers them again before the backward pass (they were freed in between to save memory), and reduce-scatters the gradients: three operations of \(\frac{N-1}{N}\Psi\) each. Three over two is 1.5.
Compare NVLink, PCIe, InfiniBand and Ethernet for training.basic
NVLink with NVSwitch connects GPUs inside a server: 450 GB/s per direction per H100, all pairs at once. PCIe Gen5 x16 is about 63 GB/s per direction and connects GPUs to CPUs and network cards. InfiniBand NDR (400 Gb/s = 50 GB/s per port, often one per GPU) and RoCE Ethernet connect servers, with RDMA and GPUDirect for low latency. The gap between in-server and between-server bandwidth (about 9 times on H100) is why parallelism is placed hierarchically: the most communication-heavy kind (tensor parallelism) stays inside a server.
How does DDP overlap communication with the backward pass?core
It groups gradients into buckets (25 MB by default) in reverse layer order and registers autograd hooks. When all gradients of a bucket are ready, it launches an asynchronous all-reduce for that bucket on a separate stream while the backward pass continues with earlier layers. Only the last bucket(s) remain after backward finishes. Overlap works only if total communication time is less than backward time, and it costs some SMs.
How do you choose the bucket size?advanced
Small buckets start communicating early and leave a short tail, but each pays the per-call latency \(2(N-1)\alpha\) and small messages reach lower bandwidth. Large buckets are efficient per byte but start late, and one giant bucket overlaps nothing. The best size depends on \(\alpha\), \(\beta\), \(N\) and the backward time per layer; the default of 25 MB is a reasonable middle, and you tune it by measuring step time in a profiler.
Your 64-GPU job is much slower per GPU than the 8-GPU job. What do you check?advanced
First estimate with (43.4) and (43.7): is communication now longer than the backward pass? Then run nccl-tests across nodes and compare busbw with the network spec. Check 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
In all-to-all, each rank sends a different chunk to every other rank (a distributed transpose). In MoE, each GPU sends each token to the GPU that holds its chosen expert and receives the results back: two all-to-alls per MoE layer in forward and two in backward. The chunk sizes depend on routing and are uneven, every pair of GPUs talks, and it crosses the network if experts span servers, so it is latency- and bisection-bandwidth-sensitive. Capacity limits, expert placement inside a server and overlap are the usual remedies.

Exercises

  1. 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\).
  2. 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)?
  3. 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\)?
  4. nccl-tests reports a reduce-scatter on 16 GPUs with algbw 40 GB/s. What is the busbw?
  5. 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?
  6. Show that running a reduce-scatter and then an all-gather costs exactly (43.4).
Answerscheck
1. \(2(N-1) = 6\) chunks of \(M/4\), so \(1.5M\). For \(N = 8\): 14 chunks of \(M/8\), so \(1.75M\). 2. Each GPU sends \(1.75 \times 2 = 3.5\) GB: \(3.5/63 = 56\) ms on PCIe, \(3.5/450 = 7.8\) ms on NVLink. 3. Latency term \(2 \cdot 63 \cdot 5\) µs \(= 630\) µs. Bandwidth term \(2 \cdot \tfrac{63}{64} M / \beta\); set equal: \(M = 630\text{ µs} \times 50\text{ GB/s} / 1.96875 = 16\) MB. Below about 16 MB the ring is mostly latency. 4. busbw \(= 40 \times 15/16 = 37.5\) GB/s. 5. \(\Psi = 140\) GB; \(3 \cdot \tfrac{63}{64} \cdot 140 = 413\) GB per GPU per step. 6. (43.2) plus (43.3) is \(2(N-1)\alpha + 2\frac{N-1}{N}\frac{M}{\beta}\), which is (43.4).

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

\[ T_{\text{AR}} = 2(N-1)\alpha + \frac{2(N-1)}{N}\frac{M}{\beta}, \qquad T_{\text{RS}} = T_{\text{AG}} = (N-1)\alpha + \frac{N-1}{N}\frac{M}{\beta} \]
\[ \text{busbw}_{\text{AR}} = \frac{M}{t}\cdot\frac{2(N-1)}{N}, \qquad T_{\text{step}} \approx T_{\text{fwd}} + \max(T_{\text{bwd}}, T_{\text{comm}}) + T_{\text{tail}} \]

References for this session

  1. Hugging Face (Nanotron team) (2025). The Ultra-Scale Playbook: Training LLMs on GPU Clusters
  2. Austin et al., Google DeepMind (2025). How to Scale Your Model
  3. Hugging Face (Nanotron team) (2025). The Ultra-Scale Playbook: Training LLMs on GPU Clusters
  4. Austin et al., Google DeepMind (2025). How to Scale Your Model
  5. NVIDIA (docs). nccl-tests: Performance reported by NCCL tests (algbw and busbw)
  6. NVIDIA (docs). NCCL User Guide: Collective Operations and Environment Variables
  7. Patarasuk and Yuan (2009). Bandwidth optimal all-reduce algorithms for clusters of workstations
  8. Thakur, Rabenseifner and Gropp (2005). Optimization of Collective Communication Operations in MPICH
  9. Sergeev and Del Balso (2018). Horovod: fast and easy distributed deep learning in TensorFlow
  10. Li et al. (2020). PyTorch Distributed: Experiences on Accelerating Data Parallel Training
  11. Rajbhandari et al. (2019). ZeRO: Memory Optimizations Toward Training Trillion Parameter Models
  12. Zhao et al. (2023). PyTorch FSDP: Experiences on Scaling Fully Sharded Data Parallel
  13. Shoeybi et al. (2019). Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism
  14. Fedus et al. (2021). Switch Transformers
  15. Liu et al. (2023). Ring Attention with Blockwise Transformers for Near-Infinite Context
  16. NVIDIA (web). NVLink and NVLink Switch