Abstract
NOWs are arranged as a switch-based network which allows the layout of both regular and irregular topologies. However, the irregular pattern interconnect makes routing and deadlock avoidance quite complicated. Current proposals use the up*/down* routing algorithm to remove cyclic dependencies between channels and avoid deadlock. Recently, a simple and effective methodology to compute up*/down* routing tables has been proposed by us. The resulting routing algorithm is very effective in irregular topologies. However, its behavior is very poor in regular networks with orthogonal dimensions. Therefore we propose a more flexible routing scheme that is effective in both regular and irregular topologies. Unlike up*/down* routing algorithms, the proposed routing algorithm breaks cycles at different nodes for each direction in the cycle, thus providing better traffic balancing than that provided by up*/down* routing algorithms. Evaluation results modeling a Myrinet network show that the new routing algorithm increases throughput with respect to the original up*/down* routing algorithm by a factor of up to 3:5 for regular networks, also maintaining the performance of the improved up*/down* routing scheme proposed in [7] when applied to irregular networks.
This work was supported by the Spanish CICYT under Grant TIC97-0897-C04-01.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
N. J. Boden et al., Myrinet — A gigabit per second local area network, IEEE Micro, vol. 15, Feb. 1995.
L. Cherkasova, V. Kotov, and T. Rockicki, Fibre channel fabrics: Evaluation and design, 29th Hawaii International Conference on System Sciences, Feb. 1995.
W. J. Dally and C. L. Seitz, Deadlock-free message routing in multiprocessors interconnection networks, IEEE Transactions on Computers, vol. C-36, no. 5, pp. 547–553, May. 1987.
D. García and W. Watson, Servernet II, in Proceedings of the 1997 Parallel Computer, Routing, and Communication Workshop, June 1997.
W. Qiao and L. M. Ni., Adaptive routing in irregular networks using cut-trough switches, in Proc. of the 1996 Int. Conf. on Parallel Processing, Aug. 1996.
R. Riesen et al., “CPLANT”, in in Proc. of the Second Extreme Linux Workshop, June 1999.
J.C. Sancho and A. Robles, Improving the Up*/Down* Routing Scheme for Networks of Workstations Accepted for publishing in Euro-Par 2000, Aug. 2000.
J.C. Sancho, A. Robles, and J. Duato, New Methodology to Compute Deadlock-Free Routing Tables for Irregular Networks, in in Proc. of CANPC’2000, Jan. 2000.
M. D. Schroeder et al., Autonet: A high-speed, self-configuring local area network using point-to-point links, SRC research report 59, DEC, Apr. 1990.
R. Sheifert, Gigabit Ethernet, Addison-Wesley, Apr. 1998.
F. Silla and J. Duato, Improving the Efficiency of Adaptive Routing in Networks with Irregular Topology, in 1997 Int. Conference on High Performance Computing, Dec. 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Carlos Sancho, J., Robles, A., Duato, J. (2000). A Flexible Routing Scheme for Networks of Workstations. In: Valero, M., Joe, K., Kitsuregawa, M., Tanaka, H. (eds) High Performance Computing. ISHPC 2000. Lecture Notes in Computer Science, vol 1940. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-39999-2_23
Download citation
DOI: https://doi.org/10.1007/3-540-39999-2_23
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41128-4
Online ISBN: 978-3-540-39999-5
eBook Packages: Springer Book Archive