ring allreduce algorithm
**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**
| Algorithm | Data Transferred (per worker) | Latency (steps) |
|-----------|------------------------------|----------------|
| Naive (tree) | 2S | 2 log₂(N) |
| Ring AllReduce | 2S × (N-1)/N | 2(N-1) |
| Recursive Halving-Doubling | 2S | 2 log₂(N) |
- 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.