TL;DR: All-reduce combines matching elements and returns the result to every rank. Reduce-scatter combines them but leaves each rank a shard. All-gather copies shards into a complete result on each rank. All-to-all exchanges destination-specific chunks without inherently reducing them. State the starting layout before calculating traffic.
How to approach it
Draw two ranks with small, different values. Say who owns each output. Only then choose a collective algorithm, message size and rank count for the cost model.
A strong answer
A gradient bucket is ready on two workers. Rank 0 has [1, 2], rank 1 has [3, 4], and both need the elementwise sum [4, 6]. All-Reduce does that. Averaging would require division as well; sum does not implicitly mean average.
The decomposition explains the result, not necessarily the implementation selected by a library. Trees, rings and other algorithms can deliver the same semantics. NCCL's collective documentation defines those layouts independently of a particular timing model.
All-to-all has a different job. Suppose rank 0 owns destination chunks [a0, a1] and rank 1 owns [b0, b1]. After exchange, rank 0 has [a0, b0] and rank 1 has [a1, b1]. No sum occurred. In Expert Parallelism, the chunks can contain tokens routed to different expert owners; unequal routing means unequal payload sizes and possibly a variable-size exchange.
Here is a four-rank ring byte example. Let S=16 MiB be the complete logical reduction buffer on each input rank. Count bytes sent per rank, excluding protocol overhead and receive bytes:
reduce-scatter send = (N−1)/N × S = 3/4 × 16 = 12 MiB
all-gather send = (N−1)/N × S = 12 MiB
all-reduce send = 2 × (N−1)/N × S = 24 MiB
sanity: after reduce-scatter, each rank owns 16/4 = 4 MiB.
For the all-gather in this example, S is the final 16 MiB result assembled on every rank. Each rank begins with only 4 MiB. Substituting that local shard into the same formula would undercount traffic by four. Now consider a separate all-to-all with a 16 MiB local input split equally among four destinations: each rank keeps 4 MiB and sends 12 MiB. The send count happens to match, but the meaning of the starting buffer is different.
NCCL tests' performance notes explain normalization factors. Keep algorithm bandwidth, normalized bus bandwidth and a physical link's directional rate separate. A 24 MiB send estimate is not 24 MiB of total fabric traffic, and adding received bytes does not double elapsed time on an independently bidirectional path.
| Training task | Typical ownership need |
|---|---|
| Replicated gradients | Reduced result on all replicas |
| Sharded optimizer | Reduced gradient shard per owner |
| Materialize sharded parameters | Gather pieces for the operation |
| Dispatch tokens to experts | Route chunks to destination owners |
Ordinary data parallelism commonly uses the first row; optimizer/state sharding uses the next two. Tensor parallelism may reduce partial matrix products or gather/scatter activations according to its layout. Expert parallelism uses the destination exchange. These are common mappings, not exclusive ownership of a primitive.
The actual implementation may use different dtypes, grouping, fusion and repeated gathers. Replacing all-reduce with reduce-scatter plus all-gather does not prove an entire sharded training step transfers the same bytes. Count every invocation and its buffer.
For a hypothetical bandwidth of 12 GiB/s available to the modeled send path, 24 MiB takes at least 1.953 ms before startup, contention or synchronization. Small messages can be latency-bound even when that large-message rate is achievable. Ring cost alone cannot choose the winner.
Collective Communication Primitives provides the ownership vocabulary; Ring vs Tree All-Reduce examines alternative communication schedules. Start with the collective whose output ownership matches the next operation. Reverse an optimization if complete update time worsens, memory no longer fits, or numerical checks fail. Profile group membership, message sizes, arrival skew and exposed duration; a rank waiting for input is different from a saturated link.
What interviewers probe next
- “Can all-gather reverse a reduction?” It can replicate reduced shards, but it cannot recover the original operands that were summed.
- “Does all-to-all send every chunk simultaneously?” Its semantics do not prescribe simultaneous physical transfers.
- “Why different floating-point results?” A changed reduction order can change rounding. Validate the required tolerance.
Common mistakes
- Calling the local shard and full gathered output the same S.
- Treating a topology-independent result as a topology-independent runtime.
- Assigning every collective in a job to its world-size group.
Key takeaways
- Two input vectors [1, 2] and [3, 4] reduce to [4, 6].
- The four-rank, 16 MiB ring sends 24 MiB per rank for all-reduce.
- Ownership determines semantics; actual calls and topology determine cost.