基于并发性发掘的低开销回卷恢复实现方法

doi:10.3969/j.issn.1000-3428.2013.11.010

计算机工程

基于并发性发掘的低开销回卷恢复实现方法

袁功彪^a，杨金民^a，白树仁^b

(湖南大学 a. 信息科学与工程学院；b. 超级计算中心，长沙 410082)

收稿日期:2012-12-28 出版日期:2013-11-15 发布日期:2013-11-13
作者简介:袁功彪(1987－)，男，硕士研究生，主研方向：容错计算；杨金民、白树仁，教授、博士
基金资助:
国家自然科学基金资助项目(61272401, 61133005)；湖南省科技计划基金资助重点项目(201GK2003)

Implementation Method of Low Overhead Rollback Recovery Based on Concurrency Exploiting

YUAN Gong-biao ^a, YANG Jin-min^a, BAI Shu-ren ^b

(a. College of Information Science and Engineering; b. Supercomputing Center, Hunan University, Changsha 410082, China)

Received:2012-12-28 Online:2013-11-15 Published:2013-11-13

摘要/Abstract

摘要： 现有的回卷恢复容错技术存在同步约束和阻塞问题，其时间开销随系统节点规模的增大而剧增。为此，提出一种基于并发性发掘的低开销回卷恢复实现方法。利用消息传递附带跟踪消息依赖的策略解除消息日志中的同步约束，解析进程负载以发掘进程负载的并发性，构建进程负载并发执行的实现架构，采用数据缓存策略和多线程技术实现进程内部各负载的并发执行，以降低故障恢复开销。3个NAS NPB2.3标准性能检测程序的实验结果表明，该方法可使检查点开销从0.63 s、3.19 s、1.21 s分别降低到0.18 s、0.67 s、0.19 s，日志开销率从13.4%、3.5%、18.3%分别降低到0.7%、0.1%、1.0%。

关键词: 回卷恢复, 时间开销, 同步约束, 并发性挖掘, 消息日志, 检查点

Abstract: Existing rollback recovery technologies show that their time overheads increase sharply with the scale of nodes due to synchronization constraints and the sequential execution pattern. Aiming at this problem, this paper proposes an implementation method of low overhead rollback recovery based on concurrency exploiting. It uses the strategy of piggybacking dependency on messages to release the message log synchronization constraints. In addition, the workloads in a process is resolved to exploit their concurrency. Then data buffering strategy and multithreading technology are applied to implement the concurrent execution of various process workloads, leading to a low overhead rollback recovery scheme. Experimental results of three NAS NPB2.3 benchmarks show that the overheads of a checkpoint are decreased from 0.63 s, 3.19 s, 1.21 s to 0.18 s, 0.67 s, 0.19 s respectively, and the overhead ratios of message logging are decreased from 13.4%, 3.5%, 18.3% to 0.7%, 0.1%, 1.0% respectively.

Key words: rollback recovery, time overhead, synchronization constraint, concurrency exploiting, message log, checkpoint

中图分类号:

TP391

袁功彪，杨金民，白树仁. 基于并发性发掘的低开销回卷恢复实现方法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2013.11.010.

