Multicast Communication in Multicomputers

Supported in part by NSF grant MIP-9204066.

Principal Investigators:

Lionel M. Ni
Philip K. McKinley
Abdol-Hossein Esfahanian
Department of Computer Science
Michigan State University

Project Description. This research project investigated one-to-many, or multicast, communication in multicomputers. The project comprised two major parts. The first component investigated how to provide multicast communication in existing systems that do not offer hardware multicast support. The second component addressed architectural support for multicast communication, including a study of switching architectures and multicast routing. Most of the work in the project targeted massively parallel processors (MPPs) that adopt the wormhole routing switching strategy; example systems include the Intel Paragon, MIT J-machine, and Cray T3D. The specific contributions of the project are discussed in turn.

Traditionaly, most MPPs have supported only point-to-point communication in hardware. In these environments, multicast must be implemented in software by sending multiple unicast (single destination) messages. The multicast project produced several unicast-based multicast algorithms (e.g., U-cube, U-mesh, U-torus) for one-port wormhole-routed systems. The algorithms are applicable to commercial multicomputers, and we demonstrated their performance advantage through experimental studies. Also, we developed unicast-based multicast algorithms for so-called multi-port architectures; multi-port systems allow nodes to transmit/receive multiple messages simultaneously.

Hardware-supported multicast in wormhole-routed MPPs can be either tree-based or path-based. We showed that tree-based multicast communication, which is adopted in the nCUBE-2, a wormhole-routed hypercube multicomputer, is not deadlock-free. This result led us to develop the path-based approach. In this deadlock-free method, the destination set is partitioned at the source, and separate copies are sent on different outgoing channels; each copy visits a set of destinations sequentially. Path-based routing is applicable to many topologies, including hypercubes and meshes. We proposed and studied four path-based multicast routing strategies for two-dimensional (2D) mesh multicomputers and extended our study to include other topologies and adaptive path-based routing algorithms. To assist in this research, we developed an efficient simulator for wormhole-routed systems, called MultiSim, which has been distributed to other researchers and used at other universities. We have also developed multicast algorithms for future systems based on multichannel optical interconnects.