Communication-Efficient Distributed Training via Ring-Based Coded Approximate All-Reduce

Abstract

Ring All-Reduce is a widely used protocol for aggregating gradients across workers in large-scale distributed training. For a system with $N$ workers, its normalized per-worker communication is $2(N-1)/N$. In this work we present a communication-efficient Ring All-Reduce (CERAR) protocol for ``approximate''gradient aggregation. CERAR partitions each local gradient into $c$ components and relies on linear encoding and decoding operations. It performs $L=c+N-2$ communication rounds over an $N$-worker ring, yielding normalized communication rate $1+(N-2)/c$ and normalized storage rate $1+N/c$. We present an explicit Vandermonde matrix based construction whose approximation error can be made arbitrarily small, with communication and storage rates approaching one as $c$ increases. However, this comes at the cost of ill-conditioned encoding matrices. We therefore give an alternate construction whose error is $O(\epsilon)$, while the relevant condition numbers are $O(\epsilon^{-r_\star})$, where $r_\star=\lceil c/N\rceil-1$. This motivates a condition-number-constrained optimization formulation for obtaining numerically stable practical designs. Our experiments show that, compared with the production-standard NCCL on NVIDIA A100 PCIe GPU clusters with low-bandwidth PCIe interconnect, CERAR reduces raw All-Reduce time by up to 47\%. For training a 1.4-billion-parameter Pythia model, it reduces training time by about 17\% for the same number of iterations while achieving essentially identical validation loss. On GPU clusters with high-bandwidth NVLink interconnects, CERAR performs worse in the All-Reduce phase and slightly worse in overall training time. However, the gap narrows for larger model sizes, suggesting that further gains may be possible with more optimized CERAR implementations.