Ring AllReduce is the bandwidth-optimal collective communication algorithm that reduces and broadcasts data across N workers by passing partial results around a logical ring — using exactly 2(N-1)/N of the minimum possible bandwidth and scaling independently of the number of workers, making it the dominant algorithm for synchronizing gradients in data-parallel deep learning training.

The AllReduce Problem

• N workers each hold a vector of size S.
• Goal: Every worker ends up with the element-wise sum (or average) of all N vectors.
• Naive approach (send all to one, reduce, broadcast): Bottlenecked on single node — O(N×S) at root.

Ring AllReduce — Two Phases

Phase 1: Reduce-Scatter (N-1 steps) 1. Divide each worker's data into N chunks. 2. Step 1: Worker i sends chunk i to worker (i+1) mod N; receives chunk (i-1) from worker (i-1) mod N; accumulates (adds) received chunk. 3. Repeat N-1 times: Each step, a different chunk moves around the ring, accumulating partial sums. 4. After N-1 steps: Worker i holds the fully reduced chunk i.

Phase 2: AllGather (N-1 steps) 1. Same ring pattern, but now workers send their fully-reduced chunk around. 2. After N-1 steps: Every worker has all N fully-reduced chunks = complete AllReduce result.

Bandwidth Analysis

• Ring is bandwidth-optimal: Each link carries exactly the minimum data required.
• Ring has high latency: 2(N-1) steps — worse than tree for small messages.
• For gradient sync (large messages, S >> 1GB): Bandwidth dominates → Ring wins.

Implementation in Practice

• NCCL (NVIDIA): Implements ring AllReduce over NVLink and InfiniBand.
• Automatically selects ring vs. tree vs. recursive halving based on message size.
• For large messages (> 256KB): Ring AllReduce is default.
• Gloo (Meta): CPU-based ring AllReduce for PyTorch.
• Horovod: Originally popularized ring AllReduce for distributed deep learning.

Ring AllReduce for Gradient Sync

• Each GPU computes gradients locally → ring AllReduce averages gradients across all GPUs.
• With 8 GPUs and 1GB of gradients:
• Each GPU sends/receives: $2 \times 1GB \times \frac{7}{8} = 1.75GB$ total.
• Over NVLink (300 GB/s bidirectional): ~6 ms.
• This is overlapped with backward computation → nearly free.

Ring AllReduce is the algorithm that enabled efficient multi-GPU deep learning — its bandwidth-optimal scaling means that adding more GPUs for data-parallel training incurs minimal communication overhead, directly enabling the large-scale training runs behind modern language models.