ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2022, Vol. 59 ›› Issue (4): 864-881.doi: 10.7544/issn1000-1239.20200767

• 信息安全 • 上一篇    下一篇

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

陈淑平,何王全,李祎,漆锋滨   

  1. (国家并行计算机工程技术研究中心 北京 100190) (chenshuping_hit@163.com)
  • 出版日期: 2022-04-01
  • 基金资助: 
    国家重点研发计划项目(2017YFB0202004)

Multicast Routing Algorithm for Limited MFT Size in InfiniBand

Chen Shuping, He Wangquan, Li Yi, Qi Fengbin   

  1. (National Research Center of Parallel Computer Engineering & Technology, Beijing 100190)
  • Online: 2022-04-01
  • Supported by: 
    This work was supported by the National Key Research and Development Program of China (2017YFB0202004).

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

关键词: 多播路由算法, 多播组, 有限多播表条目数, 集合操作, InfiniBand

Abstract: 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.

Key words: multicast routing algorithm, multicast group, limited multicast table size, collective operations, InfiniBand

中图分类号: