容错并行算法的研究与分析

论文摘要

随着系统规模的增加,大规模并行计算机的平均故障间隔时间远低于许多大规模科学应用的运行时间,因此大规模科学应用必须能够容忍硬件错误。传统的回滚恢复协议是目前大规模系统中常用的容错技术,在恢复时失效进程上的计算全部在一个处理器上重算。这是对计算资源的浪费,也使得恢复时间不可能小于前一个检查点和故障发生时刻之间的时间间隔。为了缩短故障恢复时间,本文提出了一种新的容错方法:容错并行算法。文章从容错并行算法的理论基础、概念、设计方法及支撑工具等几个方法对容错并行算法进行了深入的研究,并对容错并行算法的性能进行了分析和测试。本文所做的创新工作主要体现在以下几点:1、给出了并行计算在系统出现故障的情况下的可靠性定义,并基于任务依赖图给出了并行计算可靠性的定量分析方法;基于此分析方法,分析和比较了时间冗余和空间冗余的容错技术对并行计算可靠性的影响。2、为了缩短故障恢复时间,有效提高并行计算的可靠性,提出了一种新的容错方法:容错并行算法。容错并行算法执行时在数据保存段保存计算的中间状态以保证故障时正确的复算;发生故障时未发生故障的处理器通过在线的方式感知故障处理机的故障,并自动通过并行复算恢复故障处理器上的负载。容错并行算法充分发挥无故障进程的计算能力,加速故障恢复过程,缩短了故障恢复时间,使得恢复时间可以远低于checkpoint和发生故障时刻之间的时间间隔。3、容错并行算法设计的基本思想是以程序段为基础,添加数据保存段,故障检测段和复算段构成相应的容错程序段。本文系统地讨论了容错并行算法的设计方法,提出了面向容错并行算法的程序段的划分方法以及分割和合并原则;利用面向并行程序的定值-引用关系确定状态保存段中所需保存的数据;给出了两种复算段中并行复算代码的设计方法:基于循环并行化以及基于模板的方法。同时,还针对矩阵LU分解、快速傅里叶变换以及桶排序等三类典型的并行应用,设计并实现了其相应的容错并行算法。4、为了降低容错并行算法给用户带来的编程负担,本文实现了一个面向MPI程序的容错并行算法设计的支撑工具GiFT。GiFT通过编译指导的方法实现程序段的划分;利用面向并行程序的控制流分析以及数据流分析方法自动确定保存的数据,实现了容错并行算法数据保存的低开销以及数据保存段的自动设计;通过编译指导的方法,实现了基于循环并行化以及基于模板的并行复算代码生成的自动化。5、容错并行算法的性能分析与实验。首先,给出了故障情况下的容错并行算法的性能度量,建立了考虑系统故障情况下的性能模型来预测容错并行算法的完成时间,并以此为基础评估了程序段的运行时间、数据保存开销、故障率以及并行复算加速比等系统参数对容错并行算法性能的影响;随后,针对科学计算中的6个典型测试用例在一个1024个处理器的集群系统上对容错并行算法的性能进行了测试并与系统级checkpointing方法进行了对比,这6个典型测试用例包括矩阵乘程序和5个NPB核心测试用例（EP、IS、CG、MG和FT）。结果表明与checkpointing方法相比,容错并行算法有性能上的优势。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 大规模系统的可靠性问题
• 1.1.1 单芯片处理器制造工艺不断发展
• 1.1.2 大规模系统的规模不断增加
• 1.1.3 大规模系统的可靠性受到挑战
• 1.1.4 软件实现的硬件容错
• 1.2 容错研究基础
• 1.2.1 基本概念
• 1.2.2 并行程序的故障类型
• 1.3 课题研究内容
• 1.3.1 课题来源
• 1.3.2 课题研究重点
• 1.3.3 课题研究难点
• 1.4 相关研究工作
• 1.4.1 Checkpointing 技术.
• 1.4.2 消息日志
• 1.4.3 MPI 容错
• 1.4.4 基于算法的容错
• 1.4.5 其它工作
• 1.5 本文的主要工作和创新
• 1.6 论文结构
• 第二章 并行计算的可靠性分析
• 2.1 面向可靠性分析的并行程序任务依赖图模型
• 2.1.1 任务依赖图模型的提出
• 2.1.2 并行程序的任务依赖图模型
• 2.1.3 任务依赖图的组成
• 2.2 并行计算的可靠性计算
• 2.2.1 规则和定律
• 2.2.2 任务结点可靠度的计算
• 2.2.3 并行计算可靠度的计算
• 2.3 并行计算的容错技术分析
• 2.3.1 时间冗余技术
• 2.3.2 空间冗余技术
• 2.3.3 冗余技术讨论
• 2.4 小结
• 第三章 容错并行算法的概念与设计方法
• 3.1 基本思想
• 3.1.1 一个例子
• 3.1.2 与传统方法的比较
• 3.2 容错并行算法的概念
• 3.3 设计方法
• 3.3.1 程序段的划分
• 3.3.2 故障检测段的设计方法
• 3.3.3 数据保存段的设计方法
• 3.3.4 复算段的设计方法
• 3.4 小结
• 第四章 容错并行算法的设计与分析
• 4.1 容错并行算法的分类
• 4.2 矩阵LU 分解的容错并行算法.
• 4.2.1 矩阵LU 分解的算法描述.
• 4.2.2 矩阵LU 分解的容错并行算法设计与分析.
• 4.3 快速傅里叶变换的容错并行算法
• 4.3.1 快速傅里叶变换的算法描述
• 4.3.2 FFT 的容错并行算法设计与分析
• 4.4 排序算法的容错并行算法
• 4.4.1 桶排序的算法描述
• 4.4.2 桶排序的容错并行算法设计与分析
• 4.5 小结
• 第五章 容错并行算法的编译辅助工具
• 5.1 程序段选择的实现
• 5.2 故障检测段的实现
• 5.3 状态保存段的实现
• 5.3.1 控制流分析
• 5.3.2 数据流分析
• 5.3.3 保存代码生成
• 5.4 复算段的实现
• 5.4.1 恢复数据代码生成
• 5.4.2 并行复算代码生成
• 5.5 小结
• 第六章 容错并行算法的性能分析与实验
• 6.1 容错并行算法的开销来源
• 6.2 容错并行算法的性能度量
• 6.2.1 执行时间
• 6.2.2 加速比
• 6.2.3 效率
• 6.3 系统参数对容错并行算法性能的影响
• 6.3.1 程序段的运行时间对性能的影响
• 6.3.2 数据保存开销对性能的影响
• 6.3.3 故障率对性能的影响
• 6.3.4 并行复算加速比对性能的影响
• 6.4 实验配置
• 6.5 实验性能
• 6.6 实验结论
• 6.7 小结
• 第七章 结束语
• 7.1 工作总结
• 7.2 研究展望
• 致谢
• 参考文献
• 攻读博士学位期间已发表和待发表的论文
• 攻读博士学位期间参与的科研项目