InfiniBand中面向有限多播表条目数的多播路由算法

Multicast Routing Algorithm for Limited MFT Size in InfiniBand

高性能计算中,硬件支持的多播操作对集合通信的性能具有重要影响.随着超级计算机系统规模的不断扩大,多播组的个数急剧增加,可能会超过硬件支持的多播表条目数,而现有的多播路由算法没有给出相应的解决方案.提出一种面向有限多播表条目数的多播路由算法MR4LMS(multicast routing for limited MFT size),该算法使用先构造后染色、先染色后构造2种多播树构建方法,可显著降低所需的多播表条目数;而在多播表条目数不足时,通过合并算法将多个相似的多播组合并到一起以进一步减少所需的多播表条目数.在多种典型拓扑结构及通信模式下对MR4LMS进行了测试,结果表明仅需设置256个多播表条目就能够支持数千甚至数万个多播组,满足典型应用的需求.还对多播路由算法的最大EFI(edge forwarding index)及运行时间进行了测试,获得了令人满意的结果,表明MR4LMS可用于超大规模互连网络.

In high performance computing,multicast operations supported by hardware have important impact on the performance of collective communication.As the supercomputer becomes larger and larger,the number of MCGs(multicast groups)increases rapidly also,and may exceed the number of MFT(multicast forwarding table)entries supported by hardware.However,the existing multicast routing algorithms do not provide solutions to this problem.This paper proposes a multicast routing algorithm for limited MFT size in InfiniBand called MR4LMS(multicast routing for limited MFT size).The algorithm uses two different methods,called FBTC(first build then color)and FCTB(first color then build)respectively,to build the multicast tree,in order to reduce the number of MFT entries as more as possible.When the number of MFT entries is not enough,several similar MCGs can be merged together by a merge algorithm to further reduce the required MFT entries.MR4LMS is tested under various typical topologies and communication patterns.The results show that it only needs 256 MFT entries to support thousands or even tens of thousands of MCGs to meet the requirements of typical communication patterns.In addition,we test the maximum EFI(edge forwarding index)and the running time of MR4LMS and obtain the satisfying performance result,which show that the MR4LMS can be used in large-scale interconnect networks.