# Synthesizing Optimal Collective Algorithms

arXiv: https://arxiv.org/abs/2008.08708 · HTML: https://mlsanity.com/paper/2008.08708/

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Aug 2020.

## Built on by (most cited first, 30 of 30)

- [Software-Hardware Co-design for Fast and Scalable Training of Deep Learning Recommendation Models](https://mlsanity.com/paper/2104.05158/) (2021)
- [TACCL: Guiding Collective Algorithm Synthesis using Communication Sketches](https://mlsanity.com/paper/2111.04867/) (2021)
- [MegaScale-Infer: Serving Mixture-of-Experts at Scale with Disaggregated Expert Parallelism](https://mlsanity.com/paper/2504.02263/) (2025)
- [On Optimizing the Communication of Model Parallelism](https://mlsanity.com/paper/2211.05322/) (2022)
- [Themis: A Network Bandwidth-Aware Collective Scheduling Policy for Distributed Training of DL Models](https://mlsanity.com/paper/2110.04478/) (2021)
- [T3: Transparent Tracking & Triggering for Fine-grained Overlap of Compute & Collectives](https://mlsanity.com/paper/2401.16677/) (2024)
- [Communication-Efficient Large-Scale Distributed Deep Learning: A Comprehensive Survey](https://mlsanity.com/paper/2404.06114/) (2024)
- [MSCCL++: Rethinking GPU Communication Abstractions for AI Inference](https://mlsanity.com/paper/2504.09014/) (2025)
- [Swing: Short-cutting Rings for Higher Bandwidth Allreduce](https://mlsanity.com/paper/2401.09356/) (2024)
- [Efficient Direct-Connect Topologies for Collective Communications](https://mlsanity.com/paper/2202.03356/) (2022)
- [UniEP: Unified Expert-Parallel MoE MegaKernel for LLM Training](https://mlsanity.com/paper/2604.19241/) (2026)
- [Synthesizing Optimal Parallelism Placement and Reduction Strategies on Hierarchical Systems for Deep Learning](https://mlsanity.com/paper/2110.10548/) (2021)
- [MCR-DL: Mix-and-Match Communication Runtime for Deep Learning](https://mlsanity.com/paper/2303.08374/) (2023)
- [Enhancing Large-Scale AI Training Efficiency: The C4 Solution for Real-Time Anomaly Detection and Communication Optimization](https://mlsanity.com/paper/2406.04594/) (2024)
- [Communication Optimization for Distributed Training: Architecture, Advances, and Opportunities](https://mlsanity.com/paper/2403.07585/) (2024)
- [Robust Heuristic Algorithm Design with LLMs](https://mlsanity.com/paper/2510.08755/) (2025)
- [ForestColl: Throughput-Optimal Collective Communications on Heterogeneous Network Fabrics](https://mlsanity.com/paper/2402.06787/) (2024)
- [Lion Cub: Minimizing Communication Overhead in Distributed Lion](https://mlsanity.com/paper/2411.16462/) (2024)
- [Efficient AllReduce with Stragglers](https://mlsanity.com/paper/2505.23523/) (2025)
- [Bine Trees: Enhancing Collective Operations by Optimizing Communication Locality](https://mlsanity.com/paper/2508.17311/) (2025)
- [GF-DiT: Scheduling Parallelism for Diffusion Transformer Serving](https://mlsanity.com/paper/2606.13501/) (2026)
- [Bidirectional Reactive Programming for Machine Learning](https://mlsanity.com/paper/2311.16977/) (2023)
- [The Big Send-off: Scalable and Performant Collectives for Deep Learning](https://mlsanity.com/paper/2504.18658/) (2025)
- [Load Balancing for AI Training Workloads](https://mlsanity.com/paper/2507.21372/) (2025)
- [Enabling Reconfiguration-Communication Overlap for Collective Communication in Optical Networks](https://mlsanity.com/paper/2510.19322/) (2025)
- [FreeScale: Distributed Training for Sequence Recommendation Models with Minimal Scaling Cost](https://mlsanity.com/paper/2604.24073/) (2026)
- [HetCCL: Enabling Collective Communication For Mixed-Vendor Heterogeneous Clusters](https://mlsanity.com/paper/2605.31000/) (2026)
- [Tuning Collective Patterns to Alleviate Congestion in Shared AI Clusters](https://mlsanity.com/paper/2609.04417/) (2026)
- [The Life of a Token: from Words to Bits on the Wire](https://mlsanity.com/paper/2609.19924/) (2026)
- [Purlin: Separating Orchestration from the Datapath of Collectives](https://mlsanity.com/paper/2609.36954/) (2026)

## Abstract (arXiv)

Collective communication algorithms are an important component of distributed computation. Indeed, in the case of deep-learning, collective communication is the Amdahl's bottleneck of data-parallel training. This paper introduces SCCL (for Synthesized Collective Communication Library), a systematic approach to synthesize collective communication algorithms that are explicitly tailored to a particular hardware topology. SCCL synthesizes algorithms along the Pareto-frontier spanning from latency-optimal to bandwidth-optimal implementations of a collective. The paper demonstrates how to encode SCCL's synthesis as a quantifier-free SMT formula which can be discharged to a theorem prover. We further demonstrate how to scale our synthesis by exploiting symmetries in topologies and collectives. We synthesize and introduce novel latency and bandwidth optimal algorithms not seen in the literature on two popular hardware topologies. We also show how SCCL efficiently lowers algorithms to implementations on two hardware architectures (NVIDIA and AMD) and demonstrate competitive performance with hand optimized collective communication libraries.