Оптимизация времени создания и объёма контрольных точек восстановления параллельных программ*)
Аннотация
В работе рассмотрены подходы к формированию инкрементных и дифференциальных контрольных точек восстановления параллельных программ. Описан и исследован алгоритм создания контрольных точек, основанный на хешировании, предложена его параллельная версия. Показано, что для итерационных методов решения сложных задач рассмотренные алгоритмы имеют высокую эффективность и позволяют значительно снизить объем ввода-вывода при создании контрольных точек. Оценена эффективность и масштабируемость параллельной версии алгоритма.
Об авторах
А. Ю. Поляков
Институт физики полупроводников им. А.В. Ржанова СО РАН
Россия
Россия
А. А. Данекина
Россия
Список литературы
1. Хорошевский В.Г. Архитектура вычислительных систем. - М.: МГТУ им. Н.Э. Баумана, 2008. 520 с.
2. TOP500 Supercomputer sites [Электронный ресурс]. URL: http://www.top500.org/
3. 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.
4. 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.
5. T. B. Team. An overview of the BlueGene/L supercomputer. In Proceedings of SC2002: High Performance Networking and Computing, Baltimore, MD, Nov. 2002.
6. 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)
7. 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.
8. 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.
9. 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. 2008
10. 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).
11. 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.
12. 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.
13. 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.
14. 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.
15. Q. Gao, W. Yu, W. Huang, and D. K. Panda. Application-transparent checkpoint/restart for MPI programs over InfiniBand. Parallel Processing, Jan 2006.
16. Paul H. Hargrove and Jason C. Duell. Berkeley Lab Checkpoint/Restart (BLCR) for Linux Clusters. In Proceedings of SciDAC 2006: June 2006.
17. 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.
18. 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.
19. 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 2005
20. Sangho 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, 2006
21. 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.
22. Rsync [Электронный ресурс]. URL: http://rsync.samba.org/. (дата обращения 14.05.2010).
23. Muthitacharoen, A., B. Chen, and D. Mazieres. A Low-bandwidth Network File System. In Symposium on Operating Systems Principles (SOSP). 2001. Banff, Canada.
24. Rivest, R., The MD4 message digest algorithm // Proc. of Advances in Cryptology - CRYPTO'90, pp. 303 − 311, Springer-Verlag, 1991.
25. Rivest, R., The MD5 Message-Digest Algorithm, RFC1321, April 1992
26. FIPS 180-1. Secure Hash Standard. U.S. Department of Commerce/N.I.S.T., National Technical Information Service, Springfield, VA, April 1995.
27. 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.
28. IML++ (Iterative Methods Library) [Электронный ресурс]. URL: http://math.nist.gov/iml (дата обращения 14.05.2010)
29. HBICT (Hash based incremental checkpointing tool) [Электронный ресурс]. URL: http://sourceforge.net/projects/hbict/ (дата обращения 06.06.2010)
Рецензия
Для цитирования:
Поляков А.Ю., Данекина А.А. Оптимизация времени создания и объёма контрольных точек восстановления параллельных программ*). Вестник СибГУТИ. 2010;(2):87-100.
For citation:
A.yu. Polyakov , Danekina A.a. Optimization of size and creation time of parallel programs checkpoints. The Herald of the Siberian State University of Telecommunications and Information Science. 2010;(2):87-100. (In Russ.)
Просмотров:
627
Послать статью по эл. почте 
