allreduce collective communication
**AllReduce Collective Communication** is **the fundamental distributed operation that combines (reduces) values from all participating processes and distributes the result to every process — serving as the primary gradient synchronization mechanism in data-parallel deep learning training, where its bandwidth efficiency directly determines multi-GPU scaling performance**.
**AllReduce Semantics:**
- **Operation**: given N processes each holding a vector of size S, AllReduce produces the element-wise reduction (sum, max, min, etc.) and distributes the complete result to all N processes
- **Naive Implementation**: reduce to root (O(S) at root) + broadcast from root (O(S) per hop) = O(N·S) total data transfer; root bandwidth bottleneck makes this impractical
- **Optimal Lower Bound**: each process must send and receive at least S·(N-1)/N ≈ S bytes; any algorithm achieving this is bandwidth-optimal — independent of N for large S
**Algorithm Variants:**
- **Ring AllReduce**: N processes arranged in logical ring; two phases: reduce-scatter (N-1 steps, each process sends 1/N of data forward and receives/reduces 1/N) and allgather (N-1 steps, each process forwards its completed chunk); transfers 2S·(N-1)/N ≈ 2S bytes per process — bandwidth-optimal
- **Recursive Halving-Doubling**: processes pair recursively (like butterfly network); each step, paired processes exchange half the data and reduce; in log₂N steps, all processes have the complete result; O(S log N/N + S) transfer — better latency for small messages
- **Tree AllReduce**: reduce up binary tree to root, then broadcast down; O(S·log N) total transfer — not bandwidth-optimal but simple, low latency for small messages (2 log N steps vs 2(N-1) for ring)
- **Bucket/Direct AllReduce**: each process is responsible for reducing 1/N of the data; all processes send their chunk to the responsible process (reduce-scatter), then responsible process broadcasts the result; 2S·(N-1)/N transfer — equivalent to ring but may use different network topology
**NCCL Implementation:**
- **Topology-Aware**: NVIDIA NCCL detects NVLink/NVSwitch/PCIe topology and selects optimal algorithm; NVSwitch-connected GPUs use one-shot AllReduce via NVSwitch multicast; PCIe-only systems use ring or tree
- **Multi-Node**: hierarchical AllReduce: intra-node ring/NVSwitch AllReduce, then inter-node tree or ring AllReduce via InfiniBand RDMA; minimizes slow cross-node traffic
- **Double Binary Tree**: NCCL's tree algorithm uses two overlapping binary trees that together achieve bandwidth optimality — each tree transfers S/2 data, and both trees operate concurrently
- **Pipeline**: large AllReduce operations are chunked and pipelined — multiple chunks flow through the ring/tree simultaneously, hiding latency and achieving steady-state bandwidth
**Performance Characteristics:**
- **Bandwidth Efficiency**: ring AllReduce achieves 85-95% of unidirectional NVLink bandwidth per GPU; NVSwitch AllReduce achieves >95% — measured in GB/s per GPU, not aggregate
- **Latency Components**: per-step latency includes: network transit (~1 μs NVLink, ~1-5 μs InfiniBand), software overhead (~2-5 μs per step), and reduction compute (~0.1 μs per MB for fp16 sum); total latency: α·steps + S·(N-1)/(N·BW)
- **Scaling Efficiency**: for large messages (>10 MB), ring AllReduce achieves near-linear bandwidth scaling — communication time is constant regardless of GPU count; for small messages (<100 KB), latency dominates and tree algorithms are preferred
- **Overlap with Compute**: overlapping AllReduce communication with backward pass computation hides most of the communication latency — achieved by launching per-layer AllReduce as soon as gradients for each layer are available, overlapping with earlier layers' backward computation
AllReduce is **the single most performance-critical operation in distributed deep learning — its efficient implementation by libraries like NCCL is what makes multi-GPU training practical, and understanding the tradeoffs between ring, tree, and hybrid algorithms is essential for optimizing training at scale**.