What an Allreduce Actually Moves: Trees, Rings, and the Cost Model

A global sum over one value per rank looks like the simplest operation in a parallel program. It is also the operation that decides whether a job scales past a few thousand cores, because every rank participates, every rank needs the answer, and the amount of data that must cross the network grows with the process count in a way that a naive implementation makes linear.

The interface is a single call, MPI_Allreduce, taking a send buffer, a receive buffer, a count, a datatype, an operation, and a communicator. What the call hides is a choice among algorithms whose costs differ by a factor of the process count in one term and by a factor of the logarithm in another. Understanding that choice explains both the performance cliffs at particular message sizes and the fact that the same reduction can produce slightly different floating-point results at different job sizes.

Reduce plus broadcast is the wrong decomposition

The obvious construction sends every rank’s contribution to rank zero, sums them there, and broadcasts the result. It is correct, and it is the design the interface implicitly rejects.

The gather phase has rank zero receiving P-1 messages, so the root’s inbound bandwidth is proportional to P times the per-rank payload while every other rank is idle. The broadcast phase then has the same shape in reverse. Total time scales linearly with P on the critical path, and the root becomes a serialization point for both memory bandwidth and network injection. At a few thousand ranks the root’s network port saturates long before the fabric does.

The alternative is to distribute the work so that every rank contributes bandwidth. Allreduce can be decomposed into a reduce-scatter, in which each rank ends up with the sum of one distinct slice, followed by an allgather, in which the slices are exchanged so that every rank holds all of them. Each phase moves n(P-1)/P elements per rank, which approaches n as P grows rather than nP. That is the difference between a cost that is linear in the process count and one that is essentially constant.

The two terms of the cost model

Almost every collective analysis uses the same two-parameter model. A message of n bytes costs

T(n) = alpha + beta * n

where alpha is the fixed per-message latency, covering software overhead, the network header, and the round trip through the adapter, and beta is the inverse of the achieved bandwidth per byte. On current interconnects alpha is on the order of a microsecond and beta corresponds to tens of gigabytes per second per port, but the exact values are properties of the fabric, the adapter, and the message rate, not of the standard.

A collective built from s sequential message steps and moving m bytes per rank therefore costs roughly s * alpha + m * beta. The two algorithms below differ in which term they minimize, and the crossover between them is a function of n, P, and the machine’s alpha-to-beta ratio.

The model is honest about its own limits. It ignores congestion, which matters when many ranks target the same link, and it ignores the fact that a rank can have several messages in flight. It is still the right first tool, because it predicts the shape of the curve: latency-dominated for small payloads, bandwidth-dominated for large ones.

Ring, recursive doubling, and the combined algorithm

Recursive doubling performs log2(P) steps. At step k, each rank exchanges its accumulator with the rank at distance 2^k and adds. After the last step every rank holds the sum of all contributions. Each step moves one full payload per rank, so the bandwidth term is n * log2(P) and the latency term is alpha * log2(P). For small n, the logarithm wins: a thousand ranks need ten steps rather than a thousand.

The ring algorithm arranges the ranks in a cycle and rotates partial sums. In the reduce-scatter phase each rank sends n/P elements per step and accumulates what it receives, over P-1 steps, ending with the complete sum of one slice. The allgather phase then rotates the finished slices the same way. Bandwidth per rank is 2n(P-1)/P, close to 2n, but latency is 2(P-1) * alpha, which is linear in the process count. For large payloads the bandwidth saving dominates; for small ones the step count is fatal.

The standard high-performance construction combines them. A reduce-scatter over slices, followed by an allgather over slices, has the bandwidth of the ring and the latency of recursive doubling: 2n(P-1)/P bytes and 2 log2(P) steps. This is the algorithm usually attributed to Rabenseifner, and it is what production libraries select for medium and large messages.

/* Recursive-doubling allreduce of one double per rank.
   Requires a power-of-two communicator size; other sizes need
   extra steps to fold in the remaining ranks. */
double allreduce_pow2(double local, MPI_Comm comm)
{
    int rank, size;
    MPI_Comm_rank(comm, &rank);
    MPI_Comm_size(comm, &size);

    double acc = local;
    for (int mask = 1; mask < size; mask <<= 1) {
        double other;
        int partner = rank ^ mask;          /* pair ranks differing in bit k */
        MPI_Sendrecv(&acc, 1, MPI_DOUBLE, partner, 0,
                     &other, 1, MPI_DOUBLE, partner, 0,
                     comm, MPI_STATUS_IGNORE);
        acc += other;
    }
    return acc;
}

The loop is the mechanism in miniature: after step k, each rank holds the sum over the block of 2^(k+1) ranks that shares its high bits. The exchange is symmetric, so no rank is a root and no rank is idle.

A communicator whose size is not a power of two is handled by running the power-of-two schedule over the largest power of two below the size and then folding the remainder in with extra steps. The standard does not prescribe the schedule; it only requires that the result be the reduction of all contributions, which is why libraries can choose freely and why the choice is invisible at the interface.

Floating-point sums are not associative

The standard requires reduction operators to be associative and commutative, and it does not require the implementation to apply them in any particular order. Addition of floating-point numbers is commutative but not associative, so different schedules produce different roundings. A sum over a million values accumulated in a different tree order is a different number, usually in the last few bits and occasionally in a much more visible place when cancellation is involved.

This has two consequences. First, a program’s output can change when the process count changes, even though the mathematical problem is identical, because the tree depth and the partition of the sum change with P. Second, two runs at the same process count can differ if the implementation selects a different algorithm, for example because a message crossed a size threshold or because the communicator was laid out differently.

Determinism can be recovered, at a cost. A fixed reduction order can be imposed by reducing to a single rank in a defined sequence, which reintroduces the linear critical path. Reproducible summation algorithms, such as compensated summation or error-free transformations, reduce the sensitivity but do not by themselves make the result independent of the order unless the order is also fixed. The trade is explicit: the fast algorithms are non-deterministic in the last bits, and the deterministic ones are slower.

Where collectives stop scaling

Three failure modes dominate.

The first is a mismatch. Every rank in a communicator must call the same collective in the same order, and an implementation has no way to detect that rank 7 called a broadcast while rank 8 called a reduction. The result is not an error message but a hang, or worse, a silent exchange of payloads between operations that happen to have compatible signatures. The matching rules from point-to-point communication apply underneath, and a collective is not more forgiving than the sends it is built from.

The second is a size cliff. Libraries choose an algorithm by message size and communicator size, and the chosen algorithm changes at thresholds that are tuned per platform. A code whose message size sits near a threshold can show a step change in time when a parameter changes slightly, and the step is not a bug. It is the cost model switching terms.

The third is that collectives synchronize. MPI_Allreduce does not require a barrier in the specification, but the algorithm effectively waits for the slowest contributor at every step, so the observed time is the maximum over ranks of arrival time plus the reduction. Load imbalance that a point-to-point code could hide becomes visible. This is one reason strong scaling flattens earlier than the arithmetic suggests: the reduction at the end of each iteration charges the job for its slowest rank.

The algorithms also set a floor for what any code can achieve. If a solver performs one allreduce per iteration over a small vector, the iteration time cannot fall below roughly 2 log2(P) * alpha, which at a thousand ranks and a microsecond of latency is tens of microseconds regardless of how fast the arithmetic is. That floor, not the floating-point rate, is often what limits a tightly coupled iteration. The communication-avoiding algorithms article takes the next step and restructures the arithmetic to need fewer of these global steps.