Multicast Routing Algorithm for Limited MFT Size in InfiniBand

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.