This paper consists of two parts. In the first part, two new algorithms for deadlock- and livelock-free wormhole routing in the torus network are presented. The first algorithm, called Channels, is for the n-dimensional torus network. This technique is fully-adaptive minimal, that is, all paths with a minimal number of hops from source to destination are available for routing, and needs only five virtual channels per bidirectional link, the lowest channel requirement known in the literature for fully-adaptive minimal worm-hole routing. In addition, this result also yields the lowest buffer requirement known in the literature for packet-switched fully-adaptive minimal routing. The second algorithm, called 4-Classes, is for the bidimensional torus network. This technique is fully-adaptive minimal and requires only eight virtual channels per bidirectional link. Also, it allows for a highly parallel implementation of its associated routing node. In the second part of this paper, four worm-hole routing techniques for the two-dimensional torus are experimentally evaluated using a dynamic message injection model and different traffic patterns and message lengths.>

This paper consists of two parts. In the first one, two new algorithms for wormhole routing on the hypercube network are presented. These techniques are adaptive and are ensured to be deadlock- and livelock-free. These properties are guaranteed by using a small number of resources in the routing node. The first algorithm is adaptive and nonminimal and will be referred to as Nonminimal. In this technique, some moderate derouting is allowed in order to alleviate the potential congestion arising from highly structured communication patterns. The second algorithm, dubbed Subcubes, is adaptive and minimal, and is based on partitioning the hypercube into subcubes of smaller dimension; This technique requires only two virtual channels per physical link of the node. In the second part of the paper, a wide variety of techniques for wormhole routing in the hypercube are evaluated from an algorithmic point of view. Five partially adaptive algorithms are considered: the Hanging algorithm, the Zenith algorithm, the Hanging-Order algorithm, the Nonminimal algorithm; and the Subcubes algorithm. One oblivious algorithm, the Dimension-Order, or E-Cube routing algorithm, is also used. Finally, a Fully Adaptive Minimal algorithm is tried. A simple node model was designed and adapted to all the algorithms.>

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

This paper consists of two parts. In the first part, a new algorithm for deadlock- and livelock-free routing for the n-dimensional torus network is presented. This algo- rithm, called *-Channels, is fully-adaptive minimal, i.e. all paths with a minimal number of hops from source to destination are available for routing. *-Channels works for messages of unknown size, thus yielding new rout- ing techniques for both packet-switched and worm-hole models. *.Channels differs radically from the packetswitched fully-adaptive minimal methods presented in SPAA '91 by Pifarr6, Gravano, Felperin, and Sanz [PGFS91]. In particular, the packet-based techniques in [PGFS91] do not work for worm-hole routing as dead- lock situations can be constructed.

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