sibsutisВестник СибГУТИThe Herald of the Siberian State University of Telecommunications and Information Science1998-6920СибГУТИsibsutis-668Research ArticleСтатьиОптимизация времени создания и объёма контрольных точек восстановления параллельных программ*)Optimization of size and creation time of parallel programs checkpointsПоляковА. Ю.A.yu. Polyakovnoemail@neicon.ruДанекинаА. А.Danekina A.a.noemail@neicon.ruИнститут физики полупроводников им. А.В. Ржанова СО РАНRussian Federation2010160120230287100Copyright © Поляков А.Ю., Данекина А.А., 20232023Поляков А.Ю., Данекина А.А.Поляков А.Ю., Данекина А.А.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.sibsutis.ru/jour/article/view/668

В работе рассмотрены подходы к формированию инкрементных и дифференциальных контрольных точек восстановления параллельных программ. Описан и исследован алгоритм создания контрольных точек, основанный на хешировании, предложена его параллельная версия. Показано, что для итерационных методов решения сложных задач рассмотренные алгоритмы имеют высокую эффективность и позволяют значительно снизить объем ввода-вывода при создании контрольных точек. Оценена эффективность и масштабируемость параллельной версии алгоритма.

An approaches to parallel programs incremental and differential checkpointing are stated. Hash based sequential and parallel algorithms are proposed and investigated. An efficiency of proposed approach for iterative and direct methods for solving complex tasks are shown. Good scalability of parallel version of proposed algorithm is shown.

