Title: OptCCL: Scalable Synthesis of Optimal Collective Communication Algorithms
Authors: Richard Shapley, Rachit Agarwal, and David Shmoys (Cornell University)
Scribe: Ziyi Wang (Xiamen University)
Introduction:
Collective communication is a critical component of modern machine learning training and inference systems. It is used to synchronize gradients, model parameters, and optimizer states across GPUs, and its communication efficiency directly affects end-to-end training and inference performance as well as GPU utilization. As machine learning clusters continue to scale, the number of GPUs keeps increasing, intra-host and inter-host interconnects become increasingly complex, and scenarios in which multiple collective communication operations or even multiple tenants share network resources are becoming more common. Against this background, designing optimal collective communication algorithms for specific hardware and network topologies has become increasingly difficult. Existing approaches generally struggle to achieve optimality, scalability, and generality at the same time: heuristic approaches can scale to large systems but cannot guarantee optimality, whereas approaches based on SMT, MILP, or flow optimization can search for optimal solutions but are often limited to relatively small GPU clusters or a restricted set of communication patterns and hardware topologies.
The paper therefore asks the following central question: Can collective communication algorithms with optimality guarantees be synthesized scalably while retaining generality?
Key idea and contribution:
The authors propose OptCCL, a general framework that automatically synthesizes optimal collective communication algorithms for a given hardware configuration and network topology. It aims to achieve both algorithmic optimality and synthesis scalability for large GPU clusters.
Existing approaches typically solve data routing between GPUs and link-level scheduling of data chunks jointly, causing the optimization problem to grow rapidly with the number of GPUs, data chunks, and time steps. OptCCL shows that, when minimizing collective completion time, routing and scheduling can be decoupled without sacrificing optimality. The core optimization problem can therefore be reduced to spatial routing, after which an optimal schedule can be constructed.
Based on this insight, OptCCL develops a multicommodity-flow formulation. As shown in the next figure, it first abstracts GPUs, NICs, switches, and physical links into a bandwidth-constrained directed graph. It then constructs a time-expanded network that represents data transmission and storage across discrete time layers, providing a unified mathematical model for routing and scheduling.
Unlike conventional formulations that treat each sender as a commodity, OptCCL models every sender-destination pair as an independent commodity. This allows standard flow-conservation constraints to describe data-transmission paths, while capacity constraints over selected sets of flows capture data replication, sharing, and reduction in collective communication. To improve synthesis efficiency for large-scale problems, OptCCL further combines linear programming relaxation, iterative strengthening, and optimality-preserving symmetry reduction to reduce the numbers of variables, constraints, and repeated subproblems. The resulting framework supports existing collective operations and heterogeneous hardware capabilities, optimizes secondary objectives such as total data transferred while preserving optimal collective completion time, and jointly handles multiple concurrent collectives that share host and network resources.
Evaluation:
The authors evaluate OptCCL through simulation on a range of scale-up and scale-out GPU topologies, including A100 systems with eight GPUs per host and DOE systems with four GPUs per host, both using multi-rail inter-host networks. They consider both individual and concurrent collectives and compare OptCCL against TE-CCL, SyCCL, and TACCL. Performance is measured using algorithmic bandwidth (AlgBW), while synthesis time is used to evaluate synthesis scalability.
For AllGather, OptCCL achieves 1-5x, 1-1.6x, and 1.2-18x higher AlgBW than TE-CCL, SyCCL, and TACCL, respectively, while reducing synthesis time by about 3-60x on larger topologies. For All-to-All, OptCCL improves AlgBW by up to about 1.3x over TE-CCL and SyCCL and reduces synthesis time by 2-500x.
The authors additionally evaluate multiple concurrent collectives on a topology containing 64 A100 GPUs. Jointly optimizing multiple collective operations performs substantially better than optimizing each operation independently and then executing them sequentially.
Overall, OptCCL can synthesize collective communication algorithms with optimality guarantees for clusters containing hundreds of GPUs within tens of minutes. In contrast, some existing approaches can handle only tens of GPUs within three hours, while other approaches scale to larger systems but generate algorithms that deviate substantially from the optimum.
Q: I think your assumption is that the data has a normal distribution, so you can do this compression. Do you have any evidence to show that the data has this kind of distribution? Does this assumption hold for more workloads?
A: We measured this empirically. In large language models, we have several different layers, and different layers often exhibit different kinds of data distributions. Some values are extremely small, while some are extremely large, and that is the reason for the gradient skewness. I think this is general, at least for LLM workloads. For spatial locality, the intuition is that within a layer, the data often follows a similar distribution. But for different layers, or different parts of the weights or tensors, they can have different distributions. So adjacent entries within one layer or the same weight matrix often exhibit similar distributions or similar magnitudes, while entries that are far away may exhibit different magnitudes. That is why we think this property holds, at least for LLM workloads.
Personal thoughts
I consider the decoupling of routing and scheduling to be the most valuable aspect of the paper: this result substantially reduces problem complexity while retaining a rigorous optimality guarantee. The paper is not restricted to a single collective or idealized hardware, but further considers heterogeneous components and concurrent communication, which strengthens its systems contribution. However, the current evaluation is primarily simulation-based. A natural next step is to integrate OptCCL into production collective communication libraries such as NCCL or RCCL and validate its end-to-end benefits on real training and inference workloads. It is also worth exploring how to account for propagation latency for small messages and how to optimize more complex objectives such as weighted completion time.