Deadlock-Free Multicast Wormhole Routing in 2D-Mesh Multicomputers

Multicast communication services, in which the same message is delivered from a source node to an arbitrary number of destination nodes, are being provided in new generation multicomputers. Broadcast is a special case of multicast in which a message is delivered to all nodes in the network. The nCUBE-2 is the first multicomputer that directly supports broadcast using wormhole routing. This paper shows that the broadcast wormhole routing adopted in the nCUBE-2 is not deadlock-free, a property that is critical to wormhole routed networks. Four multicast wormhole routing strategies for 2D-mesh multicomputers are proposed and studied. All of the algorithms are shown to be deadlock-free. These are the first deadlock-free multicast wormhole routing algorithms ever proposed. A simulation study has been conducted that compares the performance of these multicast algorithms under dynamic network traffic conditions in a 2D-mesh. The results indicate that a dual-path routing algorithm offers bette..