отказоустойчивостьконтрольные точки восстановления программраспределенные вычислительные системыfault tolerancecheckpoint and recoveryincremental checkpointlarge scale systemsReferencesХорошевский В.Г. Архитектура вычислительных систем. - М.: МГТУ им. Н.Э. Баумана, 2008. 520 с.Хорошевский В.Г. Архитектура вычислительных систем. - М.: МГТУ им. Н.Э. Баумана, 2008. 520 с.TOP500 Supercomputer sites [Электронный ресурс]. URL: http://www.top500.org/TOP500 Supercomputer sites [Электронный ресурс]. URL: http://www.top500.org/Fabrizio Petrini and Kei Davis and Jose Carlos Sancho. System-Level Fault-Tolerance in Large-Scale Parallel Machines with Buffered Coscheduling. In In 9th IEEE Workshop on Fault-Tolerant Parallel, Distributed and Network-Centric Systems (FTPDS04), Santa Fe, NM, April 2004.Fabrizio Petrini and Kei Davis and Jose Carlos Sancho. System-Level Fault-Tolerance in Large-Scale Parallel Machines with Buffered Coscheduling. In In 9th IEEE Workshop on Fault-Tolerant Parallel, Distributed and Network-Centric Systems (FTPDS04), Santa Fe, NM, April 2004.Ian Philp. Software failures and the road to a petaflop machine. In HPCRI: 1st Workshop on High Performance Computing Reliability Issues, in Proceedings of the 11th International Symposium on High Performance Computer Architecture (HPCA-11). IEEE Computer Society, 2005.Ian Philp. Software failures and the road to a petaflop machine. In HPCRI: 1st Workshop on High Performance Computing Reliability Issues, in Proceedings of the 11th International Symposium on High Performance Computer Architecture (HPCA-11). IEEE Computer Society, 2005.T. B. Team. An overview of the BlueGene/L supercomputer. In Proceedings of SC2002: High Performance Networking and Computing, Baltimore, MD, Nov. 2002.T. B. Team. An overview of the BlueGene/L supercomputer. In Proceedings of SC2002: High Performance Networking and Computing, Baltimore, MD, Nov. 2002.Tom Budnik, Brant Knudson, Mark Megerian, Sam Miller. High Throughput Computing on IBM's Blue Gene®/P // IBM Rochester Blue Gene Development. − Режим доступа: http://www-03.ibm.com/systems/resources/HTC_WhitePaper_V2_050508.pdf (дата обращения: 01.06.2010)Tom Budnik, Brant Knudson, Mark Megerian, Sam Miller. High Throughput Computing on IBM's Blue Gene®/P // IBM Rochester Blue Gene Development. − Режим доступа: http://www-03.ibm.com/systems/resources/HTC_WhitePaper_V2_050508.pdf (дата обращения: 01.06.2010)A. B. Nagarajan, F. Mueller, C. Engelmann, and S.L. Scott. Proactive Fault Tolerance for HPC with Xen Virtualization. In Proceedings of the 21st Annual International Conference on Supercomputing (ICS'07), Seattle, WA, June 2007.A. B. Nagarajan, F. Mueller, C. Engelmann, and S.L. Scott. Proactive Fault Tolerance for HPC with Xen Virtualization. In Proceedings of the 21st Annual International Conference on Supercomputing (ICS'07), Seattle, WA, June 2007.Elnozahy E.N., Alvisi L., Wang Y.M., Johnson D.B. A survey of rollback-recovery protocols in message-passing systems // ACM Computing Surveys. - Vol. 34, No 3, 2002. - pp. 375-408.Elnozahy E.N., Alvisi L., Wang Y.M., Johnson D.B. A survey of rollback-recovery protocols in message-passing systems // ACM Computing Surveys. - Vol. 34, No 3, 2002. - pp. 375-408.C. Wang, F. Mueller, C. Engelmann, and S. L. Scott. Proactive process-level live migration in HPC environments. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, Austin, TX, USA, Nov. 2008C. Wang, F. Mueller, C. Engelmann, and S. L. Scott. Proactive process-level live migration in HPC environments. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, Austin, TX, USA, Nov. 2008Ana Maria Visan, Artem Polyakov, Praveen S. Solanki, Kapil Arya, Tyler Denniston, Gene Cooperman Temporal Debugging using URDB, 2009. - Режим доступа: http://arxiv.org/abs/0910.5046v1 (дата обращения: 01.06.2010).Ana Maria Visan, Artem Polyakov, Praveen S. Solanki, Kapil Arya, Tyler Denniston, Gene Cooperman Temporal Debugging using URDB, 2009. - Режим доступа: http://arxiv.org/abs/0910.5046v1 (дата обращения: 01.06.2010).Yi-Min Wang, Yennun Huang, Kiem-Phong Vo, Pi-Yu Chung and Chandra Kintala. «Checkpointing and Its Applications», 25th Annual Int'l symposium on Fault-Tolerant Computing, PP. 22 - 30, Oct. 1995.Yi-Min Wang, Yennun Huang, Kiem-Phong Vo, Pi-Yu Chung and Chandra Kintala. «Checkpointing and Its Applications», 25th Annual Int'l symposium on Fault-Tolerant Computing, PP. 22 - 30, Oct. 1995.Xiangyu Dong, Naveen Muralimanohar, Norman P. Jouppi, Yuan Xie. A Case Study of Incremental and Background Hybrid In-Memory Checkpointing, The Exascale Evaluation and Research Techniques Workshop (EXERT) at ASPLOS 2010, March 2010.Xiangyu Dong, Naveen Muralimanohar, Norman P. Jouppi, Yuan Xie. A Case Study of Incremental and Background Hybrid In-Memory Checkpointing, The Exascale Evaluation and Research Techniques Workshop (EXERT) at ASPLOS 2010, March 2010.J. Ansel, K. Arya, G. Cooperman. DMTCP: Transparent Checkpointing for Cluster Computations and the Desktop // Proc. of IEEE International Parallel and Distributed Processing Symposium (IPDPS'09). IEEE Press, 2009.J. Ansel, K. Arya, G. Cooperman. DMTCP: Transparent Checkpointing for Cluster Computations and the Desktop // Proc. of IEEE International Parallel and Distributed Processing Symposium (IPDPS'09). IEEE Press, 2009.J. Hursey, J. M. Squyres, T. I. Mattox, and A. Lumsdaine. The design and implementation of checkpoint/restart process fault tolerance for Open MPI. In Proceedings of the 21st IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE Computer Society, March 2007.J. Hursey, J. M. Squyres, T. I. Mattox, and A. Lumsdaine. The design and implementation of checkpoint/restart process fault tolerance for Open MPI. In Proceedings of the 21st IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE Computer Society, March 2007.Q. Gao, W. Yu, W. Huang, and D. K. Panda. Application-transparent checkpoint/restart for MPI programs over InfiniBand. Parallel Processing, Jan 2006.Q. Gao, W. Yu, W. Huang, and D. K. Panda. Application-transparent checkpoint/restart for MPI programs over InfiniBand. Parallel Processing, Jan 2006.Paul H. Hargrove and Jason C. Duell. Berkeley Lab Checkpoint/Restart (BLCR) for Linux Clusters. In Proceedings of SciDAC 2006: June 2006.Paul H. Hargrove and Jason C. Duell. Berkeley Lab Checkpoint/Restart (BLCR) for Linux Clusters. In Proceedings of SciDAC 2006: June 2006.S. Agarwal, R. Garg, M. S. Gupta, and J. E. Moreira. Adaptive incremental checkpointing for massively parallel systems. In ICS 2004, pages 277 - 286, 2004.S. Agarwal, R. Garg, M. S. Gupta, and J. E. Moreira. Adaptive incremental checkpointing for massively parallel systems. In ICS 2004, pages 277 - 286, 2004.R. C. Burns and D. D. E. Long, «Efficient distributed backup with delta compression». In Proceedings of the 1997 I/O in Parallel and Distributed Systems (IOPADS'97), San Jose, CA, USA, Nov. 1997.R. C. Burns and D. D. E. Long, «Efficient distributed backup with delta compression». In Proceedings of the 1997 I/O in Parallel and Distributed Systems (IOPADS'97), San Jose, CA, USA, Nov. 1997.Jose Carlos Sancho, Song Jiang, Fabrizio Petrini, Kei Davis. Transparent, Incremental Checkpointing at Kernel Level: A Foundation for Fault Tolerance for Parallel Computers // In Proceedings of the 2005 International Conference for High Performance Computing, Networking, Storage and Analysis (Supercomputing 2005), Seattle, WA, November 2005Jose Carlos Sancho, Song Jiang, Fabrizio Petrini, Kei Davis. Transparent, Incremental Checkpointing at Kernel Level: A Foundation for Fault Tolerance for Parallel Computers // In Proceedings of the 2005 International Conference for High Performance Computing, Networking, Storage and Analysis (Supercomputing 2005), Seattle, WA, November 2005Sangho Yi, Junyoung Heo, Yookun Cho, Jiman Hong. Adaptive page-level incremental checkpointing based on expected recovery time // Proc. of the 2006 ACM symposium on Applied computing table of contents Dijon, France, pp. 1472 - 1476, 2006Sangho Yi, Junyoung Heo, Yookun Cho, Jiman Hong. Adaptive page-level incremental checkpointing based on expected recovery time // Proc. of the 2006 ACM symposium on Applied computing table of contents Dijon, France, pp. 1472 - 1476, 2006S.A. Kiswany, M. Ripeanu, S. S. Vazhkudai, A. Gharaibeh, «stdchk: A Checkpoint Storage System for Desktop Grid Computing», Proc. of ICDCS 2008, Beijing, China, 2008.S.A. Kiswany, M. Ripeanu, S. S. Vazhkudai, A. Gharaibeh, «stdchk: A Checkpoint Storage System for Desktop Grid Computing», Proc. of ICDCS 2008, Beijing, China, 2008.Rsync [Электронный ресурс]. URL: http://rsync.samba.org/. (дата обращения 14.05.2010).Rsync [Электронный ресурс]. URL: http://rsync.samba.org/. (дата обращения 14.05.2010).Muthitacharoen, A., B. Chen, and D. Mazieres. A Low-bandwidth Network File System. In Symposium on Operating Systems Principles (SOSP). 2001. Banff, Canada.Muthitacharoen, A., B. Chen, and D. Mazieres. A Low-bandwidth Network File System. In Symposium on Operating Systems Principles (SOSP). 2001. Banff, Canada.Rivest, R., The MD4 message digest algorithm // Proc. of Advances in Cryptology - CRYPTO'90, pp. 303 − 311, Springer-Verlag, 1991.Rivest, R., The MD4 message digest algorithm // Proc. of Advances in Cryptology - CRYPTO'90, pp. 303 − 311, Springer-Verlag, 1991.Rivest, R., The MD5 Message-Digest Algorithm, RFC1321, April 1992Rivest, R., The MD5 Message-Digest Algorithm, RFC1321, April 1992FIPS 180-1. Secure Hash Standard. U.S. Department of Commerce/N.I.S.T., National Technical Information Service, Springfield, VA, April 1995.FIPS 180-1. Secure Hash Standard. U.S. Department of Commerce/N.I.S.T., National Technical Information Service, Springfield, VA, April 1995.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.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.IML++ (Iterative Methods Library) [Электронный ресурс]. URL: http://math.nist.gov/iml (дата обращения 14.05.2010)IML++ (Iterative Methods Library) [Электронный ресурс]. URL: http://math.nist.gov/iml (дата обращения 14.05.2010)HBICT (Hash based incremental checkpointing tool) [Электронный ресурс]. URL: http://sourceforge.net/projects/hbict/ (дата обращения 06.06.2010)HBICT (Hash based incremental checkpointing tool) [Электронный ресурс]. URL: http://sourceforge.net/projects/hbict/ (дата обращения 06.06.2010)

The authors declare that there are no conflicts of interest present.