An efficient, fully adaptive deadlock recovery scheme: DISHA

ABSTRACT

This paper presents a simple, efficient and cost effective routing strategy that considers deadlock recovery as opposed to prevention. Performance is optimized in the absence of deadlocks by allowing maximum flexibility in routing. Disha supports true fully adaptive routing where all virtual channels at each node are available to packets without regard for deadlocks. Deadlock cycles, upon forming, are efficiently broken by progressively routing one of the blocked packets through a deadlock-free lane. This lane is implemented using a central "floating" deadlock buffer resource in routers which is accessible to all neighboring routers along the path. Simulations show that the Disha scheme results in superior performance and is extremely simple, ensuring quick recovery from deadlocks and enabling the design of fast routers.

REFERENCES

• 1: K. V. Anjan , Timothy Mark Pinkston, DISHA: a deadlock recovery scheme for fully adaptive routing, Proceedings of the 9th International Symposium on Parallel Processing, p.537-543, April 25-28, 1995
• 2: Anjan K. V., Timothy Mark Pinkston, and Jose Duato. Concurrent Deadlock Recovery in Disha. ~;ubmitted to the International Conference on Computer Design, October 1995.
• 3: Anjan K. V. and Timothy Mark Pinkston. DISHA: An Efficient, Fully Adaptive Deadlock Recovery Scheme. CENG Technical Report 94-23, Department of Electrical Engineering - Systems, University of Southern California, Los Angeles, CA 90089-2562, November 1994.
• 4: Andrew A. Chien , Jae H. Kim, Planar-adaptive routing: low-cost adaptive networks for multiprocessors, Proceedings of the 19th annual international symposium on Computer architecture, p.268-277, May 19-21, 1992, Queensland, Australia
• 5: Andrew A. Chien. A Cost and Speed Model for k-ary ncube Wormhole Routers. In Proceedings of the symposium on Hot Interconnects, IEEE Computer Society, August 1993.
• 6: K. Aoyama. Design Issues in Implementing an Adaptive Router. Master's Thesis, University of Illinois, Department of Computer Science, 1304 W. Springfield Avenue, Urbana, Illinois., January 1993.
• 7: Pablo E. Berman , Luis Gravano , Gustavo D. Pifarré , Jorge L. C. Sanz, Adaptive deadlock- and livelock-free routing with all minimal paths in Torus networks, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.3-12, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.140902]
• 8: Rajendra V. Boppana , Suresh Chalasani, A comparison of adaptive wormhole routing algorithms, Proceedings of the 20th annual international symposium on Computer architecture, p.351-360, May 16-19, 1993, San Diego, California, United States
• 9: W. J. Dally , C. L. Seitz, Deadlock-free message routing in multiprocessor interconnection networks, IEEE Transactions on Computers, v.36 n.5, p.547-553, May 1987 [doi>10.1109/TC.1987.1676939]
• 10: 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]
• 11: W. J. Dally , H. Aoki, Deadlock-Free Adaptive Routing in Multicomputer Networks Using Virtual Channels, IEEE Transactions on Parallel and Distributed Systems, v.4 n.4, p.466-475, April 1993 [doi>10.1109/71.219761]
• 12: 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]
• 13: J. Duato. A Necessary and Sufficient Condition for Deadlock-Free Adaptive Routing in Wormhole Networks. In Proceedings of the International Conference on Parallel Processing, CRC Press, pages I 142-I 149, August 1994.
• 14: Pedro López , José Duato, Deadlock-Free Adaptive Routing Algorithms for the 3D-Torus: Limitations and Solutions, Proceedings of the 5th International PARLE Conference on Parallel Architectures and Languages Europe, p.684-687, June 14-17, 1993
• 15: José Duato, Improving the efficiency of virtual channels with time-dependent selection functions, Conference proceedings on PARLE'92, p.45-58, April 1994, Paris, France
• 16: Patrick T. Gaughan , Sudhakar Yalamanchili, Adaptive routing protocols for hypercube interconnection networks, Computer, v.26 n.5, p.12-23, May 1993 [doi>10.1109/2.211888]
• 17: J. H. Kim , Z. Liu , A. A. Chien, Compressionless routing: a framework for adaptive and fault-tolerant routing, Proceedings of the 21ST annual international symposium on Computer architecture, p.289-300, April 18-21, 1994, Chicago, Illinois, United States
• 18: S. Konstantinidou , L. Snyder, Chaos router: architecture and performance, Proceedings of the 18th annual international symposium on Computer architecture, p.212-221, May 27-30, 1991, Toronto, Ontario, Canada
• 19: Daniel H. Linder , Jim C. Harden, An Adaptive and Fault Tolerant Wormhole Routing Strategy for k-ary n-cubes, IEEE Transactions on Computers, v.40 n.1, p.2-12, January 1991 [doi>10.1109/12.67315]
• 20: Christopher J. Glass , Lionel M. Ni, The turn model for adaptive routing, Proceedings of the 19th annual international symposium on Computer architecture, p.278-287, May 19-21, 1992, Queensland, Australia
• 21: Lionel M. Ni , Philip K. McKinley, A Survey of Wormhole Routing Techniques in Direct Networks, Computer, v.26 n.2, p.62-76, February 1993 [doi>10.1109/2.191995]
• 22: Timothy Mark Pinkston. Design Considerations for Optical Interconnects in Parallel Computers. In Proceedings of the First International Workshop on Massively Parallel Processing using Optical Interconnects, IEEE Computer Society, pages 306-322, April 1994.
• 23: Douglas S. Reeves, Edward F. Gehringer, and Anil Claandiramani. Adaptive Routing and Deadlock Recovery: A Simulation Study. In Proceedings of the 4th Conference on Hypercube Concurrent Computers and Applications, March 1989.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Design, Performance, Theory, Verification