Turn grouping for multicast in wormhole-routed mesh networks supporting the turn model

Multicast is an important collective communication in scalable parallel com puters. One efficient scheme to perform multicast is multidestination messa ging[8]. In multidestination messaging, destination nodes of a multicast ar e partitioned into disjoint groups. Nodes in each group are reached with a multidestination message that conforms to the base routing algorithm of the system. A systematic way of partitioning the nodes is critical to the effi ciency of multidestination messaging. In this paper we propose a node group ing method, called turn grouping, for partitioning the destination nodes in a multicast. Turn grouping is general in the sense that it supports any ba se routing algorithm derivable from the turn model [5]. Given such a base r outing algorithm and the corresponding prohibited turns, turn grouping can systematically produce a proper schedule for multicasting the message. We e valuated the performance of turn grouping using three typical turn model-ba sed routing algorithms. The simulation results show that our approach perfo rms better than the Umesh [12] and the Hamiltonian-path [8] algorithms.