Trivance: Latency-Optimal AllReduce by Shortcutting Multiport Networks
This work addresses the latency bottleneck of AllReduce in direct-connect topologies like TPUv4 tori, which is critical for large-scale distributed training and inference.
Trivance is a novel AllReduce algorithm that reduces communication steps to log3(n) (50% improvement over prior methods) and reduces congestion by a factor of three, achieving 5-30% performance improvement for small to medium AllReduce sizes in high-bandwidth settings.
AllReduce is a fundamental collective communication operation in distributed computing and a key performance bottleneck for large-scale training and inference. Its completion time is determined by the number of communication steps, which dominate latency-sensitive workloads, and the communication distance affecting both latency- and bandwidth-bound regimes. Direct-connect topologies, such as Google's TPUv4 tori, are particularly prone to large communication distances due to limited bisection bandwidth. In this paper, we present Trivance, a novel AllReduce algorithm that completes within $\log_3 n$ steps - a 50% improvement in comparison to Swing and Recursive Doubling, while reducing congestion compared to Bruck's algorithm by a factor of three and preserving bandwidth-optimality. Trivance exploits both transmission ports of a bidirectional ring within each step to triple the communication distance along both directions simultaneously. By performing joint reductions, Trivance improves both the number of steps and network congestion. We further show that Trivance extends naturally to multidimensional torus networks, retaining its latency advantage while achieving performance comparable to bandwidth-optimal algorithms for large AllReduce sizes. Our packet-level SST simulation shows that Trivance improves state-of-the-art approaches by 5-30% for AllReduce sizes up to 8 MiB, in high-bandwidth settings up to 32 MiB and for 3D tori up to 128 MiB. Throughout the evaluation, Trivance remains the best-performing latency-optimal algorithm.