Tree and recursive-doubling collectives

Take p equal to a power of two. In a simple recursive-doubling AllReduce, each rank exchanges its current full-array partial result with a partner whose rank differs in one successive bit. After one round it covers two ranks, after two it covers four, and after log2(p) rounds it covers all participants. Assume a compatible associative and commutative reduction for this simple schedule. Each exchange can reduce received values locally. The protocol's valid ordering for a noncommutative operation needs additional care rather than relying on a rank-bit diagram.

A full-array exchange sends n bytes each round, so logarithmic startup does not imply a single-tensor byte volume. A simple tree reduce followed by broadcast has a different two-phase critical path, with its own fan-in, fan-out, and contention assumptions. Real libraries can use double trees, pipelining, multiple channels, and hardware assistance. The teaching equations compare specific idealized algorithms. They are not a statement that every operation named tree has the same traffic or that one generic tree formula describes current NCCL on every architecture.

A recursive-halving reduce-scatter exchanges successively smaller relevant portions, leaving each rank with its reduced shard. A reverse allgather doubles the available reduced data until every rank has the full result. For equal datatype-aligned partitions and a power-of-two group, each phase has logarithmic steps and aggregate per-rank send volume n(1−1/p). This achieves a different latency-bandwidth balance from full-array recursive doubling. It requires suitable element partitioning and operator support; non-power-of-two sizes need an explicitly described extension or another algorithm.

Local reduction work still matters and can be represented by an additional seconds-per-byte or seconds-per-element term in a richer model. GPU kernels can also contend for memory bandwidth while network transfers occur. Keeping those terms separate helps identify when an apparently better network schedule loses in practice. The original collective-optimization literature analyzes multiple message sizes and participant counts precisely because the best choice changes with the regime. Record what assumptions hold before using a model crossover to tune a real job.

For a small tensor, the transfer term may be much smaller than a few additional startup rounds. A scalar synchronization can therefore behave differently from a hundred-megabyte gradient bucket. For a large tensor, repeated full-array exchanges can dominate despite a low round count. Validate several representative payloads and datatype choices instead of carrying a single microbenchmark result into every layer of a model. An autotuned implementation may already choose different algorithms across those sizes, so a manual override can improve one point and worsen the rest.

The modular lab illustrates the rank-bit partner progression as a separate arithmetic exercise. Reset, set both m=8 and a=1, predict all eight residues appear in one additive orbit, then Play or Step. Separately Reset, set both m=8 and a=4, predict period two, then Play or Step. This is addition modulo eight, not the XOR partner schedule used by recursive doubling and not a tree simulation. State that difference explicitly: arithmetic coverage can be inspected here, but the logarithmic communication argument must come from the actual partner protocol described above.