YUAN Gong-biao, YANG Jin-min, BAI Shu-ren. Implementation Method of Low Overhead Rollback Recovery Based on Concurrency Exploiting[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2013.11.010.

http://www.ecice06.com/CN/Y2013/V39/I11/46

参考文献

参考文献 [1] Guptal R, Naik H, Beckman P. Understanding Checkpointing Overheads on Massive-scale Systems: Analysis of the IBM Blue Gene/P System[J]. International Journal of High Performance Computing Applications, 2011, 25(2): 180-192. [2] Wang Chao, Mueller F, Engelmann C, et al. Hybrid Full/ Incremental Checkpoint/Restart for MPI Jobs in HPC Environments[C]//Proc. of the 16th International Conference on Parallel and Distributed Systems. Washington D. C., USA: IEEE Press, 2011: 524-533. [3] Yang Xuejun, Du Yunfei, Wang Panfeng, et al. FTPA: Suppor- ting Fault-tolerant Parallel Computing Through Parallel Recomputing[J]. IEEE Trans. on Parallel and Distributed Systems, 2009, 20(10): 1471-1486. [4] Elnozahy E, Alvisi L, Wang Yimin, et al. A Survey of Rollback Recovery Protocols in Message Passing Systems[J]. ACM Computing Surveys, 2002, 33(3): 375-408. [5] Chiu G M, Chiu J F. A New Diskless Checkpointing Approach for Multiple Processor Failures[J]. IEEE Trans. on Dependable and Secure Computing, 2011, 8(4): 481-493. [6] Guermouche A, Ropas T, Brunet E. Uncoordinated Check- pointing Without Domino Effect for Send-deterministic MPI Applications[C]//Proc. of IEEE International Parallel & Distributed Processing Symposium. Anchorage, USA: IEEE Press, 2011: 989-1000. [7] Wang Rui, Salzberg B, Lomet D B. Log-based Recovery for Middleware Servers[C]//Proc. of ACM International Con- ference on Management of Data. New York, USA: ACM Press, 2007: 425-436. [8] Li Yawei, Lan Zhiling. FREM: A Fast Restart Mechanism for General Checkpoint/Restart[J]. IEEE Trans. on Computers, 2011, 60(5): 639-652. [9] 富弘毅, 丁滟, 宋伟, 等. 一种利用并行复算实现的OpenMP容错机制[J]. 软件学报, 2012, 23(2): 411-427. [10] Yang Jinmin, Li Kinfun, Li Wenwei. Trading off Logging Overhead and Coordinating Overhead to Achieve Efficient Rollback Recovery[J]. Concurrency and Computation: Practice and Experience, 2009, 21(6): 819-853. [11] NAS Parallel Benchmarks. NASA Ames Research Cen- ter[EB/OL]. [2012-12-30]. http://www.nas.nasa.gov/publica tions/npb.html. [12] Yang Jinmin, Zhang Dafang, Yang Xuedong. WINDAR: A Multithreaded Rollback-recovery Toolkit on Windows[C]// Proc. of the 10th IEEE Pacific Rim Dependable Computing International Symposium. New York, USA: IEEE Press, 2004. [13] Rao S, Alvisi L, Vin H. The Cost of Recovery in Message Logging Protocols[J]. IEEE Transactions on Knowledge and Data Engineering, 2000, 12(2): 160-173. 编辑金胡考

选择文件类型/文献管理软件名称

选择包含的内容

基于并发性发掘的低开销回卷恢复实现方法

Implementation Method of Low Overhead Rollback Recovery Based on Concurrency Exploiting

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

编辑推荐

Metrics

本文评价

[1]	刘浩波,李军义,李仁发. 一种改进的实时嵌入式系统容错优化方法[J]. 计算机工程, 2015, 41(1): 12-18.
[2]	长孙妮妮, 张毅坤, 华灯鑫, 邹子夏, 陈浩. 一种基于B+树的混合索引结构[J]. 计算机工程, 2012, 38(14): 35-37.
[3]	牛如美, 陈雨亭. 一种基于异常处理的并发程序容错机制[J]. 计算机工程, 2012, 38(13): 44-47.
[4]	刘翠英, 高胜法, 王慧丽. 一种高效的协调式检查点算法[J]. 计算机工程, 2011, 37(23): 49-51.
[5]	杨晖;陈闳中. 支持文件迁移的Linux检查点机制的实现[J]. 计算机工程, 2010, 36(3): 266-268.
[6]	余冲;王振兴;郭浩然;刘慧生. 基于监控器时间开销的虚拟机发现方法[J]. 计算机工程, 2009, 35(22): 47-49.
[7]	万国伟;卢宇彤;谢旻;沈志宇. 一种低开销非阻塞的协同式检查点算法[J]. 计算机工程, 2007, 33(24): 66-68.
[8]	周小成;孙凝晖;霍志刚;马捷. 一种降低并行程序检查点开销的方法[J]. 计算机工程, 2007, 33(12): 84-86.
[9]	鄢喜爱;杨金民;田华. 双机容错系统中最佳检查点间隔的分析[J]. 计算机工程, 2007, 33(05): 283-285.
[10]	霍志刚;马捷;孙凝晖. 一个基于通信系统支持的并行检查点系统[J]. 计算机工程, 2007, 33(05): 217-219.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于并发性发掘的低开销回卷恢复实现方法

Implementation Method of Low Overhead Rollback Recovery Based on Concurrency Exploiting

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

编辑推荐

Metrics

本文评价