Multicast time-expanded graph-based collective communication scheduling algorithm

Liu Fei; Wang Peng; Ma Han; Li Ye; Li Hongyan

doi:10.11959/j.issn.1000-436x.2026062

Chinese

您当前的位置：

首页 >

文章列表页 >

Multicast time-expanded graph-based collective communication scheduling algorithm

Papers | 更新时间：2026-05-07

- Multicast time-expanded graph-based collective communication scheduling algorithm
- Journal on Communications Vol. 47, Issue 4, Pages: 67-79(2026)
- 作者机构：
  
  1.西安电子科技大学空天地一体化综合业务网全国重点实验室，陕西西安 710071
  2.新加坡科技设计大学，新加坡 487372
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(62371374)
- DOI：10.11959/j.issn.1000-436x.2026062
  CLC： TP393.0
- Received：27 December 2025，
  
  Revised：2026-03-01，
  
  Accepted：02 March 2026，
  
  Published：20 April 2026
- 稿件说明：
移动端阅览
刘飞,王鹏,麻涵等.基于组播时间扩展图的集合通信编排算法[J].通信学报,2026,47(04):67-79.

Liu Fei,Wang Peng,Ma Han,et al.Multicast time-expanded graph-based collective communication scheduling algorithm[J].Journal on Communications,2026,47(04):67-79.
刘飞,王鹏,麻涵等.基于组播时间扩展图的集合通信编排算法[J].通信学报,2026,47(04):67-79. DOI： 10.11959/j.issn.1000-436x.2026062.

Liu Fei,Wang Peng,Ma Han,et al.Multicast time-expanded graph-based collective communication scheduling algorithm[J].Journal on Communications,2026,47(04):67-79. DOI： 10.11959/j.issn.1000-436x.2026062.

摘要

集合通信时延已成为大模型分布式训练的瓶颈。针对现有算法拓扑感知不足、调度复杂度高等问题，提出一种基于组播时间扩展图的集合通信编排算法。通过构建组播时变图模型，刻画节点间的拓扑关系及时隙冲突约束，将集合通信编排问题转化为时变图中组播路径搜索问题，实现路由与时隙联合规划。仿真结果表明，所提算法完成时间接近最优，同时显著降低计算复杂度，适用于大规模分布式训练场景。

Abstract

Collective communication latency has become a major performance bottleneck in large-scale distributed training. To address the limitations of existing algorithms in terms of insufficient topology awareness and high computational complexity

a topology-aware collective communication scheduling algorithm based on multicast time-expanded graph was proposed. By constructing a multicast time-varying graph model

both network topology constraints and time-slot conflict constraints were explicitly captured. The collective communication scheduling problem was then transformed into a multicast path search problem on the time-varying graph

enabling joint optimization of routing and time slot planning. Simulation results demonstrate that the proposed algorithm achieves near-optimal communication completion time while significantly reducing computational complexity

making it suitable for large-scale distributed training scenarios.

关键词

Keywords

references

高翔 , 董斌 , 肖晴 , 等 . 智算场景下集合通信库的挑战与发展趋势 [J ] . 电信科学 , 2025 , 41 ( 4 ): 81 - 94 .

Gao X , Dong B , Xiao Q , et al . Challenges and development trends of collective communication libraries in intelligent computing scenarios [J ] . Telecommunications Science , 2025 , 41 ( 4 ): 81 - 94 .

Liu T R , Hei C Y , Li F L , et al . ResCCL: resource-efficient scheduling for collective communication [C ] // Proceedings of the ACM SIGCOMM 2025 Conference . New York : ACM Press , 2025 : 55 - 70 .

Hui L H , Yang W , Wu F , et al . DirectReduce: a scalable ring AllReduce offloading architecture for torus topologies [J ] . IEEE Internet of Things Journal , 2025 , 12 ( 16 ): 32951 - 32964 .

Zhang Z X , Wen Y B , Lyu H Q , et al . AI computing systems for large language models training [J ] . Journal of Computer Science and Technology , 2025 , 40 ( 1 ): 6 - 41 .

Geng J K , Li D , Cheng Y , et al . HiPS: hierarchical parameter synchronization in large-scale distributed machine learning [C ] // Proceedings of the 2018 Workshop on Network Meets AI & ML . New York : ACM Press , 2018 : 1 - 7 .

Jiang Y H , Gu H X , Lu Y F , et al . 2D-HRA: two-dimensional hierarchical ring-based all-reduce algorithm in large-scale distributed machine learning [J ] . IEEE Access , 2020 , 8 : 183488 - 183494 .

Pjesivac G J . Towards automatic and adaptive optimizations of MPI collective operations [D ] . Knoxville : The University of Tennessee, Knoxville , 2007 .

Sanders P , Speck J , Träff J L . Two-tree algorithms for full bandwidth broadcast, reduction and scan [J ] . Parallel Computing , 2009 , 35 ( 12 ): 581 - 594 .

Weingram A , Li Y K , Qi H , et al . xCCL: a survey of industry-led collective communication libraries for deep learning [J ] . Journal of Computer Science and Technology , 2023 , 38 ( 1 ): 166 - 195 .

Cavazzoni C . EURORA: a European architecture toward exascale [C ] // Proceedings of the Future HPC Systems: the Challenges of Power-Constrained Performance . New York : ACM Press , 2012 : 1 - 4 .

Cho M , Finkler U , Serrano M , et al . BlueConnect: decomposing all-reduce for deep learning on heterogeneous network hierarchy [J ] . IBM Journal of Research and Development , 2019 , 63 ( 6 ): 1 - 11 .

Kalb J L , Lee D S . Network topology analysis [R ] . 2008 .

Cai Z X , Liu Z Y , Maleki S , et al . Synthesizing optimal collective algorithms [C ] // Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming . New York : ACM Press , 2021 : 62 - 75 .

Shah A , Chidambaram V , Cowan M , et al . TACCL: Guiding collective algorithm synthesis using communication sketches [C ] // Proceedings of the 20th NSDI-2023 USENIX Symposium on Networked Systems Design and Implementation . Berkeley : USENIX Association , 2023 : 593 - 612 .

Liu X T , Arzani B , Kakarla S K R , et al . Rethinking machine learning collective communication as a multi-commodity flow problem [C ] // Proceedings of the ACM SIGCOMM 2024 Conference . New York : ACM Press , 2024 : 16 - 37 .

Takahashi H , Matsuyama A . An approximate solution for steiner problem in graphs [J ] . Math. Japonica , 1980 , 24 ( 6 ): 573 - 577 .

GUROBI optimization , LLC . Gurobi optimizer reference manual [R ] . 2024 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Distributed parallel training technology for large-scale model with heterogeneous computing resources

Large-scale post-disaster user distributed coverage optimization based on multi-agent reinforcement learning

Time deterministic routing algorithm and protocol based on time-varying graph over the space-ground integrated network

Related Author

BAN Yourong

WANG Sheng

HUANG Lei

ZHANG Hao

ZHANG Xiaoguang

DI Xinkai

XU Si

HUANG Zixiao

Related Institution

China Mobile Research Institute

Infinigence AI

School of Artificial Intelligence, Beijing University of Posts and Telecommunications

Lab of BLOS Trusted Information Transmission, Chongqing University of Posts and Telecommunications

School of Information and Communication Engineering, Beijing University of Posts and Telecommunications

AI问答

Postal code：100079
Tel：（010）53879206 Email：tmw@bjxintong.com.cn
Technical support is provided by Beijing Founder electronics co., LTD 京ICP备09082226号-64 京公网安备11010602201714号
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