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. A 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. In this paper we give theoretical analyses of simple wormhole routing algorithms, showing them to be nearly optimal for butterfly and mesh connected networks. Our analysis requires initial random delays in injecting messages to the network. We report simulation results suggesting that the idea of random initial delays may have an impact beyond theoretical analysis.

Studies the use of randomized routing in multistage networks. While log N additional randomizing stages are needed to break "spatial locality", within each permutation, only log log N additional randomizing stages are needed to break "temporal locality" among successive permutations. Thus, log N bits of initial randomization per input, followed by log log N bits of randomization per packet are sufficient to ensure that t permutations are delivered in time t+log N. We present simulation results that validate this analysis.

This paper deals with the problem of packet-switched routing in parallel machines. Several new routing algorithms for different interconnection networks are presented. While the new techniques apply to a wide variety of networks, routing algorithms will be shown for the hypercube, the two-dimensional mesh, and the shuffle-exchange. Although the new techniques are designed for packet routing, they can be used alternatively for virtual cut-through routing models. The techniques presented for hypercubes and meshes are fully-adaptive and minimal. A fully-adaptive and minimal routing is one in which all possible minimal paths between a source and a destination are of potential use at the time a message is injected into the network. Minimal paths followed by messages ultimately depend on the local congestion encountered in each node of the network. All of the new techniques are completely free of deadlock situations.>

Article Hot-potato routing on processor arrays Share on Authors: Christos Kaklamanis DIMACS Center Rutgers University Piscataway, NJ DIMACS Center Rutgers University Piscataway, NJView Profile , Danny Krizanc School of Computer Science Carleton University Ottawa, Ontario K1S 5B6 School of Computer Science Carleton University Ottawa, Ontario K1S 5B6View Profile , Satish Rao NEC Research Institute, 4 Independence Way, Princeton, NJ NEC Research Institute, 4 Independence Way, Princeton, NJView Profile Authors Info & Claims SPAA '93: Proceedings of the fifth annual ACM symposium on Parallel Algorithms and ArchitecturesAugust 1993 Pages 273–282https://doi.org/10.1145/165231.376321Online:01 August 1993Publication History 34citation295DownloadsMetricsTotal Citations34Total Downloads295Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

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.>

Article Free Access Share on Fully-adaptive routing: packet switching performance and wormhole algorithms Authors: S. A. Felperin CRAAG IBM Argentina, ESLAI CRAAG IBM Argentina, ESLAIView Profile , L. Gravano CRAAG IBM Argentina, ESLAI CRAAG IBM Argentina, ESLAIView Profile , G. D. Pifarré CRAAG IBM Argentina, ESLAI CRAAG IBM Argentina, ESLAIView Profile , J. L. C. Sanz IBM Almaden Research Center, CRAAG IBM Argentina IBM Almaden Research Center, CRAAG IBM ArgentinaView Profile Authors Info & Claims Supercomputing '91: Proceedings of the 1991 ACM/IEEE conference on SupercomputingAugust 1991 Pages 654–663https://doi.org/10.1145/125826.126141Published:01 August 1991Publication History 22citation327DownloadsMetricsTotal Citations22Total Downloads327Last 12 Months8Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on Fully-adaptive minimal deadlock-free packet routing in hypercubes, meshes, and other networks Authors: Gustavo D. Pifarré ESLAI, Escuela Superior Latino Americana de Informática, CC 3193, (1000) Buenos Aires, Argentina. and Computer Research and Advanced Applications Group, IBM, Argentina, Ing. E. Butti 275, (1300) Buenos Aires, Argentina. and Computer Science Dept., IBM Almadeu Research Center, San, José, California ESLAI, Escuela Superior Latino Americana de Informática, CC 3193, (1000) Buenos Aires, Argentina. and Computer Research and Advanced Applications Group, IBM, Argentina, Ing. E. Butti 275, (1300) Buenos Aires, Argentina. and Computer Science Dept., IBM Almadeu Research Center, San, José, CaliforniaView Profile , Luis Gravano ESLAI, Escuela Superior Latino Americana de Informática, CC 3193, (1000) Buenos Aires, Argentina. and Computer Research and Advanced Applications Group, IBM, Argentina, Ing. E. Butti 275, (1300) Buenos Aires, Argentina. and Computer Science Dept., IBM Almadeu Research Center, San, José, California ESLAI, Escuela Superior Latino Americana de Informática, CC 3193, (1000) Buenos Aires, Argentina. and Computer Research and Advanced Applications Group, IBM, Argentina, Ing. E. Butti 275, (1300) Buenos Aires, Argentina. and Computer Science Dept., IBM Almadeu Research Center, San, José, CaliforniaView Profile , Sergio A. Felperin ESLAI, Escuela Superior Latino Americana de Informática, CC 3193, (1000) Buenos Aires, Argentina. and Computer Research and Advanced Applications Group, IBM, Argentina, Ing. E. Butti 275, (1300) Buenos Aires, Argentina. and Computer Science Dept., IBM Almadeu Research Center, San, José, California ESLAI, Escuela Superior Latino Americana de Informática, CC 3193, (1000) Buenos Aires, Argentina. and Computer Research and Advanced Applications Group, IBM, Argentina, Ing. E. Butti 275, (1300) Buenos Aires, Argentina. and Computer Science Dept., IBM Almadeu Research Center, San, José, CaliforniaView Profile , Jorge L. C. Sanz Computer Science Dept., IBM Almaden Research Center, San, José, California., Computer Research and Advanced Applications Group, IBM, Argentina, Ing. E. Butti 275, (1300) Buenos Aires, Argentina Computer Science Dept., IBM Almaden Research Center, San, José, California., Computer Research and Advanced Applications Group, IBM, Argentina, Ing. E. Butti 275, (1300) Buenos Aires, ArgentinaView Profile Authors Info & Claims SPAA '91: Proceedings of the third annual ACM symposium on Parallel algorithms and architecturesJune 1991 Pages 278–290https://doi.org/10.1145/113379.113405Published:01 June 1991Publication History 24citation298DownloadsMetricsTotal Citations24Total Downloads298Last 12 Months5Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A survey of some packet-switched routing methods for massively parallel computers is presented. Some of the techniques are applicable to both shared-memory and message-passing architectures. These routing methods are compared in terms of their efficiency in supporting programming models, efficiency in mapping to parallel machines, and practicality. Among the outlined methods, three nonadaptive techniques and some adaptive routing algorithms are discussed.>