Collective communication algorithms

Identify the collective contract

A broadcast begins with one source buffer and finishes with a copy on every rank. A reduce combines values at one destination. An all-reduce combines values and returns the complete result to every rank. An all-gather begins with one shard per rank and returns every shard to every rank. A reduce-scatter combines full logical inputs and leaves one reduced shard per rank.

An all-to-all is different: each rank sends a distinct portion to every destination. Its traffic depends on the complete rank-pair pattern and can stress bisection bandwidth. Mixture-of-experts dispatch commonly uses this operation because each token can route to an expert on another rank.

Derive equal-split all-to-all traffic

Let each of P ranks begin with N bytes divided equally among P destinations. One N/P-byte slice is already at its destination and needs no network transfer. The rank sends the other P−1 slices, so its off-rank injection volume is (P−1)N/P bytes and its receive volume is equal. As P grows, the off-rank volume approaches N per rank even though each peer message becomes smaller.

This byte count does not predict time by itself. All ranks communicate with many peers, and routes can converge on the same NIC, switch uplink, or fabric cut. A pairwise link can be fast while the all-to-all is limited by endpoint message concurrency or bisection bandwidth. For expert routing, replace N/P with the actual per-destination token counts and include packing, padding, and capacity overflow.

Derive four-rank ring reduce-scatter

Let ranks R0 through R3 each hold chunks [0,1,2,3]. Arrange them in the ring R0→R1→R2→R3→R0. In every round, each rank sends one chunk to its next neighbor and receives one from its previous neighbor. The receiving rank reduces the values into the corresponding local partial result.

After P−1 = 3 rounds, each rank owns one fully reduced chunk. The ownership index depends on the schedule. Every rank sent three chunks of size N/4, so sent volume is 3N/4. Receive volume is equal. The full reduced tensor is not yet replicated.

Derive ring all-gather

Begin with the reduced chunk owned by each rank. In round one, every rank sends its owned chunk to the next neighbor and stores the received chunk. In the next rounds, it forwards chunks that other ranks still need.

After another P−1 rounds, every rank holds all P reduced chunks. Each rank again sent (P−1)N/P bytes. Combining phases gives 2(P−1) rounds and 2(P−1)N/P sent bytes per rank.

Compare ring and tree depth

The ring's dependent round count grows linearly with P. For large buffers, every link can carry one chunk per round and sustain an efficient pipeline. The per-rank byte volume approaches 2N as P becomes large.

A balanced tree has approximately log2(P) levels for a reduction and another log2(P) for a broadcast. The tree pays fewer startup stages for small messages. Link use and per-node load depend on the implementation and physical mapping, so the crossover must be measured on the target topology.

Use hierarchy for nonuniform topology

A flat algorithm assumes comparable links among ranks. Multi-node servers usually have fast local GPU fabrics and slower cross-node network links. Let each node contain G ranks and let there be Q nodes. One bandwidth-balanced hierarchical plan first reduce-scatters the N-byte tensor within each node, so each local rank owns an N/G-byte partial shard. Corresponding local ranks then all-reduce those shards across Q nodes. A local all-gather reconstructs the complete result inside each node.

During the global phase, each rank sends 2(Q−1)/Q × N/G bytes under the ideal ring model. Summed over G local ranks, one node sends 2(Q−1)N/Q bytes across the network. This calculation separates constrained network traffic from the two local phases. Actual NIC and rail mapping determines whether the G cross-node groups use independent paths or contend for one port.

A leader-based hierarchy is different. Local ranks reduce to one leader, leaders exchange a full N-byte result, and leaders broadcast locally. The leader design can reduce the number of network participants but concentrates endpoint traffic and memory work. Do not refer to both designs as one hierarchical byte count; draw ownership and calculate the selected schedule.

Include implementation details

Libraries divide large buffers into chunks and channels. Multiple channels use parallel paths or endpoints. Protocols select payload granularity and synchronization behavior. Reduce-scatter also performs local arithmetic and memory traffic.

The ideal byte and round model predicts broad behavior. The model does not specify actual channels, protocol, routing, or overlap. Compare the model with library logs, completed-payload bandwidth, bus-bandwidth conventions, and rank timelines before assigning a cause to the difference.

Draw a rank timeline

For a small rank count, write one row per rank and one column per dependent round. Label the chunk sent, chunk received, local reduction, and resulting ownership. This exposes whether a claimed schedule sends a chunk before it exists, uses a link twice in one round, or finishes without every rank owning the promised result.

Then map every logical edge to the physical route. Two ring edges that look independent can share one NIC, PCIe switch, or fabric cut. The logical timeline supplies dependency depth; the route map supplies contention. Both are needed to predict elapsed time.