SHORTCUT: In-Collective Topology Reconfiguration for Low-Latency AllReduce
TL;DR
Shortcut is presented: an effective strategy for topology reconfiguration that enables RD to shortcut costly multi-hop communication only when it pays off - beyond the performance of the Ring algorithm.
Abstract
Distributed ML training relies on efficient AllReduce communication to aggregate data across nodes. In this setting, reconfigurable optical interconnects offer high-bandwidth, energy-efficient direct links between accelerators but often produce ring-based topologies that remain static during a collective. The Ring AllReduce algorithm naturally matches these topologies but its cumulative latency grows linearly with node count. Low-latency algorithms such as Recursive Doubling (RD) instead achieve logarithmic cumulative per-step latency, but their long-distance exchanges incur dilation and congestion costs on a static ring. In-collective topology reconfiguration can eliminate these penalties but each topology change adds reconfiguration delay. The key question to improve AllReduce completion time is therefore not only how to reconfigure RD efficiently, but when selectively reconfigured RD becomes faster than the topology-matched Ring algorithm. We present Shortcut: an effective strategy for topology reconfiguration that enables RD to shortcut costly multi-hop communication only when it pays off - beyond the performance of the Ring algorithm. Across small and medium messages on 32 nodes, Shortcut achieves $4.4\times$-$6.0\times$ speedups over Ring. At 128 nodes, it remains up to $7\times$ faster with a $10\,\mu s$ reconfiguration delay, showing that selective reconfiguration is especially effective in latency-sensitive, large-scale settings.