Dataflow, executed · 03
Ring all-reduce: the bytes per rank don't grow
Collectives
The picture everyone draws is a circle with four boxes and arrows going round, and it leaves you with the impression that all-reduce gets more expensive as you add GPUs. Half of that is exactly backwards.
Per rank, a ring all-reduce moves
2(N−1)/N times the buffer. That is under
2D for every ring size there has ever been — 1.5D at four
ranks, 1.97D at sixty-four — and it never reaches 2D. Adding ranks
does not cost bytes.
It is bandwidth-optimal, and no arrangement of sends can do
better: every rank must at minimum ship its data out once and take the
answer back once. The ring hits that floor almost exactly, and the
2(N−1)/N approaches 2 from below as the ring grows,
which is the whole trick — the fraction gets closer to the bound but
never crosses it.
What the circle diagram hides
A static circle with arrows draws the topology and hides the schedule. It has no time axis, so it cannot show you the one thing that makes the algorithm work: which chunk each rank sends on each step, chosen so that what arrives is always the chunk the receiver is itself accumulating. Get that rotation wrong and the picture looks identical while the answer is garbage.
The exchange runs in two phases of N−1 steps each.
Reduce-scatter sends partial sums round until each rank
owns exactly one finished chunk — rank r ends up holding the
complete total for chunk r and nobody else's.
All-gather then walks those finished chunks round the
same ring until everyone has all of them. Six steps at four ranks, and
each is strictly serial: nothing in step 4 can start before step 3
lands.
The cost that doesn't grow, and the one that does
The useful contrast is the naive alternative: if every rank simply sent
its whole buffer to every peer, each would move (N−1)D.
Three times the buffer at four ranks, sixty-three times at sixty-four.
That is the cost that explodes, and avoiding it is the entire
reason the ring exists.
| Quantity | Rule | N = 4 | N = 64 |
|---|---|---|---|
| Ring bytes per rank | 2(N−1)/N | 1.50D | 1.97D |
| Naive bytes per rank | N−1 | 3D | 63D |
| Serial steps | 2(N−1) | 6 | 126 |
| Chunk-sends in the run | N × 2(N−1) | 24 | — |
Read the last two rows together and the real trade shows up. Bandwidth per rank is flat — 1.50D to 1.97D across a sixteen-fold increase in ring size. Round trips go from 6 to 126. A big ring is not a bandwidth problem; it is a latency problem, and that is why hierarchical and tree-shaped collectives exist at all. They spend bandwidth to buy back depth.
Nothing here is drawn
The exchange is executed before a frame is placed, and the module refuses to import unless every rank finishes holding the true elementwise sum — not merely the rank the camera happens to follow. The byte counts are then counted from the send log rather than printed from the formula, so a broken schedule cannot quietly agree with the arithmetic on screen, and the closed form is checked against every ring size from 2 to 64.
git clone https://github.com/SciMigo/straightedge
cd straightedge && python3 -m pip install -e '.[render]'
cd examples/ring_allreduce && manim -qm scene.py RingAllReduceChange the number of ranks or what each contributes and the chunk rotation, the colours, the counter and the totals all follow. The one thing you cannot do is make it show a rank finishing with the wrong sum.
A note on what the picture had to lose
Four ranks is small enough to read and too small to make the point. The interesting regime is the one you cannot animate: at sixty-four ranks the per-rank traffic has barely moved while the step count has grown twenty-one-fold, and that divergence is the actual result. A four-rank ring shows you the mechanism honestly and the asymptotics not at all, which is why the table above exists and why it is checked to 64 rather than to 4. Worth stating rather than hiding: a simplification you cannot see is indistinguishable from an error.