Configurable flow control mechanisms for fault-tolerant routing

ABSTRACT

Fault-tolerant routing protocols in modern interconnection networks rely heavily on the network flow control mechanisms used. Optimistic flow control mechanisms such as wormhole routing (WR) realize very good performance, but are prone to deadlock in the presence of faults. Conservative flow control mechanisms such as pipelined circuit switching (PCS) insures existence of a path to the destination prior to message transmission, but incurs increased overhead. Existing fault-tolerant routing protocols are designed with one or the other, and must accommodate their associated constraints. This paper proposes the use of configurable flow control mechanisms. Routing protocols can then be designed such that in the vicinity of faults, protocols use a more conservative flow control mechanism, while the majority of messages that traverse fault-free portions of the network utilize a WR like flow control to maximize performance. Such protocols are referred to as two-phase protocols, where routing decisions are provided some control over the operation of the virtual channels. This ability provides new avenues for optimizing message passing performance in the presence of faults. A fully adaptive two-phase protocol is proposed and compared via simulation to those based on WR and PCS. The architecture of a network router supporting configurable flow control is described, and the paper concludes with avenues for future research.

REFERENCES

• 1: J. D. Allen , P. T. Gaughan , D. E. Schimmel , S. Yalamanchili, Ariadne—an adaptive router for fault-tolerant multicomputers, Proceedings of the 21ST annual international symposium on Computer architecture, p.278-288, April 18-21, 1994, Chicago, Illinois, United States
• 2: K. V. Anjan , Timothy Mark Pinkston, An efficient, fully adaptive deadlock recovery scheme: DISHA, Proceedings of the 22nd annual international symposium on Computer architecture, p.201-210, June 22-24, 1995, S. Margherita Ligure, Italy
• 3: 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
• 4: Suresh Chalasani , Rajendra V. Boppana, Fault-tolerant wormhole routing in tori, Proceedings of the 8th international conference on Supercomputing, p.146-155, July 11-15, 1994, Manchester, England [doi>10.1145/181181.181330]
• 5: 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
• 6: 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]
• 7: 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]
• 8: William J. Dally , Larry R. Dennison , David Harris , Kinhong Kan , Thucydides Xanthopoulos, The Reliable Router: A Reliable and High-Performance Communication Substrate for Parallel Computers, Proceedings of the First International Workshop on Parallel Computer Routing and Communication, p.241-255, May 16-18, 1994
• 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: Larry R. Dennison , Whay S. Lee , William J. Dally, High-performance bidirectional signalling in VLSI systems, Proceeding of the 1993 symposium on Research on integrated systems, p.300-319, February 1993, Seattle, Washington, United States
• 11: José Duato, A Thory of Fault-Tolerant routing in Wormhole Networks, Proceedings of the 1994 International Conference on Parallel and Distributed Systems, p.600-607, December 19-21, 1994
• 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: José Duato , V. B. Dao , Patrick T. Gaughan , Sudhakar Yalamanchili, Scouting: Fully Adaptive, Deadlock-Free Routing in Faulty Pipelined Networks, Proceedings of the 1994 International Conference on Parallel and Distributed Systems, p.608-613, December 19-21, 1994
• 14: D. Ferrari. Computer Systems Performance Evaluation. Prentice Hall, 1978.
• 15: P. T. Gaughan, B. V. Dao, S. Yalamanchili and D. E. SchimmeI. Distributed deadlock-free routing in faulty pipelined kary n-cubes. Technical Report GIT/CSRL-93/11, Georgia institute of Technology, November 1993
• 16: P.T. Gaughan and S. Yalamanchili. A family of fault-tolerant routing protocols for direct multiprocessor networks. Technical Report GIT/CSRL-93/01, Georgia Institute of Technology, January 1993. To appear in IEEE Transaction on Parallel and Distributed Systems.
• 17: 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]
• 18: P. T. Gaughan and S. Yalamanchili. Pipelined circuit switching: A fault-tolerant variant of wormhole routing. Proceedings of IEEE Symposium on Parallel and Distributed Processing, December 1992.
• 19: 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
• 20: C. J. Glass and L. M. Ni. Fault-tolerant wormhole routing in meshes. Proceedings of the 23rd International Symposium on Fault-Tolerant Computing, pages 240-249, 1L993.
• 21: R. E. Kessler and J. L. Schwarzmeier. Cray T3D: A new dimensions for cray research. Proceedings of the 38th Annual IEEE Computer Society International Computing Conference, 1993.
• 22: 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
• 23: Tze Chiang Lee , John P. Hayes, A fault-tolerant communication scheme for hypercube computers, IEEE Transactions on Computers, v.41 n.10, p.1243-1256, October 1992
• 24: Michael D. Noakes , Deborah A. Wallach , William J. Dally, The J-machine multicomputer: an architectural evaluation, Proceedings of the 20th annual international symposium on Computer architecture, p.224-235, May 16-19, 1993, San Diego, California, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Adaptable architectures
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Circuit-switching networks

General Terms:
Design, Performance