A PERFORMANCE MODEL OF DISHA ROUTING IN K-ARY N-CUBE NETWORKS
Abstract
A number of analytical models for predicting message latency in k-ary n-cubes have recently been reported in the literature. Most of these models, however, have been discussed for adaptive routing algorithms based on deadlock avoidance, e.g. Duato's routing. Several research studies have empirically demonstrated that routing algorithms based on deadlock recovery offer maximal adaptivity that can result in considerable improvement in network performance. Disha is an example of a true fully adaptive routing algorithm that uses minimal hardware to implement a simple and efficient progressive method to recover from potential deadlocks. This paper proposes a new analytical model of Disha in wormhole-routed k-ary n-cubes. Simulation experiments confirm that the proposed model exhibits a good degree of accuracy for various networks sizes and under different traffic conditions.
References
- IEEE Trans. Computers 38(7), 1001 (1989), DOI: 10.1109/12.30851. Google Scholar
K. V. Anjan , T. M. Pinkston and J. Duato , Generalised theory for deadlock-free adaptive wormhole routing and its application to DISHA concurrent, Proc. 10th Int. Parallel Processing Symposium (1996) pp. 815–821, DOI: 10.1109/IPPS.1996.508153. Google ScholarY. Boura , C. Das and T. Jacob , A performance model for adaptive routing in hypercubes, Proc. Int. Workshop Parallel processing (1994) pp. 11–16. Google Scholar- Journal of Applied Probability 186 (1965). Google Scholar
- IEEE Trans. Computers 36(5), 547 (1987), DOI: 10.1109/TC.1987.1676939. ISI, Google Scholar
- IEEE Trans. Parallel & Distributed Systems 3(2), 194 (1992), DOI: 10.1109/71.127260. Crossref, ISI, Google Scholar
- J. Parallel & Distributed Computing 32, 202 (1994), DOI: 10.1006/jpdc.1994.1132. Google Scholar
- IEEE Trans. Parallel & Distributed Systems 4(12), 320 (1993), DOI: 10.1109/71.250114. Google Scholar
-
J. Duato , S. Yalamanchili and L. Ni , Interconnection networks: An engineering approach ( IEEE Computer Society Press , 1997 ) . Google Scholar - Journal of Systems & Software 71(3), 259 (2004), DOI: 10.1016/S0164-1212(03)00008-6. Crossref, ISI, Google Scholar
- Computers & Electrical Engineering 30(1), 45 (2004), DOI: 10.1016/S0045-7906(03)00004-1. Crossref, ISI, Google Scholar
- IEEE Trans. Parallel & Distributed Systems 8(3), 229 (1997), DOI: 10.1109/71.584089. Crossref, ISI, Google Scholar
- IEEE Trans. Computers 43(7), 806 (1994), DOI: 10.1109/12.293259. ISI, Google Scholar
-
L. Kleinrock , Queueing Systems 1 ( John Wiley , New York , 1975 ) . Google Scholar J. Laudon and D. Lenoski , The SGI Origin: a ccNUMA highly scalable server, Proc. ACM/IEEE 24th Int. Symp. Computer Architecture (1997) pp. 241–251. Google Scholar- IEEE Trans. Parallel & Distributed Systems 6(7), 755 (1995), DOI: 10.1109/71.395404. Crossref, ISI, Google Scholar
J. M. Martinez , Software-based deadlock recovery techniques for true fully adaptive routing in wormhole networks, Proc. Int. Conf. Parallel Processing (ICPP'97) (1997) pp. 182–189, DOI: 10.1109/ICPP.1997.622586. Google ScholarS. Nugent , The iPSC/2 direct-connect communication technology, Proc. Conf. on Hypercuhe Concurrent Computers & Applications1 (1988) pp. 51–60, DOI: 10.1145/62297.62305. Google Scholar- IEEE Trans. Computers 42(12), 1 (1999), DOI: 10.1109/12.817384. ISI, Google Scholar
T. M. Pinkston and S. Warnakulasuriya , On deadlocks in interconnection networks, Proc. 24th Int. Symp. Computer Architecture (1997) pp. 38–49. Google Scholar- Mathematics of Operations Research 4(2), 162 (1979). Crossref, Google Scholar
- Performance Evaluation 43(2–3), 165 (2001), DOI: 10.1016/S0166-5316(00)00049-3. Crossref, ISI, Google Scholar
C. Su and K. G. Shin , Adaptive deadlock-free routing in multicomputers using one extra channel, Proc. International Conference on Parallel Processing1 (1993) pp. 175–182, DOI: 10.1109/ICPP.1993.37. Google Scholar-
H. C. Tijms , Stochastic modelling and analysis: A computational approach ( J. Wiley ) . Google Scholar B. Vanvoorst , S. Seidel and E. Barscz , Workload of an iPSC/860, Proc. Scalable High-Performance Computing Conf. (1994) pp. 221–228. Google Scholar


