Automated application-level checkpointing of MPI programs

ABSTRACT

The running times of many computational science applications, such as protein-folding using ab initio methods, are much longer than the mean-time-to-failure of high-performance computing platforms. To run to completion, therefore, these applications must tolerate hardware failures.In this paper, we focus on the stopping failure model in which a faulty process hangs and stops responding to the rest of the system. We argue that tolerating such faults is best done by an approach called application-level coordinated non-blocking checkpointing, and that existing fault-tolerance protocols in the literature are not suitable for implementing this approach.We then present a suitable protocol, which is implemented by a co-ordination layer that sits between the application program and the MPI library. We show how this protocol can be used with a precompiler that instruments C/MPI programs to save application and MPI library state. An advantage of our approach is that it is independent of the MPI implementation. We present experimental results that argue that the overhead of using our system can be small.

REFERENCES

• 1: Adnan Agbaria , Roy Friedman, Starfish: Fault-Tolerant Dynamic MPI Programs on Clusters of Workstations, Proceedings of the The Eighth IEEE International Symposium on High Performance Distributed Computing, p.31, August 03-06, 1999
• 2: Micah Beck , James S. Plank , Gerry Kingsley, Compiler-Assisted Checkpointing, University of Tennessee, Knoxville, TN, 1994
• 3: Adam Beguelin , Erik Seligman , Peter Stephan, Application level fault tolerance in heterogeneous networks of workstations, Journal of Parallel and Distributed Computing, v.43 n.2, p.147-155, June 15, 1997 [doi>10.1006/jpdc.1997.1338]
• 4: Greg Bronevetsky , Daniel Marques , Keshav Pingali , Paul Stodghill, Collective operations in application-level fault-tolerant MPI, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782847]
• 5: K. Mani Chandy , Leslie Lamport, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.63-75, Feb. 1985 [doi>10.1145/214451.214456]
• 6: Elmootazbellah N. Elnozahy , Willy Zwaenepoel, Manetho: Transparent Roll Back-Recovery with Low Overhead, Limited Rollback, and Fast Output Commit, IEEE Transactions on Computers, v.41 n.5, p.526-531, May 1992 [doi>10.1109/12.142678]
• 7: M. Elnozahy, L. Alvisi, Y. M. Wang, and D. B. Johnson. A survey of rollback-recovery protocols in message passing systems. Technical Report CMU-CS-96-181, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA, Oct. 1996.
• 8: Message P Forum, MPI: A Message-Passing Interface Standard, University of Tennessee, Knoxville, TN, 1994
• 9: M. P. I. Forum. MPI-2: Extensions to the message-passing interface, July 18 1997. Available from http://www.mpi-forum.org/docs/mpi-20-html/mpi2-report.html.
• 10: Richard L. Graham , Sung-Eun Choi , David J. Daniel , Nehal N. Desai , Ronald G. Minnich , Craig E. Rasmussen , L. Dean Risinger , Mitchel W. Sukalski, A network-failure-tolerant message-passing system for terascale clusters, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514205]
• 11: Indranil Gupta , Tushar D. Chandra , Germán S. Goldszmidt, On scalable and efficient distributed failure detectors, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.170-179, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384010]
• 12: IBM Research. Blue gene project overview. Online at http://www.research.ibm.com/bluegene/, 2002.
• 13: David B. Johnson , Willy Zwaenepoel, Transparent optimistic rollback recovery, ACM SIGOPS Operating Systems Review, v.25 n.2, p.99-102, April 1991 [doi>10.1145/122120.122132]
• 14: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 15: J. B. M. Litzkow, T. Tannenbaum and M. Livny. Checkpoint and migration of UNIX processes in the condor distributed processing system. Technical Report 1346, University of Wisconsin-Madison, 1997.
• 16: National Nuclear Security Administration. Asci home. Online at http://www.nnsa.doe.gov/asc/, 2002.
• 17: James S. Plank , Micah Beck , Gerry Kingsley , Kai Li, Libckpt: Transparent Checkpointing under Unix, University of Tennessee, Knoxville, TN, 1994
• 18: Balkrishna Ramkumar , Volker Strumpen, Portable Checkpointing for Heterogeneous Archtitectures, Proceedings of the 27th International Symposium on Fault-Tolerant Computing (FTCS '97), p.58, June 25-27, 1997
• 19: Sriram Rao , Lorenzo Alvisi , Harrick M. Vin, Egida: An Extensible Toolkit For Low-Overhead Fault-Tolerance, Proceedings of the Twenty-Ninth Annual International Symposium on Fault-Tolerant Computing, p.48, June 15-18, 1999
• 20: T. Tabe and Q. F. Stout. The use of the MPI communication library in the NAS parallel benchmarks. Technical Report CSE-TR-386-99, Advanced Computer Architecture Laboratory, Dept. of Electrical Engineering and Computer Science, University of Michigan, 17, 1999.
• 21: NR Adiga , G Almasi , GS Almasi , Y Aridor , R Barik , D Beece , R Bellofatto , G Bhanot , R Bickford , M Blumrich , AA Bright , J Brunheroto , C Caşcaval , J Castaños , W Chan , L Ceze , P Coteus , S Chatterjee , D Chen , G Chiu , TM Cipolla , P Crumley , KM Desai , A Deutsch , T Domany , MB Dombrowa , W Donath , M Eleftheriou , C Erway , J Esch , B Fitch , J Gagliano , A Gara , R Garg , R Germain , ME Giampapa , B Gopalsamy , J Gunnels , M Gupta , F Gustavson , S Hall , RA Haring , D Heidel , P Heidelberger , LM Herger , D Hoenicke , RD Jackson , T Jamal-Eddine , GV Kopcsay , E Krevat , MP Kurhekar , AP Lanzetta , D Lieber , LK Liu , M Lu , M Mendell , A Misra , Y Moatti , L Mok , JE Moreira , BJ Nathanson , M Newton , M Ohmacht , A Oliner , V Pandit , RB Pudota , R Rand , R Regan , B Rubin , A Ruehli , S Rus , RK Sahoo , A Sanomiya , E Schenfeld , M Sharma , E Shmueli , S Singh , P Song , V Srinivasan , BD Steinmacher-Burow , K Strauss , C Surovic , R Swetz , T Takken , RB Tremaine , M Tsao , AR Umamaheshwaran , P Verma , P Vranas , TJC Ward , M Wazlowski , W Barrett , C Engel , B Drehmel , B Hilgart , D Hill , F Kasemkhani , D Krolak , CT Li , T Liebsch , J Marcella , A Muff , A Okomo , M Rouse , A Schram , M Tubbs , G Ulsh , C Wait , J Wittrup , M Bae , K Dockser , L Kissel , MK Seager , JS Vetter , K Yates, An overview of the BlueGene/L Supercomputer, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-22, November 16, 2002, Baltimore, Maryland

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Preprocessors
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Message sending
      D.4.5 Reliability
          Subjects: Fault-tolerance; Checkpoint/restart

General Terms:
Algorithms, Languages, Reliability, Theory

Keywords:
MPI, application-level checkpointing, fault-tolerance, non-FIFO communication, scientific computing