Allreduce method cuts communication time on torus networks
SP-Allreduce: Symmetric Tree Schedules for Tori and Beyond
Distributed, Parallel, and Cluster Computing
Summary
Large computer systems often need to quickly combine data from many parts, and the way their connections are arranged affects the speed of this process. The authors created a new method called SP-allreduce that uses the symmetrical structure of torus networks more efficiently. Their approach reduces the number of communication steps needed, making data combination faster, and they also extended it to other network shapes. They tested their method on different networks and found it performs better than existing methods by a noticeable margin.
What this means in practice
- •For high-performance computing teams: Reduce data aggregation time in distributed machine learning across torus-based supercomputers.
- •For data center network engineers: Optimize communication schedules in symmetric network topologies like spine-leaf and HyperX for faster data exchanges.
Authors
Mikhail Cherniavskii, Andrey Kupavskii, Georgy Mironov, Stanislav Moiseev
Abstract
Allreduce is a fundamental communication primitive in large-scale distributed training, and torus interconnects remain widely deployed in high-performance systems. We introduce SP-allreduce, a new allreduce algorithm for $d$-dimensional tori that exploits the symmetry of the topology and routes only along shortest paths. We call an allreduce algorithm \emph{fully bandwidth-optimal} if it incurs no bandwidth overhead, no multihop-induced traffic inflation, and achieves perfect per-round load balance. SP-allreduce is based on a family of carefully symmetrized shortest-path trees that guarantees full bandwidth optimality in the $α$--$β$ model. We prove that it uses the minimum possible number of rounds among all fully bandwidth-optimal allreduce algorithms on $d$-dimensional tori, and therefore the minimum running time in this class. In this sense, SP-allreduce refines Bucket allreduce: it preserves Bucket's key strengths while reducing the number of rounds by a factor of two. We further extend our approach to broader symmetric topologies and to communication trees of prescribed depths. Experimentally, the resulting algorithms improve over the best compared state-of-the-art algorithms for tori by up to $1.19\times$ on square tori and $1.65\times$ on rectangular tori across the tested configurations. On HyperX and spine-leaf networks, we demonstrate gains of up to $14.82\times$ and $1.72\times$, respectively, over the best evaluated baselines.