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

Ring All-Reduce is a widely used protocol within large-scale distributed training for aggregating gradients across workers in each iteration. 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 crucially 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 close to zero with communication and storage rates approaching one with increasing $c$. However, this limit is achieved through ill-conditioned encoding matrices. Accordingly, we give an alternate construction whose error is $O(ϵ)$, while the relevant condition numbers are $O({ϵ}^{-r_{\star }})$, where $r_{\star }=\lceil c/N\rceil -1$. This naturally motivates a condition-number-constrained optimization formulation for trading off the competing objectives and obtaining numerically stable practical designs. Our numerical experiments demonstrate that when compared with the production-standard NCCL on NVIDIA A100 PCIe GPU Clusters with low-bandwidth PCIe interconnect, CERAR reduces the raw All-Reduce phase time by up to 47%, and 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 the other hand, for GPU clusters with high-bandwidth NVLink interconnects, CERAR performs worse on the All-Reduce phase time and slightly worse in terms of training. Nevertheless, the gap reduces with experiments that involve systems with larger parameter counts. In this scenario we expect the gains to manifest with more optimized implementations of the CERAR protocol.