Title: Trivance: Latency-Optimal AllReduce by Shortcutting Multiport Networks
Authors: Anton Juerss (Weizenbaum Institute & TU Berlin); Vamsi Addanki (Purdue University); Stefan Schmid (TU Berlin & Weizenbaum Institute)
Introduction
This paper studies how to accelerate AllReduce, the collective operation that aggregates and redistributes data across machines during distributed training and HPC workloads. AllReduce is often a major communication bottleneck: it can account for over 40% of MPI communication time, and its startup latency becomes especially costly for small or medium messages. Existing algorithms face a tradeoff. Recursive Doubling and Swing use relatively few resources efficiently but require \(\log_2 n\) steps, while Bruck reaches the lower bound of \(\log_3 n\) steps on bidirectional rings but routes traffic predominantly in one direction, producing high congestion. The problem is increasingly important for direct-connect accelerator fabrics such as torus-based TPU systems, where every node has multiple bidirectional ports that conventional designs do not fully exploit.
Key idea and contribution
The authors introduce Trivance, a new AllReduce algorithm for bidirectional rings and multidimensional tori. Its central idea is to communicate in both directions simultaneously and jointly reduce the two incoming messages at each step. Rather than treating the two ports as independent mirrored collectives, Trivance combines their information, allowing each round to expand a node’s known data range by a factor of three. It therefore completes latency-optimal AllReduce in \(\lceil \log_3 n \rceil\) steps, a roughly 50% reduction in communication rounds compared with \(\log_2 n\)-step methods such as Recursive Doubling and Swing.
Trivance provides both latency- and bandwidth-optimal variants. The latency-oriented version sends the full vector each step to minimize rounds; the bandwidth-oriented version uses Reduce-Scatter followed by AllGather, partitions data across nodes, and sends only the necessary blocks. The paper proves that the approach is bandwidth-optimal, reduces congestion by a factor of three relative to Bruck, and extends naturally to multidimensional torus networks by scheduling communication across different dimensions. The authors also describe practical integration requirements, including synchronized receipt of the two incoming chunks and topology-aware mapping to distinct network paths.
Evaluation
The authors evaluate Trivance using packet-level SST simulations over rings and 2D/3D tori, comparing it with Recursive Doubling, Swing, Bucket, and an adapted Bruck baseline for message sizes from 32 B to 128 MiB. Under an 800 Gb/s configuration, Trivance is the best latency-optimal approach and improves completion time by 5–30% for latency-bound workloads. Its advantage persists up to 512 KiB on rings, 8 MiB on multidimensional tori, and 32 MiB in high-bandwidth networks; on a 16×16×16 torus, it outperforms every baseline for the full tested range up to 128 MiB, with up to 20% lower completion time. This result is significant because modern accelerator clusters increasingly use high-dimensional direct-connect fabrics, where reducing collective latency can directly improve distributed-training throughput and hardware utilization.
Q: How could this system be extended to other collectives, such as AllGather and ReduceScatter?
A: Trivance, as well as our analysis of its transmission cost, applies directly to ReduceScatter and AllGather. In fact, in the bandwidth-optimal variant, we decompose AllReduce into a ReduceScatter phase and an AllGather phase, and compare it with the bandwidth-optimal variants of other algorithms. We also believe that the underlying idea may be useful for other collectives, such as All-to-All, and for reconfigurable networks. However, these extensions and their analysis are not covered in this paper.
Personal thoughts
I like that Trivance identifies a clean algorithmic gap: bidirectional ports had been available, but earlier mirrored designs treated them as separate collectives instead of using their combined information to reduce the number of rounds. The resulting radix-three communication pattern is intuitive, theoretically justified, and particularly compelling for latency-sensitive workloads. I also appreciate that the paper does not oversell universal superiority: Bucket or Swing can still win for sufficiently large messages in lower-dimensional or bandwidth-constrained networks.
The main open question is practical deployment. The results come from detailed simulation rather than an implementation in NCCL, MPI, or a TPU collective runtime. Joint reduction introduces synchronization, buffering, and chunk-readiness constraints, and real NIC/channel contention may weaken the idealized two-path assumption. It would be valuable to measure Trivance on production hardware, quantify its software overhead, and study whether adaptive algorithm selection can choose Trivance only when topology, message size, and available independent paths make it beneficial.