Communication delay in wormhole-routed torus networks

ABSTRACT

A new analytical model for predicting message delay in wormhole-routed torus is presented. Unlike previous wormhole routing models, which mainly have been developed for uniform traffic, the model introduced in this paper computes message latency in the wormhole-routed torus in the presence of broadcast traffic. Results obtained through simulation experiments show that the model exhibits a good degree of accuracy in predicting message latency under different working conditions.

REFERENCES

• 1: Seth Abraham , Krishnan Padmanabhan, Performance of the Direct Binary n-Cube Network for Multiprocessors, IEEE Transactions on Computers, v.38 n.7, p.1000-1011, July 1989 [doi>10.1109/12.30851]
• 2: Bob Broeg , Bella Bose , Younggeun Kwon , Yaagoub Ashir, Lee Distance and Topological Properties of k-ary n-cubes, IEEE Transactions on Computers, v.44 n.8, p.1021-1030, August 1995 [doi>10.1109/12.403718]
• 3: Y. Boura, C. R. Das, T. M. Jacob, A performance model for adaptive routing in hypercubes, Proceedings of International Workshop Parallel processing (1994) 11-16.
• 4: William J. Dally, Performance Analysis of k-ary n-cube Interconnection Networks, IEEE Transactions on Computers, v.39 n.6, p.775-785, June 1990 [doi>10.1109/12.53599]
• 5: W. J. Dally, Virtual-Channel Flow Control, IEEE Transactions on Parallel and Distributed Systems, v.3 n.2, p.194-205, March 1992 [doi>10.1109/71.127260]
• 6: Jeffrey T. Draper , Joydeep Ghosh, A comprehensive analytical model for wormhole routing in multicomputer systems, Journal of Parallel and Distributed Computing, v.23 n.2, p.202-214, Nov. 1994 [doi>10.1006/jpdc.1994.1132]
• 7: José Duato, A New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks, IEEE Transactions on Parallel and Distributed Systems, v.4 n.12, p.1320-1331, December 1993 [doi>10.1109/71.250114]
• 8: Jose Duato , Sudhakar Yalamanchili , Lionel Ni, Interconnection Networks: An Engineering Approach, IEEE Computer Society Press, Los Alamitos, CA, 1997
• 9: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 10: Philip K. McKinley , Hong Xu , Lionel M. Ni , Abdol-Hossein Esfahanian, Unicast-Based Multicast Communication in Wormhole-Routed Networks, IEEE Transactions on Parallel and Distributed Systems, v.5 n.12, p.1252-1265, December 1994 [doi>10.1109/71.334899]
• 11: Mohamed Ould-Khaoua, A Performance Model for Duato's Fully Adaptive Routing Algorithm in k$k$-Ary n$n$-Cubes, IEEE Transactions on Computers, v.48 n.12, p.1297-1304, December 1999 [doi>10.1109/12.817384]
• 12: Dhabaleswar K. Panda , Sanjay Singal , Ram Kesavan, Multidestination Message Passing in Wormhole k-ary n-cube Networks with Base Routing Conformed Paths, IEEE Transactions on Parallel and Distributed Systems, v.10 n.1, p.76-96, January 1999 [doi>10.1109/71.744844]
• 13: A. Shahrabi, M. Ould-Khaoua, L. Mackenzie, Analytical modeling of broadcast in Torus Networks,, Tech. Report, Department of Computing Science, University of Glasgow, 2001.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.3 Applications

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
adaptive routing, broadcast operation, interconnection networks, performance modelling, wormhole routing