Ring AllReduce cost models

Assume p ranks, an equal per-rank input of n bytes, and a datatype-element partition into p equal chunks. A ring reduce-scatter uses p−1 steps: ranks exchange chunks with neighbors and accumulate contributions so each finishes with a different reduced chunk. A subsequent allgather circulates those completed chunks for another p−1 steps. The full tensor is returned to every rank. Different ring schedules can assign chunk ownership differently; the semantic result is independent of the chosen logical neighbor numbering under compatible reduction rules.

Each rank sends one chunk per step in this simplified schedule. The data volume sent per rank over both phases is therefore 2(p−1)n/p, with the same received volume under the symmetric model. State whether a reported volume counts sends alone, send plus receive, or link-hop traffic. Doubling a send-only volume while comparing with a full-duplex directional bandwidth can count the same cost incorrectly. Real implementations can pipeline and use multiple channels or protocol variants, and local GPU reduction work can add another resource bottleneck.

Let one step cost a fixed startup alpha plus chunk bytes times beta, where beta is seconds per byte. Multiplying by the two phase lengths gives the standard simple ring model. It assumes symmetric effective neighbor performance, full-duplex progress without extra send/receive serialization, and no overlapping contention that changes the coefficients. GPU memory reads, local reduction arithmetic, synchronization, protocol overhead, and topology routing can add costs. The formula is an explanatory baseline and should be compared with measurements rather than fitted until every unexplained delay disappears into bandwidth.

For fixed n, the bandwidth term approaches twice the input size divided by effective bandwidth as p grows; it does not shrink to zero. The startup term grows linearly with p. That is why a tiny scalar reduction can favor a lower-step algorithm even when a ring moves large tensors efficiently. Fusing small tensors can reduce repeated startup, but delaying their communication can also reduce overlap with backward computation. Choose bucket boundaries using both the collective model and the training dependency timeline.

The ring is a logical communication order mapped onto physical devices and links. A simple rank-number sequence can cross a slow inter-node link repeatedly or concentrate traffic on one rail. A topology-aware implementation may choose another rank order, multiple rings, or another collective algorithm altogether. Record the library version and selected topology when testing a model. The historical MPICH algorithm analysis cited here explains latency-bandwidth tradeoffs; its hardware results are not specifications for a contemporary accelerator fabric.

The modular lab illustrates cycle coverage only. Reset, set both modulus m=8 and additive step a=1, predict a period of eight residues, then Play or Step. Separately Reset, set both m=8 and a=2, predict period four, then Play or Step. The second orbit visits only half the residues. This exact addition-modulo model does not exchange tensors or execute ring AllReduce; it helps explain why a neighbor scheme must include the full intended participant set. A short arithmetic cycle is not a faster valid substitute for an eight-rank operation.