DDP & Ring-AllReduce

In DDP (distributed data parallelism), N ranks each hold the gradients $g_i$ of their data shard, and training must sum (or average) them into the global gradient — exactly the All-Reduce operation. Let $S$ be the per-rank gradient size in bytes. The naive implementation (every rank sends its full $S$ bytes to the other N−1 ranks) costs $O(NS)$ per rank, scaling linearly and not extensible; Ring-AllReduce uses a ring topology to bring per-rank communication down to about $2S$, independent of N — the bandwidth-optimal scheme. Split the gradient into N chunks (each $S/N$ bytes); two phases of N−1 steps each: ① Scatter-Reduce: at step $k$, $\text{rank}\,i$ sends local chunk $(i-k) \bmod N$ to the next hop $\text{rank}\,(i+1) \bmod N$, and receives chunk $(i-k-1) \bmod N$ from $\text{rank}\,(i-1) \bmod N$, accumulating it in place; after N−1 steps each rank fully holds the global sum of exactly one chunk (different chunks' sums live on different ranks). ② All-Gather: the rank owning a global sum forwards it around the ring; after another N−1 steps every rank holds the global sum of all chunks. Volume derivation: each step sends $S/N$ bytes per rank, two phases total $2(N-1)$ steps, so per-rank volume $V = 2(N-1)\cdot\frac{S}{N} = 2\frac{N-1}{N}S$; as $N \to \infty$, $V \to 2S$ — because the per-step volume $S/N$ shrinks with N while the step count $N-1$ grows with N, the product converges to a constant, so per-rank bandwidth is independent of N (the full gradient is transmitted $O(S)$ times, not $O(NS)$). Latency, however, is $2(N-1)$ serial hops, still growing linearly with N: for small messages or slow networks Ring is not optimal, which is why NCCL uses tree algorithms across nodes and hierarchical reduce over NVLink within a node. Gradient overlap: backprop computes gradients layer by layer from the last layer backward; DDP buckets parameters (default ~25MB per bucket) and launches each bucket's All-Reduce asynchronously as soon as its gradients are ready, overlapping communication with the remaining backward compute so latency is almost entirely hidden; global gradient clipping happens after all All-Reduces complete and before the optimizer step.

essential infrastructure knowledge for multi-GPU large-model training (the bridge node between the DL and AI_Infra modules); interview favorites: derive Ring-AllReduce's communication volume, why it is independent of N, and how gradients overlap with backprop.

gradient synchronization is the dominant communication bottleneck of data parallelism — the more GPUs, the more sync overhead can eat the compute speedup. Ring-AllReduce keeps per-rank bandwidth at a constant ~$2S$ so communication time does not grow linearly with the number of GPUs (in the bandwidth-bound regime); combined with gradient bucketing and asynchronous overlap, latency hides inside compute, yielding near-linear scaling for single-node and multi-node training.

Derive Ring-AllReduce's volume: $S/N$ per step, $2(N-1)$ steps total → $V = 2\frac{N-1}{N}S$; show $V \to 2S$ as $N \to \infty$, i.e. the volume is independent of N.

Describe the two phases: how chunks circulate (index $(i-k) \bmod N$), why each phase takes exactly N−1 steps, and how every rank ends with the global sum of all chunks.

What is the per-rank volume of naive All-Reduce (each rank sends full $S$ to N−1 others) — $O(NS)$? Why is Ring bandwidth-optimal ($2S$ being near the lower bound of reading the full gradient)?

If bandwidth doesn't grow with N, why does latency still grow ($2(N-1)$ serial hops)? In which scenarios does NCCL switch to tree/hierarchical algorithms (small messages, slow networks, across nodes)?

How does DDP hide communication latency: gradient bucketing (~25MB) + launching each bucket's All-Reduce asynchronously once ready, overlapping with the remaining backprop; why is global gradient clipping done after All-Reduce and before the step?