Performance evaluation of automatic checkpoint-based fault tolerance for AMPI and Charm++

ABSTRACT

As the size of high performance clusters multiplies, the probability of system failure grows substantially, posing an increasingly significant challenge for scalability. Checkpoint-based fault tolerance methods are effective approaches at dealing with faults. With these methods, the state of the entire parallel application is checkpointed to reliable storage. When a fault occurs, the application is restarted from a recent checkpoint. However, the application developer is required to write significant additional code for checkpointing and restarting. This paper describes disk-based and memory-based checkpointing fault tolerance schemes that automate the task of checkpointing and restarting. The schemes also allow the program to be restarted on a different number of processors. These schemes are based on self-checkpointable, migratable objects supported by the Adaptive MPI (AMPI) and Charm++ run-time and can be applied to a wide class of applications written using MPI or message-driven languages. We demonstrate the effectiveness of the strategies and evaluate their performance.

REFERENCES

• 1: NR Adiga, G Almasi, GS Almasi, Y Aridor, R Barik, D Beece, R Bellofatto, G Bhanot, R Bickford, M Blumrich, AA Bright, and J. An overview of the bluegene/1 supercomputer, 2002.
• 2: Lorenzo Alvisi , Sriram Rao , Syed Amir Husain , Asanka de Mel , Elmootazbellah Elnozahy, An Analysis of Communication-Induced Checkpointing, Proceedings of the Twenty-Ninth Annual International Symposium on Fault-Tolerant Computing, p.242, June 15-18, 1999
• 3: Gabriel Antoniu , Luc Bougé , Raymond Namyst, An Efficient and Transparent Thread Migration Scheme in the PM2 Runtime System, Proceedings of the 11 IPPS/SPDP'99 Workshops Held in Conjunction with the 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing, p.496-510, April 12-16, 1999
• 4: Amnon Barak , Shai Guday , Richard G. Wheeler, The MOSIX Distributed Operating System: Load Balancing for UNIX, Springer-Verlag New York, Inc., Secaucus, NJ, 1993
• 5: Milind A. Bhandarkar , Laxmikant V. Kalé, A Parallel Framework for Explicit FEM, Proceedings of the 7th International Conference on High Performance Computing, p.385-394, December 17-20, 2000
• 6: D. Briatico, A. Ciuffoletti, and L. Simoncini. A distributed domino-effect free recovery algorithm. In IEEE International Symposium on Reliability, Distributed Software, and Databases, pages 207--215, December 1984.
• 7: Greg Bronevetsky , Daniel Marques , Keshav Pingali , Paul Stodghill, Automated application-level checkpointing of MPI programs, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 8: 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]
• 9: Charm++ website. http://charm.cs.uiuc.edu/.
• 10: Yuqun Chen, Kai Li, and James S. Plank. CLIP: A checkpointing tool for message-passing parallel programs. 1997.
• 11: Epcc blue gene/1. http://www.epcc.ed.ac.uk/.
• 12: Chao Huang. System support for checkpoint and restart of charm++ and ampi applications. Master's thesis, Dept. of Computer Science, University of Illinois, 2004.
• 13: Chao Huang, Orion Lawlor, and L. V. Kalé. Adaptive MPI. In Proceedings of the 16th International Workshop on Languages and Compilers for Parallel Computing (LCPC 2003), LNCS 2958, pages 306--322, College Station, Texas, October 2003.
• 14: Chao Huang , Gengbin Zheng , Laxmikant Kalé , Sameer Kumar, Performance evaluation of adaptive MPI, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1122976]
• 15: Rashmi Jyothi, Orion Sky Lawlor, and L. V. Kale. Debugging support for Charm++. In PADTAD Workshop for IPDPS 2004, page 294. IEEE Press, 2004.
• 16: Laxmikant V. Kalé. The virtualization model of parallel programming: Runtime optimizations and the state of art. In LACSI 2002, Albuquerque, October 2002.
• 17: James S. Plank , Micah Beck , Gerry Kingsley , Kai Li, Libckpt: Transparent Checkpointing under Unix, University of Tennessee, Knoxville, TN, 1994
• 18: James S. Plank and Kai Li. Faster checkpointing with n+1 parity. In 24th Annual International Symposium on Fault-Tolerant Computing, June 1994.
• 19: B. Randell. System structure for software fault-tolerance. In IEEE Trans. on Software on Software Engineering, volume SE-1 (2), pages 226--232, June 1975.
• 20: Georg Stellner, CoCheck: Checkpointing and Process Migration for MPI, Proceedings of the 10th International Parallel Processing Symposium, p.526-531, April 15-19, 1996
• 21: Y. Tamir and C. Equin. Error recovery in multicomputers using global checkpoints. In 13th International Conference on Parallel Processing, pages 32--41, August 1984.
• 22: Turing cluster. http://www.cse.uiuc.edu/turing.
• 23: Yi-Min Wang, Space reclamation for uncoordinated checkpointing in message-passing systems, University of Illinois at Urbana-Champaign, Champaign, IL, 1993
• 24: Gengbin Zheng. Achieving High Performance on Extremely Large Parallel Machines: Performance Prediction and Load Balancing. PhD thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, 2005.
• 25: Gengbin Zheng , Lixia Shi , L. V. Kale, FTC-Charm++: an in-memory checkpoint-based fault tolerant runtime for Charm++ and MPI, Proceedings of the 2004 IEEE International Conference on Cluster Computing, p.93-103, September 20-23, 2004

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Checkpoint/restart

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance

General Terms:
Performance, Reliability