The Cost of Collective Communication

The alpha–beta model, and why a ring all-reduce moves a bounded amount of data per node no matter how many nodes there are.

AI SystemsGraduate⏱ 3 hours7 min readall-reducering algorithmbandwidthlatencycollectives

AssumesScaling Limits — Amdahl, Gustafson and the Coherency Penalty · Inference Arithmetic and the Roofline

The cost model

DefinitionThe alpha–beta cost model

Sending a message of $n$ bytes between two nodes takes

T(n) \;=\; \alpha \;+\; \frac n B ,

where $\alpha$ is the per-message startup latency (microseconds: software stack, wire propagation) and $B$ is the achievable bandwidth in bytes per second. Nodes are assumed able to send and receive simultaneously, and disjoint pairs communicate without interference.

Assumptions

The model ignores topology, congestion and contention for shared switches. It is accurate for a dedicated fabric where the communication pattern respects the topology — which is precisely why collective implementations are written to match the wiring. It is a poor model for an oversubscribed datacentre network, where the effective $B$ depends on what everyone else is doing.

The baseline

PropositionCost of a centralised all-reduce

Let $p$ nodes each hold an $N$ -byte vector, and let all $p$ end up holding the element-wise sum. If all nodes send to a designated root, which reduces and broadcasts the result back, the time is at least

T_{\text{central}} \;=\; 2\,(p-1)\left(\alpha + \frac N B\right)

when the root's link is serialised, growing linearly in $p$ .

The ring

TheoremCost of the ring all-reduce

Arrange the $p$ nodes in a ring and split each node's $N$ -byte vector into $p$ chunks of $N/p$ bytes. Then all-reduce can be performed as a reduce-scatter followed by an all-gather, each taking $p-1$ steps in which every node sends one chunk to its successor. The total cost is

T_{\text{ring}} \;=\; 2\,(p-1)\,\alpha \;+\; \frac{2(p-1)}{p}\cdot\frac N B .

In particular the bandwidth term is bounded by $2N/B$ for every $p$ , and increases to that limit rather than growing with $p$ .

Key idea

The bandwidth term of a ring all-reduce is essentially independent of the cluster size: it is $2N/B$ at $p=8$ to within 12%, and at $p=512$ to within 0.4%. The price is the latency term, which grows as $2(p-1)\alpha$ . So the ring is the right algorithm for large gradients and the wrong one for small, frequent messages — which is exactly the split observed in practice between data-parallel gradient synchronisation and tensor-parallel activation exchange.

Is the ring optimal?

PropositionA bandwidth lower bound for all-reduce

In any all-reduce over $p$ nodes where the result depends non-trivially on every input, each node must receive at least $\frac{p-1}{p}N$ bytes. Hence no algorithm has a per-node bandwidth term below $\frac{p-1}{p}\cdot\frac{N}{B}$ , and the ring's $\frac{2(p-1)}{p}\cdot\frac NB$ is within a factor of $2$ of optimal.

What this does not say

The factor of two is real and is not an artefact: the ring performs a reduce-scatter and an all-gather, and each separately meets the $\frac{p-1}{p}N$ bound. An all-reduce is genuinely two collectives' worth of traffic. Implementations that appear to beat this are either overlapping communication with computation — which hides the cost rather than removing it — or reducing $N$ , by gradient compression or lower precision, which changes the problem.

Choosing an algorithm by message size

CorollaryWhich term dominates

Compare the ring, costing $2(p-1)\alpha + \frac{2(p-1)}{p}\frac NB$ , with a recursive halving-and-doubling scheme costing $2\log_2 p\,\cdot\alpha + \frac{2(p-1)}{p}\frac NB$ for power-of-two $p$ . The two have the same bandwidth term, so the comparison is entirely in latency and the logarithmic scheme wins for every $p > 2$ . Against a latency-optimal scheme, the ring is preferable only when

\frac NB \;\gtrsim\; \frac{p\,\alpha}{1} ,

that is, once the transfer time of the message exceeds roughly $p$ startup latencies.

References

PaperR. Thakur, R. Rabenseifner, W. Gropp (2005). Optimization of Collective Communication Operations in MPICHSource of the recursive-halving/doubling and ring cost analyses used here.
PaperP. Patarasuk, X. Yuan (2009). Bandwidth Optimal All-reduce Algorithms for Clusters of WorkstationsEstablishes the bandwidth optimality of the ring algorithm.

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

DefinitionThe alpha–beta cost modelTransferring n bytes costs a fixed startup latency plus n divided by bandwidth.
PropositionCost of a centralised all-reduceproof includedGathering at one root and broadcasting back moves (p−1)N bytes across the root's link, so its time grows linearly in the node count.
TheoremCost of the ring all-reduceproof includedReduce-scatter followed by all-gather moves 2(p−1)N/p bytes per node, which is below 2N for every p, while incurring 2(p−1) latency terms.
PropositionA bandwidth lower bound for all-reduceproof includedEvery node must receive at least N(p−1)/p bytes of information, so no algorithm beats the ring's bandwidth term by more than a factor of two.
CorollaryWhich term dominatesproof includedThe ring is bandwidth-optimal for large messages and latency-suboptimal for small ones, with the crossover at a message size proportional to alpha times bandwidth.