Practical and Efficient Customized Multicast Routing in Fat-Tree Topology

In high performance computing, multicast routing algorithms have important impact on the performance of collective operations supported by hardware. As the supercomputers become larger and larger, the number of MCGs (multicast groups) increases rapidly, and it may exceed the number of MFT (multicast forwarding table) entries supported by hardware. However, the existing multicast routing algorithms either do not provide solutions to this problem, or have problems such as heavy time overhead and variability for multicast routing. To address this problem, we first quantitatively study the number of conflict-free multicast spanning trees in fat-tree, and propose a practical and efficient customized multicast routing algorithm called C-MR4LMS (customized multicast routing for limited multicast forwarding table size). When constructing multicast tree, the MCG is statically mapped to a spanning tree according to the MGID (multicast global identification); thus we can construct the multicast tree quickly. When merging multicast trees, only the ones using the same spanning tree need to be merged, and the route of the merged MCGs will not be changed. Then we propose two methods to reduce the confliction of multicast routes. One is the layered MGID allocation strategy to avoid the situation that the terminal node uses the same color to join multiple MCGs. The other one is the interference-free node allocation strategy for different jobs to ensure that the MCGs of two jobs do not interfere with each other. Finally, we test the performance of C-MR4LMS in ibsim simulator and Sunway exascale prototype system and obtain the satisfying results. In particular, the running time of the algorithm compared with the existing algorithms is significantly reduced, and we get up to 94% reduction in runtime.