A lightweight idempotent messaging protocol for faulty networks

ABSTRACT

As parallel machines scale to one million nodes and beyond, it becomes increasingly difficult to build a reliable network that is able to guarantee packet delivery. Eventually large systems will need to employ fault-tolerant messaging protocols that afford correct execution in the presence of a lossy network. In this paper we present a lightweight protocol that preserves message idempotence and is easy to implement in hardware. We identify the requirements for a correct implementation of the protocol. Experiments are performed in simulation to determine implementation parameters that optimize performance. We find that an aggressive implementation on a fat tree network results in a slowdown of less than 2x compared to buffered wormhole routing on a fault-free network.

REFERENCES

• 1: E. Baydal, P. Lopez, J. Duato, "A congestion control mechanism for wormhole networks", Proc. Ninth Euromicro Workshop on Parallel and Distributed Processing, 2001, pp. 19--26.
• 2: Timothy Callahan , Seth Copen Goldstein, NIFDY: a low overhead, high throughput network interface, Proceedings of the 22nd annual international symposium on Computer architecture, p.230-241, June 22-24, 1995, S. Margherita Ligure, Italy
• 3: Andrew A. Chien, A Cost and Speed Model for k-ary n-Cube Wormhole Routers, IEEE Transactions on Parallel and Distributed Systems, v.9 n.2, p.150-162, February 1998 [doi>10.1109/71.663877]
• 4: A. DeHon , F. Chong , M. Becker , E. Egozy , H. Minsky , S. Peretz , T. F. Knight, Jr., METRO: a router architecture for high-performance, short-haul routing networks, Proceedings of the 21ST annual international symposium on Computer architecture, p.266-277, April 18-21, 1994, Chicago, Illinois, United States
• 5: Cray Research, "CRAY T3D System Architecture Overview", Cray Research Inc., March 1993. 169 pp.
• 6: David E. Culler , Anoop Gupta , Jaswinder Pal Singh, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 7: 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]
• 8: 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]
• 9: 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
• 10: Suprakash Datta , Ramesh Sitaraman, The performance of simple routing algorithms that drop packets, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.159-169, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258508]
• 11: Larry R. Dennison, Reliable Interconnection Networks for Parallel Computers, Massachusetts Institute of Technology, Cambridge, MA, 1991
• 12: Eric A. Brewer , Bradley C. Kuszmaul, How to Get Good Performance from the CM-5 Data Network, Proceedings of the 8th International Symposium on Parallel Processing, p.858-867, April 01, 1994
• 13: Ian Eslick , André DeHon , Thomas F. Knight, Jr., Guaranteeing Idempotence for Tightly-Coupled, Fault-Tolerant Networks, Proceedings of the First International Workshop on Parallel Computer Routing and Communication, p.215-225, May 16-18, 1994
• 14: Marco Fillo , Stephen W. Keckler , William J. Dally , Nicholas P. Carter , Andrew Chang , Yevgeny Gurevich , Whay S. Lee, The M-Machine multicomputer, Proceedings of the 28th annual international symposium on Microarchitecture, p.146-156, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 15: M. Galles, "Scalable Pipelined Interconnect for Distributed Endpoint Routing: The SPIDER Chip", Proc. Hot Interconnects Symposium IV, August 1996, pp. 141--146.
• 16: Stephen R. Goldschmidt , John L. Hennessy, The accuracy of trace-driven simulations of multiprocessors, Proceedings of the 1993 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.146-157, May 10-14, 1993, Santa Clara, California, United States
• 17: M. A. Holliday , C. S. Ellis, Accuracy of Memory Reference Traces of Parallel Computations in Trace-Drive Simulation, IEEE Transactions on Parallel and Distributed Systems, v.3 n.1, p.97-109, January 1992 [doi>10.1109/71.113085]
• 18: Kai Hwang, Advanced Computer Architecture: Parallelism,Scalability,Programmability, McGraw-Hill Higher Education, 1992
• 19: F. Allen , G. Almasi , W. Andreoni , D. Beece , B. J. Berne , A. Bright , J. Brunheroto , C. Cascaval , J. Castanos , P. Coteus , P. Crumley , A. Curioni , M. Denneau , W. Donath , M. Eleftheriou , B. Fitch , B. Fleischer , C. J. Georgiou , R. Germain , M. Giampapa , D. Gresh , M. Gupta , R. Haring , H. Ho , P. Hochschild , S. Hummel , T. Jonas , D. Lieber , G. Martyna , K. Maturu , J. Moreira , D. Newns , M. Newton , R. Philhower , T. Picunko , J. Pitera , M. Pitman , R. Rand , A. Royyuru , V. Salapura , A. Sanomiya , R. Shah , Y. Sham , S. Singh , M. Snir , F. Suits , R. Swetz , W. C. Swope , N. Vishnumurthy , T. J. C. Ward , H. Warren , R. Zhou, Blue Gene: a vision for protein science using a petaflop supercomputer, IBM Systems Journal, v.40 n.2, p.310-327, February 2001
• 20: Vijay Karamcheti , Andrew A. Chien, A comparison of architectural support for messaging in the TMC CM-5 and the Cray T3D, Proceedings of the 22nd annual international symposium on Computer architecture, p.298-307, June 22-24, 1995, S. Margherita Ligure, Italy
• 21: Robert M. Metcalfe , David R. Boggs, Ethernet: distributed packet switching for local computer networks, Communications of the ACM, v.26 n.1, p.90-95, Jan. 1983 [doi>10.1145/357980.358015]
• 22: 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]
• 23: 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
• 24: J. Postel, "Transmission Control Protocol", RFC 793, 1981.
• 25: Randall Rettberg , Robert Thomas, Contention is no obstacle to shared-memory multiprocessing, Communications of the ACM, v.29 n.12, p.1202-1212, Dec. 1986 [doi>10.1145/7902.7905]
• 26: Randall D. Rettberg , William R. Crowther , Philip P. Carvey , Raymond S. Tomlinson, The Monarch Parallel Processor Hardware Design, Computer, v.23 n.4, p.18-28, 30, April 1990 [doi>10.1109/2.55467]
• 27: Reza Rooholamini , Vladimir Cherkassky , Mark Garver, Finding the right ATM switch for the market, Computer, v.27 n.4, p.16-28, April 1994 [doi>10.1109/2.274995]
• 28: Jeremy Brown, "An Idemptent Message Protocol", Project Aries Technical Memo ARIES-TM-014, available at http://www.ai.mit.edu/projects/aries/documents
• 29: Bobby Woods-Corwin, "A High Speed Fault-Tolerant Interconnect Fabric for Large-Scale Multiprocessing", M.Eng Thesis, Dept. of EECS, M.I.T., May 2001.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Protocol architecture (OSI model)

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

General Terms:
Design, Performance, Reliability

Keywords:
block-structured traces, idempotence, source-reliable messaging