Lionel M. Ni
Philip K. McKinley
Department of Computer Science
Michigan State University
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.