Tuning Collective Patterns to Alleviate Congestion in Shared AI Clusters

Summary

Distributed AI training repeatedly executes collective communication patterns (e.g., NCCL's dual binary-tree AllReduce), and congestion on even one flow stalls an entire barrier-synchronized epoch. The authors observe that in shared cloud or academic clusters, individual tenants cannot control competing jobs or network infrastructure, so congestion-evasion approaches assuming global scheduling (Cassini) or switch support (adaptive routing, Crux) do not apply. They build REACT, which operates purely in the communication library: it collects per-flow completion times after batches of B=6 epochs, detects steady and erratic congestion, and applies semantics-preserving swaps (global permutation, chunk-local permutation, position-equivalent transforms) that reassign which node occupies which position in the collective graph. Viable transforms are precomputed via a bitvector equivalence check on a time-expanded network representation, pruned by node-degree heuristics, and evaluated with a simple analytical model before empirical confirmation (epsilon=5% accept, tau_r=0.05 revert). REACT is prototyped as a shim over PyTorch/NCCL and evaluated on a shared Slingshot cluster with 4- and 8-GPU jobs, showing 13-38% better algorithm bandwidth under injected congestion and <4% loss without congestion; ns-3 simulations on Clos/star topologies show up to 75% improvement, including under gray link failures. Limitations: gains are measured mostly against their own shim (which trails NCCL without REACT), testbed scale is small (4-8 ranks), enabling REACT on both concurrent jobs can interfere, and no statistical testing is reported.