Load-Balanced Multicast Routing for Large-Scale Infiniband Network

doi:10.3778/j.issn.1002-8331.2009-0276

Abstract

Abstract: In high performance computing, multicast operations supported by hardware have an important impact on the performance of applications. Among the existing two kinds of multicast routing algorithms in Infiniband network, MINIHOP-MC does not consider the problem of routing load balance, which leads to large edge forwarding index（EFI）, and seriously affects the performance of multicast messages. Although SSSP-MC partially considers the problem of routing balance, it runs for very long time and cannot meet the needs of large-scale interconnection network. In this paper, a load balanced multicast routing algorithm called FULB-MC is proposed, which can be used in large-scale interconnection networks with a large number of multicast groups. FULB-MC builds multicast tree from bottom to up, and uses two load balancing strategies to select multicast routes according to local load information. A new multicast group join/leave mechanism is also proposed to avoid frequent computation of multicast routes. It tests FULB-MC heavily for several topologies and communication modes. The results show that in terms of running time, FULB-MC is significantly lower than SSSP-MC; and in terms of link EFI index, FULB-MC performs much better than MINIHOP-MC, and almost as good as SSSP-MC.

Key words: multicast routing, load balancing, large-scale interconnection networks, Infiniband

摘要： 高性能计算中，硬件支持的多播操作对应用程序性能具有至关重要的影响。Infiniband网络中现有的两类多播路由算法中，MINIHOP-MC未考虑路由均衡性问题，导致链路edge forwarding index（EFI）指数很大，严重影响多播消息性能；SSSP-MC虽然部分考虑了路由均衡性问题，但其运行时间很长，不能满足超大规模互连网络的需求。提出一种负载均衡的快速多播路由算法FULB-MC，可用于存在大量多播组的超大规模互连网络环境。该算法采用自底向上的多播树构建方法，并综合利用两种负载均衡策略根据局部负载信息进行多播路由选择。还提出了新的加入/离开多播组机制，避免频繁计算多播路由问题。在各种拓扑结构、各种通信模式下对FULB-MC进行了大量测试。结果表明，在运行时间方面，FULB-MC显著低于SSSP-MC；在链路EFI指数方面，FULB-MC明显优于MINIHOP-MC，而与SSSP-MC基本相当。

关键词: 多播路由, 负载均衡, 超大规模互连网络, Infiniband

CHEN Shuping, ZHOU Huilin, HE Wangquan, QI Fengbin. Load-Balanced Multicast Routing for Large-Scale Infiniband Network[J]. Computer Engineering and Applications, 2022, 58(5): 138-147.

陈淑平, 周慧霖, 何王全, 漆锋滨. 用于超大Infiniband网络的负载均衡多播路由[J]. 计算机工程与应用, 2022, 58(5): 138-147.

References

[1] AJIMA Y，KAWASHIMA T，OKAMOTO T，et al.The Tofu interconnect D[C]//2018 IEEE International Conference on Cluster Computing.Piscataway：IEEE，2018：646-654.
[2] SORENSEN B.Japan’s flagship 2020 “Post-K” system[J].Computing in Science & Engineering，2019，21（1）：48-49.
[3] ALMASI G，HEIDELBERGER P，ARCHER C J，et al. Optimization of MPI collective communication on BlueGene/L systems[C]//Proc of the 19th Annual International Conference on Supercomputing.New York：ACM，2005：253-262.
[4] CHUNDURI S，PARKER S，BALAJI P，et al.Characteri-zation of MPI usage on a production supercomputer[C]//Proc of 2018 International Conference for High Performance Computing，Networking，Storage and Analysis. Piscataway：IEEE，2018.
[5] CHAN E，HEIMLICH M，PURKAYASTHA A，et al.Collective communication：theory，practice，and experience[J].Concurrency & Computation Practice & Experience，2010，19（13）：1749-1783.
[6] FARAJ A，KUMAR S，SMITH B，et al.MPI collective communications on the Blue Gene/P supercomputer：algorithms and optimizations[C]//Proceedings of the 23th International Conference on Supercomputing.New York： ACM，2009：489-490.
[7] HOEFLER T，LUMSDAINE A，REHM W.Implementation and performance analysis of non-blocking collective operations for MPI[C]//Proceedings of the SC07，2007.
[8] HUNOLD S，CARPEN-AMARIE A.Autotuning MPI collectives using performance guidelines[C]//International Conference on High Performance Computing in Asia-pacific Region.New York：ACM，2018.
[9] THAKUR R，RABENSEIFNER R，GROPP W.Optimization of collective communication operations in MPICH[J].International Journal of High Performance Computing Applications，2005，19（1）：49-66.
[10] ZIMMER C，ANDRE W，CLARK M A，et al.An evaluation of the CORAL interconnects[C]//the International Conference for High Performance Computing，Networking，Storage and Analysis.New York：ACM，2019.
[11] InfiniBand Trade Association.InfiniBand architecture specification volume 1，release 1.3[EB/OL].[2020-08-20].https：//www.infinibandta.org/.
[12] The OpenFabrics Alliance Web Site.OpenFabrics software[EB/OL].[2020-08-20].https：//www.openfabrics.org/.
[13] HEYDEMANN M C，MEYER J C，SOTTEAU D.On forwarding index of networks[J].Discrete Applied Mathe-matics，1989，23（2）：103-123.
[14] SAAD R.Complexity of the forwarding index problem[J].SIAM Journal on Discrete Mathematics，1993，6（3）：418-427.
[15] SKEIE T，LYSNE O，THEISS I.Layered shortest path （LASH） routing in irregular system area networks[C]//Proc of IPDPS’02.Piscataway：IEEE，2002.
[16] LYSNE O，SKEIE T，REINEMO S A，et al.Layered routing in irregular networks[J].IEEE Transactions on Parallel & Distributed Systems，2005，17（1）：51-65.
[17] DOMKE J，HOEFLER T，MATSUOKA S.Routing on the dependency graph：a new approach to deadlock-free high-performance routing[C]//Proc of HPDC’16.New York：ACM，2016：3-14.
[18] HOEFLER T，SCHNEIDER T，LUMSDAINE A.Optimized routing for large-scale InfiniBand networks[C]// Proc of 17th IEEE Symposium on High Performance Interconnects.Piscataway：IEEE，2009：103-111.
[19] DOMKE J，HOEFLER T，NAGEL W E.Deadlock-free oblivious routing for arbitrary topologies[C]//Proc of 2011 IEEE International Parallel & Distributed Processing Symposium.Piscataway：IEEE，2011：616-627.
[20] VALERIO M，MOSER L E，MELLIAR-SMITH P M.Recursively scalable fat-trees as interconnection networks[C]//Proc of IEEE International Phoenix Conference on Computers & Communications.Piscataway：IEEE，1994.
[21] PETRINI F，VANNESCHI M.K-ary n-trees：high performance networks for massively parallel architectures[C]//Proc of 11th International Parallel Processing Symposium.Piscataway：IEEE，1997：87-93.
[22] KIM J，DALLY W J，SCOTT S，et al.Technology-driven，highly-scalable dragonfly topology[J].ACMSIGARCH Computer Architecture News，2008，36（3）：77-88.
[23] TIAN M，GU W D，PAN J S，et al.Performance analysis and optimization of PalaBos on Petascale Sunway BlueLight MPP supercomputer[J].Procedia Engineering，2013，61：241-245.
[24] FU H H，LIAO J F，YANG J Z，et al.The Sunway Taihu-Light supercomputer：system and applications[J].Science China Information Sciences，2016，59（7）：072001.