AllReduce is the most frequent collective communication primitive in distributed data-parallel and Megatron tensor-parallel training. The choice between Ring AllReduce and Tree AllReduce represents a fundamental trade-off between bandwidth utilization and communication latency.
Ring AllReduce (Bandwidth-Optimal)
Ranks form a logical ring. Tensors are split into N chunks. In ReduceScatter phase, chunks are passed around the ring in N-1 steps. In AllGather phase, reduced chunks are broadcast in another N-1 steps. Total volume sent is 2 * (N-1)/N * S.
Tree AllReduce (Latency-Optimal)
Ranks form a binomial or double-binary tree. Reduction flows up to the root in log2(N) steps and broadcasts back down in log2(N) steps. Faster for small messages where link initiation latency dominates.
NCCL Algorithm Selection Heuristic
NCCL automatically calculates expected execution time for both algorithms based on tensor size S, node count N, bus bandwidth B, and latency alpha, switching dynamically from Tree to Ring above threshold tensor sizes (typically > 500 KB to 2 MB).
MATHEMATICAL FORMULATION · ALGORITHMIC TIME COMPLEXITY
T_ring = 2 × ((N − 1) / N) × (S / B) + 2(N − 1)α vs T_tree = 2 log₂(N) × (S / B) + 2 log₂(N)α
As N grows large, (N-1)/N approaches 1.0, making Ring transfer time independent of rank count (2 * S / B). However, latency scales linearly with N (2*(N-1)*alpha), whereas Tree latency scales logarithmically (2*log2(N)*alpha).
REAL-WORLD PRODUCTION ENGINEERING
Set NCCL_ALGO=RING or NCCL_ALGO=TREE in environment variables during debugging to benchmark actual communication overhead.
Bucket small gradient tensors into contiguous buffers (e.g., PyTorch DDP bucket_cap_mb=25) to avoid thousands of high-latency small AllReduce calls.
Enable CUDA graph capture on communication kernels to eliminate CPU launch overhead between consecutive collective operations.