A theory of wormhole routing in parallel computers
- 1 January 1992
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Virtually all theoretical work on message routing in parallel computers has dwelt on packet routing: messages are conveyed as packets, an entire packet can reside at a node of the network, and a packet is sent from the queue of one node to the queue of another node until its reaches its destination. The current trend in multicomputer architecture, however, is to use wormhole routing. In wormhole routing a message is transmitted as a contiguous stream of bits, physically occupying a sequence of nodes/edges in the network. Thus, a message resembles a worm burrowing through the network. The authors give theoretical analyses of simple wormhole routing algorithms, showing them to be nearly optimal for butterfly and mesh connected networks. The analysis requires initial random delays in injecting messages to the network. They report simulation results suggesting that the idea of random initial delays is not only useful for theoretical analysis but may actually improve the performance of wormhole routing algorithms.Keywords
This publication has 17 references indexed in Scilit:
- On bit-serial packet routing for the mesh and the torusPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Exact analysis of hot-potato routingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- Performance analysis of k-ary n-cube interconnection networksIEEE Transactions on Computers, 1990
- Average case analysis of greedy routing algorithms on arraysPublished by Association for Computing Machinery (ACM) ,1990
- The architecture and programming of the Ametek series 2010 multicomputerPublished by Association for Computing Machinery (ACM) ,1988
- How to emulate shared memoryPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- Deadlock-Free Message Routing in Multiprocessor Interconnection NetworksIEEE Transactions on Computers, 1987
- Parallel Communication With Limited BuffersPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1984
- Efficient Schemes for Parallel CommunicationJournal of the ACM, 1984
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952