Data Parallelism › The All-Reduce Operation

All-reduce is the communication primitive at the heart of DDP. Understanding how it works explains both why DDP is efficient and what its scaling limits are. All-reduce is not a single algorithm but a family of algorithms with different performance characteristics. Choosing the right one for your hardware topology can make a substantial difference in training speed.

The simplest correct all-reduce is a two-step reduce-broadcast:

1. One designated root rank aggregates all tensors from all other ranks (reduce to root)
2. The root broadcasts the result to all other ranks

This approach has the same parameter server bottleneck problem we described earlier. The root rank must receive data from $N-1$ other ranks (inbound traffic $= (N-1) \cdot |\mathbf{g}|$ bytes) and send data to $N-1$ ranks (outbound traffic $= (N-1) \cdot |\mathbf{g}|$ bytes). The root's required bandwidth scales linearly with $N$. For large $N$, this approach is impractical.

The standard solution is ring all-reduce, popularized by Baidu Research (Gibiansky, 2017) for deep learning. In ring all-reduce, the $N$ ranks are arranged in a logical ring topology. The algorithm has two phases, each consisting of $N-1$ communication steps.

Phase 1: Reduce-Scatter

In the reduce-scatter phase, each rank splits its gradient tensor $\mathbf{g}_r$ into $N$ equal chunks: $\mathbf{g}_r = [\mathbf{g}_r^{(0)}, \mathbf{g}_r^{(1)}, \ldots, \mathbf{g}_r^{(N-1)}]$. Over $N-1$ communication steps:

• Each rank sends one chunk to its right neighbor in the ring
• Each rank receives one chunk from its left neighbor and adds it to its local copy of that chunk

After $N-1$ steps, each rank holds one chunk that contains the sum of that chunk across all ranks. Specifically, rank $r$ holds $\sum_{i=0}^{N-1} \mathbf{g}_i^{(r)}$, the fully summed version of chunk $r$.

Phase 2: AllGather

In the all-gather phase, each rank sends its fully-summed chunk to its right neighbor over $N-1$ steps. By the end:

• Every rank holds every chunk of the fully summed gradient
• The complete synchronized gradient $\sum_{r} \mathbf{g}_r$ is on every rank

The total data transferred by each rank across both phases is:

$$\text{Data per rank} = 2 \cdot \frac{N-1}{N} \cdot |\mathbf{g}|$$

where:

• $|\mathbf{g}|$ is the total size of the gradient tensor in bytes
• $\frac{N-1}{N}$ approaches 1 as $N$ grows, so each rank transfers approximately $2|\mathbf{g}|$ bytes regardless of the number of GPUs
• The factor of 2 accounts for both phases: one reduce-scatter send and one all-gather send, each of approximately $|\mathbf{g}|$ bytes total

The defining property of ring all-reduce is that the per-rank communication volume is independent of $N$. Adding more GPUs does not increase the amount of data each GPU must send or receive. This is what makes ring all-reduce bandwidth-optimal: it achieves the theoretical minimum data transfer for the all-reduce problem.

To understand why this is remarkable, compare it to the naive reduce-broadcast: a single root rank must send and receive approximately $N \cdot |\mathbf{g}|$ bytes, which grows linearly with $N$. Ring all-reduce eliminates this growth by distributing the aggregation work evenly.

Ring all-reduce is optimal for large messages where bandwidth is the bottleneck. For small messages (small models, small gradient tensors), the latency of $2(N-1)$ communication steps becomes significant even if each step transfers little data. In this regime, a tree topology performs better.

In a binary tree all-reduce, ranks are organized as a binary tree. The reduce phase propagates data up the tree from leaves to root, with each internal node summing the values it receives from its children. The broadcast phase propagates the result back down from root to leaves. The total number of communication steps is $2 \log_2 N$ rather than $2(N-1)$ steps, which is dramatically fewer for large $N$.

The tradeoff is bandwidth: the root of the tree must process and retransmit $O(\log N)$ times as much data as leaf nodes, creating mild hotspots. For the large gradient tensors typical in language model training, ring all-reduce generally wins on throughput because bandwidth, not latency, is the bottleneck. For very small tensors (such as bias gradients in individual layers), tree-based all-reduce can be faster.

In practice, PyTorch uses NVIDIA Collective Communications Library (NCCL) rather than implementing ring all-reduce directly in Python or CUDA. NCCL is topology-aware: it detects whether GPUs are on the same PCIe bus, connected via NVLink, or spread across multiple nodes connected by InfiniBand or RoCE, and chooses the optimal communication algorithm for each case. NCCL also handles buffer management, stream synchronization, and error recovery, all of which are tedious to implement correctly.

NVLink (the high-bandwidth GPU interconnect available on NVIDIA A100 and H100 servers) provides roughly 600 GB/s aggregate bidirectional bandwidth on modern 8-GPU nodes, compared to roughly 32 GB/s for PCIe. For multi-node training, InfiniBand HDR provides roughly 200 Gb/s per link (about 25 GB/s). The bandwidth difference between NVLink and InfiniBand is enormous: NVLink is roughly 24 times faster per GPU. This means that gradient communication that takes 20 ms on NVLink takes nearly 500 ms on InfiniBand, completely dominating compute time.

The topology distinction is particularly important for multi-node training. Within a single node with 8 GPUs connected via NVLink, NCCL uses a ring or tree topology that fully exploits the high NVLink bandwidth. Across nodes, NCCL routes traffic through the node's InfiniBand host channel adapter (HCA), which has far lower bandwidth per GPU than NVLink. A typical multi-node DDP job therefore has a two-level communication hierarchy: intranode communication using the fast NVLink fabric, and internode communication using the slower InfiniBand fabric.

Understanding this hierarchy helps you make informed decisions about how to partition GPUs. If you have a cluster of 8-GPU nodes, it is almost always better to fill entire nodes before spreading to additional nodes. Keeping communication within a single node maximizes the use of NVLink and minimizes InfiniBand traffic. Once you must cross nodes, you want to keep the cross-node gradient transfers as small as possible, which is one motivation for combining DDP with ZeRO (which reduces the gradient tensor that must be communicated across nodes).