The Message Flow Model for Routing in Wormhole-Routed Networks

Xiaola Lin; Philip K. McKinley; Lionel M. Ni

doi:10.1109/ICPP.1993.176

The Message Flow Model for Routing in Wormhole-Routed Networks

Xiaola Lin, Philip K. McKinley, Lionel M. Ni

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

55 Citations (Scopus)

Abstract

In this paper, we introduce a new approach to deadlock-free routing in wormhole-routed networks called the message flow model. We first establish the necessary and sufficient condition for deadlock-free routing based on the analysis of the message flow on each channel. We then show how to use the model to prove that a given adaptive routing algorithm is deadlock-free. Finally, we use the method to de¿ velop new, efficient adaptive routing algorithms for 2D meshes and hypercubes.

Original language	English
Title of host publication	Architecture
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	294-297
Number of pages	4
ISBN (Electronic)	0849389836
DOIs	https://doi.org/10.1109/ICPP.1993.176
Publication status	Published - 1993
Externally published	Yes
Event	1993 International Conference on Parallel Processing, ICPP 1993 - Syracuse, United States Duration: 16 Aug 1993 → 20 Aug 1993

Publication series

Name	Proceedings of the International Conference on Parallel Processing
Volume	1
ISSN (Print)	0190-3918

Conference

Conference	1993 International Conference on Parallel Processing, ICPP 1993
Country/Territory	United States
City	Syracuse
Period	16/08/93 → 20/08/93

Bibliographical note

Publisher Copyright:
© 1993 IEEE.

Access to Document

10.1109/ICPP.1993.176

Cite this

@inproceedings{fec5181ca50d44419b67aa2bb6dfa31a,

title = "The Message Flow Model for Routing in Wormhole-Routed Networks",

abstract = "In this paper, we introduce a new approach to deadlock-free routing in wormhole-routed networks called the message flow model. We first establish the necessary and sufficient condition for deadlock-free routing based on the analysis of the message flow on each channel. We then show how to use the model to prove that a given adaptive routing algorithm is deadlock-free. Finally, we use the method to de¿ velop new, efficient adaptive routing algorithms for 2D meshes and hypercubes.",

author = "Xiaola Lin and McKinley, \{Philip K.\} and Ni, \{Lionel M.\}",

note = "Publisher Copyright: {\textcopyright} 1993 IEEE.; 1993 International Conference on Parallel Processing, ICPP 1993 ; Conference date: 16-08-1993 Through 20-08-1993",

year = "1993",

doi = "10.1109/ICPP.1993.176",

language = "English",

series = "Proceedings of the International Conference on Parallel Processing",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "294--297",

booktitle = "Architecture",

}

Lin, X, McKinley, PK & Ni, LM 1993, The Message Flow Model for Routing in Wormhole-Routed Networks. in Architecture., 4134156, Proceedings of the International Conference on Parallel Processing, vol. 1, Institute of Electrical and Electronics Engineers Inc., pp. 294-297, 1993 International Conference on Parallel Processing, ICPP 1993, Syracuse, United States, 16/08/93. https://doi.org/10.1109/ICPP.1993.176

The Message Flow Model for Routing in Wormhole-Routed Networks. / Lin, Xiaola; McKinley, Philip K.; Ni, Lionel M.
Architecture. Institute of Electrical and Electronics Engineers Inc., 1993. p. 294-297 4134156 (Proceedings of the International Conference on Parallel Processing; Vol. 1).

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

TY - GEN

T1 - The Message Flow Model for Routing in Wormhole-Routed Networks

AU - Lin, Xiaola

AU - McKinley, Philip K.

AU - Ni, Lionel M.

PY - 1993

Y1 - 1993

N2 - In this paper, we introduce a new approach to deadlock-free routing in wormhole-routed networks called the message flow model. We first establish the necessary and sufficient condition for deadlock-free routing based on the analysis of the message flow on each channel. We then show how to use the model to prove that a given adaptive routing algorithm is deadlock-free. Finally, we use the method to de¿ velop new, efficient adaptive routing algorithms for 2D meshes and hypercubes.

AB - In this paper, we introduce a new approach to deadlock-free routing in wormhole-routed networks called the message flow model. We first establish the necessary and sufficient condition for deadlock-free routing based on the analysis of the message flow on each channel. We then show how to use the model to prove that a given adaptive routing algorithm is deadlock-free. Finally, we use the method to de¿ velop new, efficient adaptive routing algorithms for 2D meshes and hypercubes.

UR - https://www.scopus.com/pages/publications/84972240794

U2 - 10.1109/ICPP.1993.176

DO - 10.1109/ICPP.1993.176

M3 - Conference Paper published in a book

AN - SCOPUS:84972240794

T3 - Proceedings of the International Conference on Parallel Processing

SP - 294

EP - 297

BT - Architecture

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 1993 International Conference on Parallel Processing, ICPP 1993

Y2 - 16 August 1993 through 20 August 1993

ER -

The Message Flow Model for Routing in Wormhole-Routed Networks

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this