Deadlock-free multicast wormhole routing in 2-D mesh multicomputers
- 1 August 1994
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 5 (8) , 793-804
- https://doi.org/10.1109/71.298203
Abstract
Multicast communication services, in which the same message is delivered from a source node to an arbitrary number of destination nodes, are being provided in new-generation multicomputers. Broadcast is a special case of multicast in which a message is delivered to all nodes in the network. The nCUBE-2, a wormhole-routed hypercube multicomputer, provides hardware support for broadcast and a restricted form of multicast in which the destinations form a subcube. However, the broadcast routing algorithm adopted in the nCUBE-2 is not deadlock-free. In this paper, four multicast wormhole routing strategies for 2-D mesh multicomputers are proposed and studied. All of the algorithms are shown to be deadlock-free. These are the first deadlock-free multicast wormhole routing algorithms ever proposed. A simulation study has been conducted that compares the performance of these multicast algorithms under dynamic network traffic conditions in a 2-D mesh. The results indicate that a dual-path routing algorithm offers performance advantages over tree-based, multipath, and fixed-path algorithms.<>Keywords
This publication has 17 references indexed in Scilit:
- iWarp: an integrated solution to high-speed parallel computingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- ComPaSS: efficient communication services for scalable architecturesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A survey of wormhole routing techniques in direct networksComputer, 1993
- Efficient implementation of barrier synchronization in wormhole-routed hypercube multicomputersJournal of Parallel and Distributed Computing, 1992
- The message-driven processor: a multicomputer processing node with efficient mechanismsIEEE Micro, 1992
- Multicast in hypercube multiprocessorsJournal of Parallel and Distributed Computing, 1990
- Multicomputers: message-passing concurrent computersComputer, 1988
- The architecture and programming of the Ametek series 2010 multicomputerPublished by Association for Computing Machinery (ACM) ,1988
- The torus routing chipDistributed Computing, 1986
- Virtual cut-through: A new computer communication switching techniqueComputer Networks (1976), 1979