Deadlock-free multicast wormhole routing in multicomputer networks
Xiaola Lin, Lionel Ming-shuan Ni · 1991
Efficient routing of messages is the key to the performance of multicomputers. Multicast communication refers to the delivery of the same message from a source node to an arbitrary number of destination nodes. Wormhole routing is the most promising switching technique used in new generation multicomputers. In this paper, we present multicast wormhole routing methods for multicomputers adopting 2D-mesh and hypercube topologies. The dual-path routing algorithm requires less system resource, while the multi-path routing algorithm creates less traffic. More importantly, both routing algorithms are deadlock-free, which is essential to wormhole networks. Keywords: Multicomputers, Heuristic Algorithms, Hypercube Topology, 2D Mesh Topology, Multicast Communication, Wormhole Routing, NP-completeness, Grid Graphs. This work was supported in part by the NSF grants ECS-8814027 and MIP-8811815 ii 1 Introduction The performance of multicomputers is highly dependent on the underlying communicat...