Collective operations in application-level fault-tolerant MPI

ABSTRACT

Fault-tolerance is becoming a critical issue on high-performance platforms. Checkpointing techniques make programs fault-tolerant by saving their state periodically and restoring this state after failure. System-level checkpointing saves the state of the entire machine on stable storage, but this usually has too much overhead. In practice, programmers do manual checkpointing by writing code to (i) save the values of key program variables at critical points in the program, and (ii) restore the entire computational state from these values during recovery. However, this can be difficult to do in general MPI programs without global barriers.In an earlier paper, we presented a distributed checkpoint coordination protocol which handles MPI's point-to-point constructs, while dealing with the unique challenges of application-level checkpointing. The protocol is implemented by a thin software layer that sits between the application program and the MPI library, so it does not require any modifications to the MPI library. However, it did not handle collective communication, which is a very important part of MPI. In this paper, we extend the protocol to handle MPI's collective communication constructs. We also present experimental results that show that the overhead introduced by the protocol for collective operations is 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: 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
• 3: D. Cameron and G. Regnier. The Virtual Interface Architecture. Intel Press, San Francisco, California, first edition, 2002.
• 4: 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]
• 5: Cornell Theory Center. Online at http://www.tc.cornell.edu/, 2003.
• 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: Emulex corporation. Overview of Giganet cLAN. Online at http://www.emulex.com/ts/legacy/clan/index.htm, 2003.
• 9: M. P. I. Forum. Overview of the MPI standard. Online at http://www.mpi-forum.org/, 2003.
• 10: 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.
• 11: National Nuclear Security Administration. ASCI home. Online at http://www.nnsa.doe.gov/asc/, 2002.
• 12: OpenMP. Overview of the OpenMP standard. Online at http://www.openmp.org/, 2003.
• 13: James S. Plank , Micah Beck , Gerry Kingsley , Kai Li, Libckpt: Transparent Checkpointing under Unix, University of Tennessee, Knoxville, TN, 1994
• 14: 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
• 15: Georg Stellner, CoCheck: Checkpointing and Process Migration for MPI, Proceedings of the 10th International Parallel Processing Symposium, p.526-531, April 15-19, 1996

INDEX TERMS

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

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

General Terms:
Algorithms, Languages, Reliability, Theory

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