Collective Communication Algorithms
Libraries implement each collective with several internal algorithms and switch between them by message size, process count, and topology.
One interface, many schedules
A collective such as allreduce or broadcast is a specification, not an algorithm. Beneath the single call, an MPI library holds a menu of schedules and picks one at runtime. The choice is governed by a simple cost model, usually the latency-bandwidth (alpha-beta) model: time to move n bytes over one link is approximately alpha + n*beta, where alpha is per-message latency and beta is per-byte transfer time.
The workhorse schedules
- Binomial tree: log2(P) steps, latency-optimal, best for small messages (broadcast, reduce).
- Recursive doubling: log2(P) steps, pairs across growing strides, small-message allreduce and allgather.
- Ring: P-1 steps but bandwidth-optimal, best for large messages (ring allreduce, allgather).
- Bruck: logarithmic steps for all-to-all of small messages via index rotation and local shuffling.
- Pipelined tree: segments a large message so links stay saturated.
The size crossover
For small messages latency dominates, so minimizing the number of steps (log P) wins even if each step is short. For large messages bandwidth dominates, so minimizing the total bytes each link carries wins even if that takes more steps. Ring allreduce, for example, moves only about 2n bytes per link regardless of P, which beats a tree once messages are large. Tuned libraries store crossover thresholds, sometimes auto-tuned per machine.
Topology and hardware offload
On a fat-tree or dragonfly network, mapping the logical schedule onto physical links to avoid contention matters as much as the schedule itself. Some interconnects offer in-network computation, performing reduction inside switches so a small allreduce completes without the data ever returning to host memory. Hardware collectives can cut latency-bound reductions substantially.
Understanding these building blocks explains why the same allreduce call can be fast at one message size and slow at another, and why picking process counts that are powers of two sometimes helps latency-bound collectives.