TL;DR: Ring all-reduce runs scatter-reduce then all-gather, each N−1 steps over chunks of size K/N, so every GPU moves 2(N−1)K/N ≈ 2K bytes regardless of N. That flat-in-N bandwidth term is why data parallelism scales, and the catch is the latency term 2(N−1)·α, which grows linearly and motivates NCCL's tree algorithms for small messages.
How to approach it
Walk the two phases concretely with a small N, then derive the per-GPU traffic and state the punchline: the bytes each GPU moves are nearly independent of cluster size, which is why data parallelism scales at all. Finish with the latency term, because knowing when ring all-reduce is the wrong algorithm is the senior half of the answer.
A strong answer
All-reduce: every GPU starts with its own K bytes of gradients; every GPU must end with the elementwise sum. Ring all-reduce arranges N GPUs in a logical ring and splits the buffer into N chunks.
Phase 1, scatter-reduce (N−1 steps). Each step, every GPU sends one chunk to its right neighbor and receives one from its left, adding the received chunk into its local copy. Chunks travel the ring accumulating partial sums; after N−1 steps, each GPU holds the fully reduced version of exactly one chunk. With N=4: GPU 0 ends up owning the complete sum of chunk 1 (say), GPU 1 of chunk 2, and so on.
The accumulation is easy to hand-wave and worth tracing exactly once, so we simulated the 4-GPU scatter-reduce (each cell counts how many GPUs' contributions a chunk has absorbed):
| chunk 0 | chunk 1 | chunk 2 | chunk 3 | |
|---|---|---|---|---|
| GPU0 after 3 steps | 1 | 4 | 3 | 2 |
| GPU1 after 3 steps | 2 | 1 | 4 | 3 |
| GPU2 after 3 steps | 3 | 2 | 1 | 4 |
| GPU3 after 3 steps | 4 | 3 | 2 | 1 |
The bold diagonal is the result: each GPU owns exactly one fully reduced chunk, and each chunk reached full accumulation on exactly one GPU, because it traveled the whole ring picking up one contribution per hop. The staircase of 1-2-3-4 in every row is the derivation made visible: a chunk's count equals how many hops it has taken, and N−1 hops is precisely enough to visit everyone once. Reconstruct this table on a whiteboard and the 2(N−1)K/N formula stops being memorized.
Phase 2, all-gather (N−1 steps). The completed chunks circulate the same way without arithmetic; after another N−1 steps every GPU has all N reduced chunks.
The cost: each GPU sends (and receives) one chunk of size K/N per step, for 2(N−1) steps:
bytes sent per GPU = 2(N−1) · K/N ≈ 2K for large N
time ≈ 2(N−1)/N · K/B + 2(N−1)·α (B = link bandwidth, α = per-step latency)
Two things to say out loud. First, the bandwidth term is essentially flat in N: going from 8 to 512 GPUs barely changes per-GPU traffic, and every link is busy every step (no hot spot). That ~2K is also a known lower bound for bandwidth-optimal all-reduce, so rings are within a factor of N/(N−1) of optimal. Second, the latency term grows linearly: 2(N−1) serialized hops. For big gradient buffers that is irrelevant; for small messages at large N (or cross-datacenter latencies) it dominates, which is why NCCL also implements tree and other algorithms and picks per message size and topology. Double binary trees get O(log N) latency at near-full bandwidth.
Per-GPU bytes 2(N−1)K/N, evaluated as N grows, stays nearly flat:
| GPUs N | Per-GPU bytes moved | Note |
|---|---|---|
| 4 | 1.5 K | 2·(3/4)·K |
| 8 | 1.75 K | 2·(7/8)·K |
| 64 | ~1.969 K | 2·(63/64)·K |
| 512 | ~1.996 K | 2·(511/512)·K, ≈ 2K |
Worked example interviewers like: 7B params in BF16 gives K = 14 GB. On 8 GPUs, each sends 2·(7/8)·14 ≈ 24.5 GB per step. Over NVLink at ~400 GB/s effective bus bandwidth, that is ~60 ms; over a single 400 Gb/s (50 GB/s) NIC, ~500 ms. This is why you overlap the all-reduce with the backward pass (bucketed gradients, as DDP does) and why per-GPU NIC counts on training nodes look extravagant until you do this math.
What interviewers probe next
- "Why split into chunks at all? Why not send the whole buffer around?" Naive ring (send full K each hop) costs each GPU (N−1)·K, and a centralized parameter server makes one node receive (N−1)·K. Both fail to keep all links busy; chunking pipelines the work so every link carries useful bytes every step.
- "When does NCCL not use a ring?" Small messages (latency-bound, so trees), and topologies where SHARP / in-network reduction on InfiniBand switches can do the reduction in the fabric, halving traffic.
- "How does this overlap with compute?" Gradients are bucketed (e.g., 25 MB buckets in PyTorch DDP) and all-reduced as soon as their layer's backward completes; a healthy run hides most of the 2K behind backward. If step time grows when you scale out, your overlap is broken; profile with NCCL traces, not nvidia-smi.
- "What is the cost of all-gather alone, as in FSDP?" (N−1)·K/N per GPU, half of all-reduce; FSDP pays it in forward and backward plus a reduce-scatter, which is how its total lands around 3K vs DP's 2K.
Common mistakes
- Stating 2(N−1)K/N from memory but being unable to reconstruct why. Interviewers ask for the two phases specifically to catch this.
- Forgetting the latency term entirely, then having no answer for "why does NCCL have tree algorithms?"
- Claiming ring all-reduce makes communication "free" because it overlaps. Overlap hides it behind compute only up to the point where comm time exceeds backward time; that crossover is exactly what kills naive scaling on slow fabrics.
- Doing the worked example in parameters instead of bytes (forgetting the ×2 for BF16, or ×4 for FP32 gradients), a factor-of-2 sloppiness in a question that is entirely about arithmetic.
Key takeaways
- Per-GPU traffic is 2(N−1)K/N ≈ 2K, flat in N: this is the whole reason DP scales.
- The latency term 2(N−1)·α grows linearly and is why NCCL switches to trees for small messages.
- Always do the worked example in bytes, not params, and overlap the all-reduce with backward or scaling stalls.