ForestColl: Throughput-Optimal Collective Communications on Heterogeneous Network Fabrics

on YouTube ↗15m

" summary

ForestColl generates throughput-optimal collective schedules by computing the bottleneck network cut via an optimality binary search, transforming switch topologies into a switch-free logical graph with switch node removal (edge splitting), and applying spanning tree packing to produce broadcast/aggregation trees. Schedule generation runs in polynomial time and maps back with no optimality loss. Evaluation on AMD MI250 and NVIDIA DGX A100 & H100 shows up to 32% higher all-gather throughput and 14–20% faster training iterations versus prior libraries, and much faster schedule synthesis.

AI-written summary · about

" chapters (10)

1. 0:00Introduction
2. 1:01Collective communications
3. 2:06Network topology diversity
4. 3:53ForestColl’s spanning tree
5. 5:41Optimal throughput via binary search
6. 8:34Bottleneck cut for optimality
7. 10:03Spanning tree packing
8. 11:08Switch node removal
9. 12:37Performance results
10. 14:02ForestColl benefits

" related talks

• 14mEfficient Direct-Connect Topologies for Collective CommunicationsArvind Krishnamurthy, Liangyu Zhao, Weiyang Wang, Siddharth Pal, Tapan Chugh, Jason Fantl, Prithwish Basu, Joud Khoury · NSDI '25
• 14mAccelerating PyTorch FSDP Via Overlapping Collectives With In...Nariaki Tateiwa · PyTorch Conference 2025
• 16mAccelerating Distributed Graph Learning by Using Collaborative In-Network...Kai Chen, Junxue Zhang, Zhaoyi Li, Jiawei Huang, Yijun Li, Jingling Liu, Hui Li, Xiaojun Zhu, Shengwen Zhou, Jing Shao, Xiaojuan Lu, Qichen Su, Jianxin Wang, Chee Wei Tan, Yong Cui · USENIX ATC '25
• 21mTransparent and Flexible Network Management for Big Data Processing in the CloudAnupam Das, Cristian Lumezanu, Yueping Zhang, Vishal Singh, Guofei Jiang, Curtis Yu · HotCloud '13
• 17mTopoOpt: Co-optimizing Network Topology and Parallelization Strategy for Distributed...Ying Zhang, Zhihao Jia, Manya Ghobadi, Dheevatsa Mudigere, Weiyang Wang, Moein Khazraee, Zhizhen Zhong, Anthony Kewitsch · NSDI 2023
• 16mFlow Scheduling with Imprecise KnowledgeKai Chen, Guyue Liu, Wenxin Li, Xin He, Yuan Liu, Keqiu Li, Zhao Ge, Zewei Guan, Heng Qi, Song Zhang · 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI '24)
• 16mHeteroSketch: Coordinating Network-wide Monitoring in Heterogeneous and Dynamic NetworksAnup Agarwal, Srinivasan Seshan, Zaoxing Liu · 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI '22)
• 16mTowards Optimal Rack-scale μs-level CPU Scheduling through In-Network Workload...Kai Chen, Hao Wang, Han Tian, Xudong Liao, Junxue Zhang, Guyue Liu, Xinchen Wan, Chaoliang Zeng, Mengyu Ma · USENIX ATC '25