Adaptive incremental checkpointing for massively parallel systems

ABSTRACT

Given the scale of massively parallel systems, occurrence of faults is no longer an exception but a regular event. Periodic checkpointing is becoming increasingly important in these systems. However, huge memory footprints of parallel applications place severe limitations on scalability of normal checkpointing techniques. Incremental checkpointing is a well researched technique that addresses scalability concerns, but most of the implementations require paging support from hardware and the underlying operating system, which may not be always available. In this paper, we propose a software based adaptive incremental checkpoint technique which uses a secure hash function to uniquely identify changed blocks in memory. Our algorithm is the first self-optimizing algorithm that dynamically computes the optimal block boundaries, based on the history of changed blocks. This provides better opportunities for minimizing checkpoint file size. Since the hash is computed in software, we do not need any system support for this. We have implemented and tested this mechanism on the BlueGene/L system. Our results on several well-known benchmarks are encouraging, both in terms of reduction in average checkpoint file size and adaptivity towards application's memory access patterns.

REFERENCES

• 1: Nitin H. Vaidya, Impact of Checkpoint Latency on Overhead Ratio of a Checkpointing Scheme, IEEE Transactions on Computers, v.46 n.8, p.942-947, August 1997 [doi>10.1109/12.609281]
• 2: J. S. Plank , W. R. Elwasif, Experimental Assessment of Workstation Failures and Their Impact on Checkpointing Systems, Proceedings of the The Twenty-Eighth Annual International Symposium on Fault-Tolerant Computing, p.48, June 23-25, 1998
• 3: J. S. Plank, J. Xu, and R. H. Netzer, "Compressed differences: An algorithm for fast incremental checkpointing," Tech. Rep. CS-95-302, University of Tennessee at Knoxville, Aug. 1995.
• 4: K. Li , J. F. Naughton , J. S. Plank, Low-Latency, Concurrent Checkpointing for Parallel Programs, IEEE Transactions on Parallel and Distributed Systems, v.5 n.8, p.874-879, August 1994 [doi>10.1109/71.298215]
• 5: M. Litzkow, T. Tannenbaum, J. Basney, and M. Livny, "Checkpoint and migration of UNIX processes in the Condor distributed processing system," Tech. Rep. UW-CS-TR-1346, University of Wisconsin - Madison Computer Sciences Department, April 1997.
• 6: Princeton University Scalable I/O Research, "A checkpointing library for Intel Paragon." http://www.cs.princeton.edu/sio/CLIP/.
• 7: J. S. Plank, M. Beck, G. Kingsley, and K. Li, "Libckpt: Transparent checkpointing under Unix," in Usenix Winter Technical Conference, pp. 213--223, Jan. 1995.
• 8: M. Elnozahy, L. Alvisi, Y. Wang, and D. Johnson, "A survey of rollback-recovery protocols in message passing systems," Tech. Rep. CMU-CS-96-181, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA, Oct. 1996.
• 9: Yuqun Chen , James S. Plank , Kai Li, CLIP: a checkpointing tool for message-passing parallel programs, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-11, November 15-21, 1997, San Jose, CA [doi>10.1145/509593.509626]
• 10: 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]
• 11: Pei Dan , Wang Dongsheng , Zhang Youhui , Shen Meiming, Quasi-asynchronous migration: a novel migration protocol for PVM tasks, ACM SIGOPS Operating Systems Review, v.33 n.2, p.5-14, April 1999 [doi>10.1145/311094.311100]
• 12: 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
• 13: C. J. Li and W. K. Fuch, "CATCH - Compiler assisted techniques for checkpointing.," in In Proceedings of the Internationnal Symposium on Fault Tolerant Computing, June 1990.
• 14: Adnan Agbaria , James S. Plank, Design, Implementation, and Performance of Checkpointing in NetSolve, Proceedings of the 2000 International Conference on Dependable Systems and Networks (formerly FTCS-30 and DCCA-8), p.49, June 25-28, 2000
• 15: James S. Plank , Kai Li , Michael A. Puening, Diskless Checkpointing, IEEE Transactions on Parallel and Distributed Systems, v.9 n.10, p.972-986, October 1998 [doi>10.1109/71.730527]
• 16: James S. Plank , Kai Li, ickp: A Consistent Checkpointer for Multicomputers, IEEE Parallel & Distributed Technology: Systems & Technology, v.2 n.2, p.62-67, June 1994 [doi>10.1109/88.311574]
• 17: Jim Pruyne , Miron Livny, Managing Checkpoints for Parallel Programs, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.140-154, April 16, 1996
• 18: E. Pinheiro, "Truly-transparent checkpointing of parallel applications." http://www.cs.rutgers.edu/~edpin/epckpt/paper_html/.
• 19: S. Sankaran, J. Squyres, B. Barrett, A. Lumsdaine, J. Duell, P. Hargrove, and E. Roman, "The design and implementation of Berkeley lab's Linux checkpoint/restart," in Los Alamos Computer Science Institute (LACSI) Symposium, Oct. 2003.
• 20: H. Zhong and J. Nieh, "CRAK: Linux checkpoint/restart as a kernel module," Tech. Rep. CUCS-014-01, Department of Computer Science, Columbia University, Nov. 2001.
• 21: Milos Prvulovic , Zheng Zhang , Josep Torrellas, ReVive: cost-effective architectural support for rollback recovery in shared-memory multiprocessors, Proceedings of the 29th annual international symposium on Computer architecture, p.111, May 25-29, 2002, Anchorage, Alaska
• 22: Daniel J. Sorin , Milo M. K. Martin , Mark D. Hill , David A. Wood, SafetyNet: improving the availability of shared memory multiprocessors with global checkpoint/recovery, Proceedings of the 29th annual international symposium on Computer architecture, p.123, May 25-29, 2002, Anchorage, Alaska
• 23: J. C. Sancho, F. Petrini, G. Johnson, J. Fernandez, and E. Frachtenberg, "On the feasibility of incremental checkpointing for scientific computing," in International Parallel and Distributed Processing Symposium, (Santa Fe, NM, USA), April 2004.
• 24: H. Nam, J. Kim, S. J. Hong, and S. Lee, "Probabilistic checkpointing," IEICE Transactions, Information and Systems, vol. E85-D, July 2002.
• 25: E. N. Elnozahy, How Safe is Probabilistic Checkpointing?, Proceedings of the The Twenty-Eighth Annual International Symposium on Fault-Tolerant Computing, p.358, June 23-25, 1998
• 26: Hyochang Nam , Jong Kim , Sung Je Hong , Sunggu Lee, Secure checkpointing, Journal of Systems Architecture: the EUROMICRO Journal, v.48 n.8-10, p.237-254, March 2003 [doi>10.1016/S1383-7621(02)00137-6]
• 27: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 28: SUN Microsystems Inc.,, "Soft memory errors and their effect on sun fire system." http://www.sun.com/products-n-solutions/hardware/docs/pdf/816-5053-10.pdf.
• 29: 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
• 30: G. Almasi, R. Bellofatto, J. Brunheroto, C. Ca|scaval, J. G. Castaqos, L. Ceze, P. Crumley, C. C. Erway, J. Gagliano, D. Lieber, X. Martorell, J. E. Moreira, A. Sanomiya, , and K. Strauss, "An Overview of the BlueGene/L System Software Organization," in Euro-Par: 9th International European Conference on Parallel Processing, Aug. 2003.
• 31: D. Bailey, T. Harris, W. Saphir, R. vander Wijngaart, A. Woo, and M. Yarros, "The NAS parallel benchmarks 2.0," Tech. Rep. NAS-95-020, NAS Systems Division, Dec. 1995.
• 32: "ASCI blue benchmarks." http://www.llnl.gov/asci_benchmarks/asci/asci_code_list.html.

INDEX TERMS

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

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

General Terms:
Algorithms, Experimentation, Performance, Reliability

Keywords:
fault-tolerance, incremental checkpoint, large scale systems, probabilistic checkpoint