TY - GEN
T1 - A class of partially adaptive routing algorithms for n-dimensional Meshes
AU - Boura, Younes M.
AU - Das, Chita R.
N1 - Publisher Copyright:
© 1993 IEEE.
PY - 1993
Y1 - 1993
N2 - A simple model, called the direction restriction model, for developing partially adaptive routing algorithms for n.dimensional meshes is introduced in this paper. This model is based on dividing a system into two unidirectional networks that contain all physical channels of the system. Delivery of a message is broken into two phases. In the first phase, a message is routed adapiively to an intermediate node using one unidirectional network. In the second phase, the message is routed adaptively to its destination in the remaining network. Messages are routed by using the wormhole switching paradigm. All of the algorithms that are developed by using this model are proven to be deadlock free at no extra cost »w terms of virtual channels. Routing algorithms are developed for 2-dimensional meshes, 3-dimensional meshes, and hy-percubes. The effectiveness of these algorithms for different traffic patterns is evaluated via simulation. The ease of use and simplicity of the direction restriction model make it an attractive tool for developing partially adaptive routing algorithms for n-dimensional meshes.
AB - A simple model, called the direction restriction model, for developing partially adaptive routing algorithms for n.dimensional meshes is introduced in this paper. This model is based on dividing a system into two unidirectional networks that contain all physical channels of the system. Delivery of a message is broken into two phases. In the first phase, a message is routed adapiively to an intermediate node using one unidirectional network. In the second phase, the message is routed adaptively to its destination in the remaining network. Messages are routed by using the wormhole switching paradigm. All of the algorithms that are developed by using this model are proven to be deadlock free at no extra cost »w terms of virtual channels. Routing algorithms are developed for 2-dimensional meshes, 3-dimensional meshes, and hy-percubes. The effectiveness of these algorithms for different traffic patterns is evaluated via simulation. The ease of use and simplicity of the direction restriction model make it an attractive tool for developing partially adaptive routing algorithms for n-dimensional meshes.
UR - http://www.scopus.com/inward/record.url?scp=0342312353&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0342312353&partnerID=8YFLogxK
U2 - 10.1109/ICPP.1993.16
DO - 10.1109/ICPP.1993.16
M3 - Conference contribution
AN - SCOPUS:0342312353
T3 - Proceedings of the International Conference on Parallel Processing
SP - 175
EP - 182
BT - Algorithms and Applications
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 -