Derive the cost of a ring all-reduce. Why is it bandwidth-optimal, and where does it stop scaling?

TL;DR: Split an S-byte buffer into n equal chunks. Reduce-scatter takes n−1 rounds and all-gather takes another n−1; each rank sends one S/n-byte chunk per round. The send count is 2(n−1)S/n, with the same amount received. If every rank has the same usable bandwidth, the ring shares the required reduction and result-distribution traffic evenly. The weak point is the 2(n−1)α startup term, especially when chunks are small.

How to approach it

State what all-reduce must produce, trace one chunk around four ranks, and count chunks rather than memorizing a factor. Separate the bandwidth bound from the latency model. Explain the assumptions behind “optimal” before comparing it with a tree or a hardware-assisted reduction.

A strong answer

Four workers hold different vectors, and every worker needs the elementwise sum. Put them in a logical ring, with each worker sending clockwise and receiving counterclockwise. Divide each vector into four equally sized chunks, A through D.

For chunk A, suppose ranks 0, 1, 2 and 3 contribute 1, 2, 4 and 8. The reduction path is:

That is three rounds. The other chunks travel on rotated paths simultaneously, leaving one complete chunk on each rank. All-gather then copies each completed chunk around the ring for three more rounds. Chunk A travels from rank 3 to rank 0, then rank 1, then rank 2. No additions occur during that second phase.

If rank i initially sends chunk i, the completed chunk after reduction is chunk (i+1) mod n on rank i under this schedule. Different ring indexing conventions can rename the ownership. Trace it instead of mixing formulas from different schedules.

For n ranks and S bytes, the calculation is:

Every rank receives the same volume. For n=4 and S=128 MiB, each chunk is 32 MiB: each phase sends 96 MiB per rank, for 192 MiB total. For n=1, the expression gives zero communication, as it should.

What “bandwidth-optimal” assumes. In the standard point-to-point reduction/dissemination model, combining n contributions requires n−1 transfers of partial values per element, and distributing the completed result requires another n−1. Across the group, that is 2(n−1)S bytes. With n equal-bandwidth endpoints, the maximum endpoint load cannot be below the average 2(n−1)S/n. The ring balances that load.

This is not a proof that each individual rank in any algorithm must receive that amount. A tree can distribute work unevenly. The argument also assumes ordinary endpoint transfers without compression or network-side arithmetic; switches that reduce values change the model. Ring vs Tree All-Reduce expands those distinctions.

Let B be usable send bandwidth in bytes per second, with receiving proceeding concurrently, and α an effective startup time per logical round:

T_ring ≈ 2(n−1)α + 2(n−1)S/(nB)

Do not insert a bidirectional aggregate as B. Also, α is not automatically a ping round-trip time. Software, device scheduling and the communication protocol contribute to the effective startup behavior.

Use a hypothetical B=16 GiB/s and α=5 microseconds:

These calculations isolate the mechanism; they are not hardware benchmarks. At n=64, reducing the buffer 128× leaves the 126-round startup term intact. This is why “bytes per rank barely grow” does not establish good small-message scaling.

Equate the two terms to find where this ring model balances: S/n = αB. Here αB is approximately 83.9 KiB per chunk. It depends on the assumed startup and bandwidth; it is not a universal threshold at which NCCL switches algorithms.

A balanced tree can reduce and broadcast through a number of dependent stages that grows logarithmically with the rank count. Its bandwidth term depends on fan-out, pipelining and placement. Complementary double trees distribute interior-node work, making short dependency depth compatible with high bandwidth. Hardware-assisted algorithms introduce more possibilities. None of these observations guarantees which option wins on a particular machine.

The nccl-tests performance guide reports algorithm bandwidth S/t and normalizes all-reduce bus bandwidth by 2(n−1)/n. That normalized value is not a measurement of one physical NIC port.

Start with the library's default selection and measure matching message sizes and rank placement using nccl-tests. If small-message time grows with rank count while bytes barely change, compare the startup-sensitive alternatives. Test overrides such as NCCL_ALGO in a controlled experiment, retaining correctness checks and the end-to-end training measurement. A global setting can help one size range and hurt another.

What interviewers probe next

• Why does reduce-scatter cost half here? It is one of the ring's two equal-volume phases. Whether an application can stop there depends on which rank needs which output shard.
• Does a logical ring imply one physical link per rank? No. Logical edges may traverse several links, and multiple logical transfers may share a NIC or switch path. B must reflect the effective bottleneck.
• Can you add all bucket estimates to the training step? Not as exposed time: some reductions overlap computation. Count bytes for transport demand, then inspect dependencies for wall time.
• Will different algorithms give identical floating-point sums? Not necessarily. Reduction order changes rounding; compare results with a justified tolerance and check the application's numerical requirements.

Common mistakes

• Counting S bytes per round instead of S/n.
• Adding partial values again during all-gather.
• Claiming every rank in every algorithm has the ring's byte lower bound.
• Treating a one-direction bandwidth estimate as a benchmark or universal algorithm decision.

Key takeaways

• Two phases × n−1 rounds × S/n bytes gives 2(n−1)S/n sent per rank.
• Four ranks reducing 128 MiB send 192 MiB each; the buffer itself is still 128 MiB.
• The balance S/n = αB belongs to a stated ring model, not a fixed library threshold.