Hardware-Based Multicast with Global Load Balance on k-ary n-trees

The multicast operation is used commonly in parallel applications and can be used to support several other collective communication operations. A significant performance improvement can be achieved by supporting multicast operations at the hardware level. In this paper, we propose two parent selecting strategies which use global information to reduce the conflict among different multicast operations on k-ary n-trees. We first define an equivalence relation to divide the switches at each stage into several equivalence classes. Then we prove that the switches, which are at the same stage and are passed through by the same multicast tree, belong to the same equivalence class. Based on the study, two least loaded parent selecting strategies are developed. The proposed strategies are evaluated through simulation experiments. The results indicate that the proposed strategies lower the multicast latency and increase the multicast throughput significantly.