Strategies for Path-Based Multicasting in Wormhole-Routed Meshes

Multicasting is an information dissemination problem which consists, for a processor of a distributed memory parallel computer, to send a same message to a subset of processors. In this paper, we propose new multicast algorithms for a mesh network using wormhole routing with the path-based facility. These new algorithms perform generally faster than algorithms previously described in the literature under the same model. We used, as criteria to compare algorithms, the off-line computation time necessary to prepare the multicast, and the communication time required to complete the multicast. Key words: multicasting, routing, wormhole, multiprocessor, parallel computers. * Both authors are supported by the research programs Architecture des Nouvelles Machines and Parall'elisme, R'eseaux, Syst`emes of the CNRS. Subsets of this paper appeared in the Proceedings of the 23rd Annual International Conference on Parallel Processing, Chicago, Il, 1994, and in the proceedings of the 6th IEEE Symp..