Ring all-reduce has a genuinely rare property for a systems algorithm: there is a proof that no algorithm can move less data. Patarasuk and Yuan showed in 2009 that to all-reduce X items across N processes, at least one process must communicate at least ⌈2·(N−1)/N·X⌉ items — and the ring hits that floor exactly. Baidu built a library around it, Horovod built a product around it, and for a while "bandwidth-optimal" was treated as the end of the conversation.

Then NVIDIA ran it on Summit at 24,576 GPUs and reported latency improvements of up to 180x — by switching away from the ring. The catch was never in the bandwidth term. It was in the other term of the cost model, the one the optimality proof explicitly does not cover.

What the proof actually says

The Patarasuk–Yuan result works in the standard model where sending a message costs a fixed per-message latency plus a per-byte transfer time. Their Lemma 3 establishes that a one-item all-reduce over N processes requires at least 2×(N−1) partial results to cross the wire in total, assuming the reduce operator is associative and commutative. Spread an X-item operation perfectly across N processes and you get Lemma 4: some process must send and receive at least ⌈2·(N−1)/N·X⌉ items — assuming data isn't compressed and the inputs are independent. In the linear communication model, the paper notes, this means the best any all-reduce can do is roughly 2× the time to send the buffer once.

The paper is equally explicit about what it does not claim. The ring-based algorithm "is only optimal in the bandwidth term, but not the latency term: the number of communication rounds is proportional to the number of processes." The butterfly-style recursive halving/doubling algorithm is actually optimal in both terms — minimum rounds and minimum bytes — but its communication pattern causes network contention on SMP/multi-core clusters, which is precisely why the authors proposed the ring: it needs only tree connectivity to stay contention-free, works for non-power-of-two process counts, and uses less working memory.

How the ring hits the floor

The mechanics, as Baidu's write-up lays them out: arrange N GPUs in a logical ring, split the gradient buffer into N chunks, and run two phases of N−1 steps each.

  1. Scatter-reduce: each step, every GPU sends one chunk to its right neighbor and receives one from its left, adding the received values into its local copy. After N−1 steps, each GPU holds one chunk that is fully summed.
  2. All-gather: same ring, same N−1 steps, but received chunks now overwrite instead of accumulate, circulating the finished chunks until everyone has all of them.

Each GPU moves K/N values per step across 2(N−1) steps:

text
data transferred per GPU = 2 · (N−1)/N · K   ≈ 2K for large N

That matches the lower bound — and, crucially, it barely grows with N. Baidu's worked example: a 300M-parameter model is about 1.2 GB of gradients. A naive single-reducer design at 1 GB/s costs about 1.2 s of communication per iteration on 2 GPUs and 10.8 s on 10, because the reducer's link is the bottleneck and its load grows linearly. The ring moves ~2.4 GB per GPU whether there are 4 GPUs or 400, bounded by the slowest neighbor-to-neighbor link — about 400 ms at 6 GB/s InfiniBand, before overlapping communication with backprop (which helps, because output-layer gradients are ready first and can start reducing while earlier layers are still computing).

This is why the technique took over distributed training. Baidu's Deep Speech models had grown from roughly 11 million parameters in 2014 to around 100 million a year later; they shipped baidu-allreduce as an embeddable C library, and Uber's Horovod implemented the same technique.

The bill for 2(N−1) rounds

Here is the tradeoff in one sentence: the ring's bytes per GPU are constant in N, but its round count is 2(N−1), so per-message latency — which the bandwidth proof treats as a separate term — gets multiplied by the cluster size.

At 8 GPUs nobody notices. At thousands of ranks, with gradient buckets that aren't enormous, those serialized hops dominate. NVIDIA's NCCL 2.4 announcement states it directly: with rings, "latency scales linearly with the number of GPUs, preventing scaling above hundreds of GPUs."

NCCL's first mitigation was hierarchical 2D rings — reduce-scatter inside each node, all-reduce across nodes, all-gather inside each node — which shortens the rings but, per NVIDIA's own ResNet-50 comparison, yields an advantage over flat rings that stays constant as the cluster grows. The latency is still linear in the number of nodes; only the constant shrank.

Double binary trees: full bandwidth, log rounds

NCCL 2.4 adopted the double binary tree construction from Sanders, Speck, and Träff's 2009 MPI work. A single binary tree gives logarithmic depth but wastes bandwidth: leaves only inject data, inner nodes do the forwarding, so roughly half the ranks' outbound links sit idle during a reduce.

The fix is to run two trees at once, each carrying half the data. In any binary tree, half or fewer of the ranks are inner nodes and half or more are leaves — so build a second tree with the roles flipped, leaves becoming inner nodes and vice versa. NCCL builds the first tree with a power-of-two pattern that maximizes locality; in the resulting pair, at most one rank is a leaf in both trees and no rank is an inner node in both. Superimpose them and every rank has two parents and two children (the roots have one of each). Each rank receives at most half the data twice and sends at most half the data twice — the same total traffic as the ring, but in O(log N) rounds instead of O(N).

On Summit, NVIDIA measured all-reduce at up to 24,576 GPUs and reported latency improvements of up to 180x over rings at 24k GPUs, with the gap widening as scale grows. Trees aren't free of fine print: the blog notes bus bandwidth degrades somewhat when traffic crosses L3 switches in the InfiniBand fabric — an interaction between the tree's communication pattern and InfiniBand routing — and NCCL automatically falls back to rings when rings deliver more bandwidth for the message at hand.

What NCCL actually picks today

The algorithm zoo has kept growing. NCCL_ALGO accepts Ring and Tree (since 2.5), CollnetChain and CollnetDirect (2.14+), NVLS (2.17+, NVLink SHARP offload), NVLSTree (2.18+), and PAT (2.23+). The default is unset: NCCL selects per operation "based on the node topology and architecture" — in practice, trees cover latency-sensitive regimes and rings cover bandwidth-bound ones. Since 2.24, Ring is no longer even an implicit fallback when you override the list. There's also a protocol axis (NCCL_PROTO: LL, LL128, Simple) that the docs explicitly discourage touching, with a warning that forcing LL128 on unsupported platforms can corrupt data.

The engineering takeaway travels beyond collectives. "Provably optimal" is always optimal in a stated term of a stated model. Ring all-reduce really does meet a tight lower bound on bytes moved, and that bound really did make 10-GPU training practical at full bandwidth. The same algorithm is also linear-latency by construction, and at 24k GPUs that unpriced term is worth 180x. When someone hands you an optimality proof, the most useful question is not whether the proof is right — it's which term of the cost model it is silent about.

References

allreducenccldistributed-trainingcollective-communicationgpu