World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

A Performance Model of Software-Based Deadlock Recovery Routing Algorithm in Hypercubes

    Recent studies have revealed that deadlocks are generally infrequent in the network. Thus the hardware resources, e.g. virtual channels, dedicated for deadlock avoidance are not utilised most of the time. This consideration has motivated the development of novel adaptive routing algorithms with deadlock recovery. This paper describes a new analytical model to predict message latency in hypercubes with a true fully adaptive routing algorithm with progressive deadlock recovery. One of the main features of the proposed model is the use of results from queueing systems with impatient customers to capture the effects of the timeout mechanism used in this routing algorithm for deadlock detection. The validity of the model is demonstrated by comparing analytical results with those obtained through simulation experiments.

    References

    • S. Abraham and K. Padmanabhan, IEEE Trans. Computers 38(7), 1001 (1989). Google Scholar
    • Anjan, K. V., Pinkston T. M., and Duato, J., Generalised theory for deadlock-free adaptive wormhole routing and its application to DISHA concurrent, Proc. 10th Int. Parallel Processing Symposium, Honululu, Pages 815-821, 1996 . Google Scholar
    • Boura, Y., Das, C., Jacob, T., A performance model for adaptive routing in hypercubes, Proc. Int. Workshop Parallel processing, Pages 11-16, 1994 . Google Scholar
    • D. J. Daley, Journal of Applied Probability 186 (1965). Google Scholar
    • W. J. Dally and C. L. Seitz, IEEE Trans. Computers 36(5), 547 (1987). ISIGoogle Scholar
    • W. Dally, IEEE Trans. Parallel & Distributed Systems 3(2), 194 (1992). Crossref, ISIGoogle Scholar
    • J. Draper and J. Ghosh, J. Parallel & Distributed Computing 32, 202 (1994). Google Scholar
    • J. Duato, IEEE Trans. Parallel & Distributed Systems 4(12), 320 (1993). Google Scholar
    • J.   Duato , S.   Yalamanchili and L.   Ni , Interconnection networks: An engineering approach ( IEEE Computer Society Press , 1997 ) . Google Scholar
    • A. Khonsari, H. Sarbazi-Azad and M. Ould-Khaoua, Journal of Systems & Software 71(3), 259 (2004). Crossref, ISIGoogle Scholar
    • A. Khonsari and M. Ould-Khaoua, Computers & Electrical Engineering 30(1), 45 (2004). Crossref, ISIGoogle Scholar
    • J. Kim, A. Chien and Z. Liu, IEEE Trans. Parallel & Distributed Systems 8(3), 229 (1997). Crossref, ISIGoogle Scholar
    • J. Kim and C. R. Das, IEEE Trans. Computers 43(7), 806 (1994). ISIGoogle Scholar
    • L.   Kleinrock , Queueing Systems   1 ( John Wiley , New York , 1975 ) . Google Scholar
    • Laudon, J., Lenoski, D., The SGI Origin: a ccNUMA highly scalable server, Proc. ACM/IEEE 24th Int. Symp. Computer Architecture, Pages: 241-251, 1997 . Google Scholar
    • X. Lin, P. A. McKinley and L. Ni, IEEE Trans. Parallel & Distributed Systems 6(7), 755 (1995). Crossref, ISIGoogle Scholar
    • Martinez, J. M., Lopez, P., Duato, J., Pinkston, T. M., Software-based deadlock recovery techniques for true fully adaptive routing in wormhole networks, Proc. Int. Conf. Parallel Processing (ICPP'97), Pages 182-189, 1997 . Google Scholar
    • Nugent, S., The iPSC/2 direct-connect communication technology, Proc. Conf. on Hypercube Concurrent Computers & Applications, 1: 51-60, 1988 . Google Scholar
    • M. Ould-Khaoua, IEEE Trans. Computers 42(12), 1 (1999). ISIGoogle Scholar
    • Pinkston T. M., Warnakulasuriya, S., On deadlocks in interconnection networks, Proc. 24th Int. Symp. Computer Architecture, Pages 38-49, 1997 . Google Scholar
    • R. E. Stanford, Mathematics of Operations Research 4(2), 162 (1979). CrossrefGoogle Scholar
    • H. Sarbazi-Azad, M. Ould-Khaoua and L. M. Mackenzie, Performance Evaluation 43(2-3), 165 (2001). Crossref, ISIGoogle Scholar
    • Su, C., Shin, K.G., Adaptive deadlock-free routing in multicomputers using one extra channel, Proc. International Conference on Parallel Processing, (1): 175-182, 1993 . Google Scholar
    • Tijms, H. C., Stochastic modelling and analysis: A computational approach J. Wiley . Google Scholar
    • Vanvoorst, B., Seidel, S., Barscz, E., Workload of an iPSC/860, Proc. Scalable High-Performance Computing Conf., Pages 221-228, 1994 . Google Scholar