All-Reduce and Distributed Training Collectives

To train faster, split a large batch across many GPUs — each one computes the gradient on its own slice of the data. But those separate gradients are only useful if they get combined back into one shared update, applied identically everywhere, so every GPU's copy of the model stays in sync. The naive way to combine them — send every GPU's gradient to one central machine, have it average them, and send the result back out — creates an obvious bottleneck: that one central machine has to receive from, and send to, every other machine, and its network link becomes the limiting factor no matter how many GPUs you add.

The analogy: passing notes around a circle instead of to one hub

Picture 8 people each holding a slip of paper with a number, needing everyone to end up knowing the sum of all 8. One way: everyone runs to a person in the middle, hands over their slip, that person adds everything up and runs a copy back to each of the 8 — that middle person does 8 times the work of anyone else and becomes the bottleneck. A cleverer way: arrange everyone in a circle, and have each person pass a running partial sum to their neighbor, who adds their own number and passes it on; after going around the circle, everyone ends up with the full sum, having only talked to their immediate neighbors, with no one doing disproportionate work. That circular passing pattern is the essence of a ring all-reduce.

What all-reduce actually does

All-reduce is a communication pattern where every participant contributes a value (here, its locally computed gradient), and every participant ends up with the combined result (typically the sum or average across all participants) — without any single node needing to see or process the whole thing alone.

$$g_{\text{combined}} = \frac{1}{N}\sum_{i=1}^{N} g_i$$

In words: the combined gradient is the average of each of the $N$ workers' own locally computed gradient $g_i$. The ring all-reduce algorithm achieves this by splitting each worker's gradient into $N$ chunks and passing chunks around the ring in two phases — a "reduce-scatter" phase where each worker ends up holding the fully-summed version of one chunk, followed by an "all-gather" phase where those summed chunks circulate once more so every worker ends up with every summed chunk. Each worker only ever sends and receives data to and from its two ring neighbors, and the total data moved per worker stays roughly constant regardless of how many workers $N$ join the ring — the key property that keeps it from bottlenecking as you scale up.

Worked example 1: naive central-hub cost

4 workers, each holding a gradient of size 1 unit of data. Central-hub approach: the hub receives 4 units in (one from each worker) and sends 4 units back out — 8 units of traffic through that one machine's network link. Scale to 100 workers: the hub now handles $100+100=200$ units through a single link — the hub's bandwidth becomes the hard ceiling on how fast this step can go, no matter how fast the other 99 machines are.

Worked example 2: ring all-reduce cost

Same 4 workers, gradient split into 4 chunks of size $0.25$ each. In ring all-reduce, each worker sends and receives roughly $2\times\frac{N-1}{N}$ times its own data over the whole process — for $N=4$: $2 \times 0.75 = 1.5$ units of data moved per worker, spread across its two ring neighbor links, not through any single bottleneck node. As $N$ grows to 100, that per-worker factor approaches $2 \times \frac{99}{100} \approx 1.98$ — it barely increases at all, since it's bounded by 2 regardless of how many workers join, versus the central-hub approach's cost per worker link staying fixed at 2 but the hub's own total traffic growing linearly with $N$ and becoming the bottleneck.

What this means in practice

All-reduce (ring-based or hierarchical variants tuned to a cluster's network topology) underlies essentially every large-scale distributed training job, implemented in libraries like NCCL, Horovod, and PyTorch's distributed package. Choosing the right collective algorithm, and overlapping communication with computation so GPUs aren't idle waiting on the network, separates a run that scales efficiently across hundreds of GPUs from one that barely speeds up past a handful.

Practice

1. With 16 workers on a central hub, how much total traffic (in and out combined, per unit gradient size) does the hub handle?
2. Why does per-worker ring all-reduce cost approach a constant (roughly 2 units) rather than growing with $N$?
3. Name one reason communication and computation being overlapped in time matters for total training speed.