Compiler-generated staggered checkpointing

ABSTRACT

To minimize work lost due to system failures, large parallel applications perform periodic checkpoints. These checkpoints are typically inserted manually by application programmers, resulting in synchronous checkpoints, or checkpoints that occur at the same program point in all processes. While this solution is tenable for current systems, it will become problematic for future supercomputers that have many tens of thousands of nodes, because contention for both the network and file system will grow. This paper shows that staggered checkpoints---globally consistent checkpoints in which processes perform checkpoints at different points in the code---can significantly reduce network and file system contention. We describe a compiler-based approach for inserting staggered checkpoints, and we show, using trace-driven simulation, that staggered checkpointing is 23 times faster that synchronous checkpointing.

REFERENCES

• 1: Micah Beck , James S. Plank , Gerry Kingsley, Compiler-Assisted Checkpointing, University of Tennessee, Knoxville, TN, 1994
• 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: NASA Ames Research Center. NAS parallel benchmarks. http://www.nas.nasa.gov/Software/NPB.
• 4: Sung-Eun Choi , Steven J. Deitz, Compiler Support for Automatic Checkpointing, Proceedings of the 16th Annual International Symposium on High Performance Computing Systems and Applications, p.213, June 16-19, 2002
• 5: E. Elnozahy, D. Johnson, and Y. Wang. A survey of rollback-recovery protocols in message-passing systems. Technical Report CMU-CS-96-181, Carnegie Mellon University, October 1996.
• 6: Samuel Z. Guyer , Calvin Lin, Broadway: A Software Architecture for Scientific Computing, Proceedings of the IFIP TC2/WG2.5 Working Conference on the Architecture of Scientific Software, p.175-192, October 02-04, 2000
• 7: Peter Ladkin , Barbara Simons, Compile-time analysis of communicating processes, Proceedings of the 6th international conference on Supercomputing, p.248-259, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143417]
• 8: Peter B. Ladkin and Stefan Leue. Interpreting message flow graphs. Formal Aspects of Computing, 7(5):473--509, 1995.
• 9: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 10: Ozalp Babaoglu , Keith Marzullo, Consistent Global States of Distributed Systems: Fundamental Concepts and Mechanisms, University of Bologna, 1993
• 11: James Steven Plank, Efficient checkpointing on MIMD architectures, Princeton University, Princeton, NJ, 1993
• 12: Nitin H. Vaidya, On Staggered Checkpointing, Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing (SPDP '96), p.572, October 23-26, 1996