On the Reduction of Deadlock Frequency by Limiting Message Injection in Wormhole Networks

1. A. Agarwal, “Limits on interconnection network performance”, IEEE Transactions on Parallel Distributed Systems, vol. 2, no. 4, pp. 398–412, Oct. 1991.

   Article  Google Scholar 

2. Anjan K. V. and T. M. Pinkston, “DISHA: A deadlock recovery scheme for fully adaptive routing,” in Proceedings of the 9th International Parallel Processing Symposium, April 1995.

   Google Scholar 

3. Anjan K. V. and T. M. Pinkston, An efficient fully adaptive deadlock recovery scheme: DISHA,” in Proceedings of the 22nd International Symposium on Computer Architecture, June 1995.

   Google Scholar 

4. Anjan K. V., T. M. Pinkston and J. Duato, “Generalized theory for deadlock-free adaptive routing and its application to Disha Concurrent,” in Proceedings of the 10th International Parallel Processing Symposium, April 1996.

   Google Scholar 

5. W. C. Athas and C. L. Seitz, “Multicomputers: Message-passing concurrent computers,” IEEE Computer, vol. 21, no. 8, pp. 9–24, August 1988.

   Google Scholar 

6. N. J. Boden, D. Cohen, R. E. Felderman, A. E. Kulawik, C. L. Seitz, J. Seizovic and W. Su, “Myrinet-A gigabit per second local area network,” IEEE Micro, pp. 29–36, February 1995.

   Google Scholar 

7. R. V. Boppana and S. Chalasani, “A comparison of adaptive wormhole routing algorithms,” in Proceedings of the 20th International Symposium on Computer Architecture, May 1993.

   Google Scholar 

8. A. A. Chien and J. H. Kim, “Planar-adaptive routing: Low-cost adaptive networks for multiprocessors,” in Proceedings of the 19th International Symposium on Computer Architecture, May 1992.

   Google Scholar 

9. A. A. Chien, “A cost and speed model for k-ary n-cube wormhole routers,” in Proceedings of Hot Interconnects’93, August 1993.

   Google Scholar 

10. W. J. Dally and C. L. Seitz, “Deadlock-free message routing in multiprocessor interconnection networks,” IEEE Transactions on Computers, vol. C-36, no. 5, pp. 547–553, May 1987.

    Article  Google Scholar 

11. W. J. Dally, “Virtual-channel flow control,” IEEE Transactions on Parallel and Distributed Systems, vol. 3, no. 2, pp. 194–205, March 1992.

    Article  Google Scholar 

12. J. Duato, “A new theory of deadlock-free adaptive routing in wormhole networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 4, no. 12, pp. 1320–1331, December 1993.

    Article  Google Scholar 

13. J. Duato, “A necessary and sufficient condition for deadlock-free adaptive routing in wormhole networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 6, no. 10, pp. 1055–1067, October 1995.

    Article  Google Scholar 

14. P. T. Gaughan and S. Yalamanchili, “Adaptive routing protocols for hypercube interconnection networks,” IEEE Computer, vol. 26, no. 5, pp. 12–23, May 1993.

    Google Scholar 

15. R. Horst, “ServerNet deadlock avoidance and fractahedral topologies,” in Proceedings of the International Parallel Processing Symposium, pp. 274–280, April 1996.

    Google Scholar 

16. Paragon XP/S Product Overview. Intel Corporation, Supercomputer Systems Division, Beaverton, OR, 1991.

    Google Scholar 

17. J. Kim, A. Chien, “An evaluation of the planar/adaptive routing,” in Proc. 4th IEEE Int. Symp. Parallel Distributed Processing, 1992.

    Google Scholar 

18. J. H. Kim, Z. Liu and A. A. Chien, “Compressionless routing: A framework for adaptive and fault-tolerant routing,” in Proceedings of the 21st International Symposium on Computer Architecture, April 1994.

    Google Scholar 

19. D. Lenoski, J. Laudon, K. Gharachorloo, W. Weber, A. Gupta, J. Hennessy, M. Horowitz and M. Lam, “The Stanford DASH multiprocessor,” IEEE Computer, vol. 25, no. 3, pp. 63–79, March 1992.

    Google Scholar 

20. P. López and J. Duato, “Deadlock-free adaptive routing algorithms for the 3D-torus: Limitations and solutions,” in Proceedings of Parallel Architectures and Languages Europe 93, June 1993.

    Google Scholar 

21. J.M. Martínez, P. López, J. Duato and T.M. Pinkston, “Software-Based Deadlock Recovery Technique for True Fully Adaptive Routing in Wormhole Networks,” to appear in Proceedings 1997 International Conference Parallel Processing, August 1997.

    Google Scholar 

22. P.K. McKinley, H. Xu, A. Esfahanian and L.M. Ni, “Unicast-based multicast communication in wormhole-routed networks,” in Proceedings 1992 International Conference Parallel Processing, August 1992.

    Google Scholar 

23. P.R. Miller, “Efficient communications for fine-grain distributed computers,” Ph.D Thesis, Southamptom University, 1991.

    Google Scholar 

24. L. M. Ni and P. K. McKinley, “A survey of wormhole routing techniques in direct networks,” IEEE Computer, vol. 26, no. 2, pp. 62–76, February 1993.

    Google Scholar 

25. T.M. Pinkston and S. Warnakulasuriya, “On Deadlocks in Interconnection Networks”, in Proceedings 24th International Symposium on Computer Architecture, June 1997.

    Google Scholar 

26. D. S. Reeves, E. F. Gehringer and A. Chandiramani, “Adaptive routing and deadlock recovery: A simulation study,” in Proceedings of the 4th Conference on Hypercube, Concurrent Computers & Applications, March 1989.

    Google Scholar 

27. S. L. Scott and G. Thorson, “The Cray T3E networks: adaptive routing in a high performance 3D torus,” in Proceedings of Hot Interconnects IV, August 1996.

    Google Scholar 

28. S. Warnakulasuriya and T.M. Pinkston, “Characterization of deadlocks in interconnection networks,” in Proceedings of the 11th International Parallel Processing Symposium, April 1997.

    Google Scholar 

Download references