OPTIMAL MULTICAST COMMUNICATION IN WORMHOLE-ROUTED TORUS NETWORKS

This paper presents efficient algorithms that implement one-to-many, o r multicast, communication in wormhole-routed torus networks. By explo iting the properties of the snitching technology and the use of virtua l channels, a minimum-time multicast algorithm is presented for n-dime nsional torus networks that use deterministic, dimension-ordered routi ng of unicast messages. The algorithm can deliver a multicast message to m - 1 destinations in [log(2) m] message-passing steps, while avoid ing contention among the constituent unicast messages. Performance res ults of a simulation study on torus networks with up to 4096 nodes are also given.