Просмотр статьи


Номер журнала: 2010.2

Заголовок статьи: Оптимизация времени создания и объёма контрольных точек восстановления параллельных программ*)

Резюме

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

Авторы

А.Ю. Поляков, А.А. Данекина

Библиография

1. Хорошевский В.Г. Архитектура вычислительных систем. – М.: МГТУ им. Н.Э. Баума-на, 2008 . 520 с.
2. TOP500 Supercomputer sites [Электронный ресурс]. URL: http://www.top500.org/
3. Fabrizio Petrini and Kei Davis and José 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 Soci-ety, 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. «Check-pointing 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 In-cremental 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 Computa-tions and the Desktop // Proc. of IEEE International Parallel and Distributed Processing Sym-posium (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 In-ternational 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, Net-working, 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 Ap-plied 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 Tech-nical 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)

Ключевые слова

отказоустойчивость, контрольные точки восстановления программ,
распределённые вычислительные системы.

Скачать полный текст