Dualcoll improves gpu cluster communication for large scale training
DualColl: Throughput-Optimal Bandwidth-Bound Collective Communications via Fractional Tree Packing
Distributed, Parallel, and Cluster ComputingData Structures and AlgorithmsNetworking and Internet Architecture
Summary
Training large AI models often involves many computers talking to each other, and this talking can be slowed down by limited network speeds. The authors created DualColl, a method that plans these communications in a mathematically optimal way to make the best use of network bandwidth. It directly targets a common communication step called AllReduce, improving speed without needing extra hardware changes. DualColl also works with different network types and can handle multiple communication groups at once.
What this means in practice
- •For distributed system engineers: Optimize communication schedules in GPU clusters to maximize throughput of bandwidth-intensive collective operations like AllReduce.
- •For high performance computing operators: Improve network bandwidth utilization in multi-network setups (NVLink, InfiniBand, Ethernet) to speed up large-scale distributed training workloads.
Authors
Namir Ballan, Reuven Cohen
Abstract
Large-scale distributed training increasingly makes collective communication bandwidth-bound. In modern GPU clusters, communication libraries such as NCCL implement collectives including AllReduce over heterogeneous interconnects such as NVLink, InfiniBand, and Ethernet, making efficient use of available network bandwidth a central systems challenge. ForestColl showed that collective communication on such fabrics can be formulated using fractional tree packing; its scalable polynomial-time construction is developed for AllGather, with AllReduce obtained by composing AllGather and ReduceScatter. We present DualColl, which targets bandwidth-bound AllReduce directly. Under the tree-based AllReduce model, DualColl applies a Garg--Könemann-style multiplicative-weights algorithm and, for any $0<ε<1$, computes a feasible schedule whose throughput is at least $(1-ε)^2$ of the optimal AllReduce throughput. Its key component is an exact minimum-cost collective-tree oracle that projects physical-link dual prices onto a logical graph of participating ranks, reducing each iteration to shortest-path computations followed by a minimum spanning tree. We further extend the framework to local equal-next-hop packet-sprayed routing and to networks without explicit per-tree bandwidth control. For the latter, we introduce a tree-coupled max-min bandwidth-sharing model and show that tree duplication approximates an explicit fractional allocation with a provable accuracy-complexity tradeoff. Finally, we extend the fractional-packing framework to additional collective operations and multiple concurrent collective groups.