Abstract
Analytical models for wormhole‐routed hypercubes with deterministic routing have been widely reported in the literature. A model for the hypercube with fully‐adaptive routing has recently been proposed in [1]. It uses M/M/1 queues, and computes a different probability of blocking at each intermediate router along the message path. As a result, the number of equations, and thus the computation steps, to evaluate latency increases with the network size. This paper proposes an alternative model that uses M/G/1 queues, and requires a constant number of computation steps irrespective of the network size. It achieves this by computing only once the mean probability of blocking across the entire path, and using it to determine the blocking time at a given router. Simulation experiments reveal that the model yields accurate latency results.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Y. Boura, C.R. Das and T.M. Jacob, A performance model for adaptive routing in hypercubes, in: Proc. of the 1st Internat. Workshop on Parallel Processing, Bangalore, India (1994) pp. 11–16.
W.J. Dally, Performance analysis of k-ary n-cubes interconnection networks, IEEE Transactions on Computers 39(6) (1990) 775–785.
W.J. Dally, Virtual channel flow control, IEEE Transactions on Parallel and Distributed Systems 3(2) (1992) 194–205.
W.J. Dally and C.L. Seitz, Deadlock-free message routing in multiprocessor interconnection networks, IEEE Transactions on Computers 36(5) (1987) 547–553.
J.T. Draper and J. Ghosh, A comprehensive analytical model for wormhole routing in multicomputer systems, Journal of Parallel and Distributed Computing 23 (1994) 202–214.
J. Duato, A New theory of deadlock-free adaptive routing in wormhole routing networks, IEEE Transactions on Parallel and Distributed Systems 4(12) (1993) 1320–1331.
J. Kim and C.R. Das, Hypercube communication delay with wormhole routing, IEEE Transactions on Computers 43(7) (1994) 806–814.
L. Kleinrock, Queueing Systems, Vol. 1 (Wiley, New York, 1975).
X. Lin, P.K. Mckinley and L.M. Lin, The message flow model for routing in wormhole-routed networks, in: Proc. of Internat. Conf. on Parallel Processing (1993) pp. 294–297.
D.H. Linder and J.C. Harden, An adaptive and fault tolerant wormhole routing strategy for k-ary n-cubes, IEEE Transactions on Computers 40(1) (1991) 2–12.
N-Cube Systems, N-cube Handbook (1986).
S.F. Nugent, The iPSC/2 direct-connect communication technology, in: Proc. of Conf. on Hypercube Concurrent Computers and Applications, Vol. 1 (1988) pp. 51–60.
C.L. Seitz, The Cosmic Cube, Communications of the ACM 28 (1985) 22–33.
C.L. Seitz, The hypercube communication chip, Dept. Comput. Sci., CalTech, Display File 5182:DF:85 (March 1985).
C. Su and K.G. Shin, Adaptive deadlock-free routing in multicomputers using one extra channel, in: Proc. of Internat. Conf. on Parallel Processing (1993) pp. 175–182.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Loucif, S., Ould‐Khaoua, M. & Mackenzie, L. Modelling fully‐adaptive routing in hypercubes. Telecommunication Systems 13, 111–118 (2000). https://doi.org/10.1023/A:1019131704035
Issue Date:
DOI: https://doi.org/10.1023/A:1019131704035