优秀研究生学位论文题录展示

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

专 业: 计算机科学与技术
关键词: 高性能计算 可靠性 容错并行算法 设计方法 性能分析
分类号: TP301
形 态: 共 123 页 约 80,565 个字 约 3.854 M内容
阅 读: 全文阅读说明

内容摘要


随着系统规模的增加,大规模并行计算机的平均故障间隔时间远低于许多大规模科学应用的运行时间,因此大规模科学应用必须能够容忍硬件错误。

传统的回滚恢复协议是目前大规模系统中常用的容错技术,在恢复时失效进程上的计算全部在一个处理器上重算。

这是对计算资源的浪费,也使得恢复时间不可能小于前一个检查点和故障发生时刻之间的时间间隔。

为了缩短故障恢复时间,本文提出了一种新的容错方法:

容错并行算法。

文章从容错并行算法的理论基础、概念、设计方法及支撑工具等几个方法对容错并行算法进行了深入的研究,并对容错并行算法的性能进行了分析和测试。

本文所做的创新工作主要体现在以下几点:

1、给出了并行计算在系统出现故障的情况下的可靠性定义,并基于任务依赖图给出了并行计算可靠性的定量分析方法;基于此分析方法,分析和比较了时间冗余和空间冗余的容错技术对并行计算可靠性的影响。

2、为了缩短故障恢复时间,有效提高并行计算的可靠性,提出了一种新的容错方法:

容错并行算法。

容错并行算法执行时在数据保存段保存计算的中间状态以保证故障时正确的复算;发生故障时未发生故障的处理器通过在线的方式感知故障处理机的故障,并自动通过并行复算恢复故障处理器上的负载。

容错并行算法充分发挥无故障进程的计算能力,加速故障恢复过程,缩短了故障恢复时间,使得恢复时间可以远低于checkpoint和发生故障时刻之间的时间间隔。

3、容错并行算法设计的基本思想是以程序段为基础,添加数据保存段,故障检测段和复算段构成相应的容错程序段。

本文系统地讨论了容错并行算法的设计方法,提出了面向容错并行算法的程序段的划分方法以及分割和合并原则;利用面向并行程序的定值-引用关系确定状态保存段中所需保存的数据;给出了两种复算段中并行复算代码的设计方法:

基于循环并行化以及基于模板的方法。

同时,还针对矩阵LU分解、快速傅里叶变换以及桶排序等三类典型的并行应用,设计并实现了其相应的容错并行算法。

4、为了降低容错并行算法给用户带来的编程负担,本文实现了一个面向MPI程序的容错并行算法设计的支撑工具GiFT。

GiFT通过编译指导的方法实现程序段的划分;利用面向并行程序的控制流分析以及数据流分析方法自动确定保存的数据,实现了容错并行算法数据保存的低开销以及数据保存段的自动设计:

通过编译指导的方法,实现了基于循环并行化以及基于模板的并行复算代码生成的自动化。

5、容错并行算法的性能分析与实验。

首先,给出了故障情况下的容错并行算法的性能度量,建立了考虑系统故障情况下的性能模型来预测容错并行算法的完成时间,并以此为基础评估了程序段的运行时间、数据保存开销、故障率以及并行复算加速比等系统参数对容错并行算法性能的影响;随后,针对科学计算中的6个典型测试用例在一个1024个处理器的集群系统上对容错并行算法的性能进行了测试并与系统级checkpointing方法进行了对比,这6个典型测试用例包括矩阵乘程序和5个NPB核心测试用例(EP、IS、CG、MG和FT)。

结果表明与checkpointing方法相比,容错并行算法有性能上的优势..……

全文目录


文摘
英文文摘
论文说明:图表目录
第一章 绪论
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研究展望
参考文献

相似论文

  1. 基于涌现视角的多Agent系统分析研究,172页,TP301.6 TP181
  2. 相似矩阵与谱聚类,62 页,TP301.6 TP311.13
  3. 改进的粒子群算法及其在控制器参数整定中的应用,54页,TP301.6
  4. 动态可重构片上系统的任务在线放置和调度算法研究,51页,TP301.6 TP311.52
  5. 关联规则算法的研究,61页,TP301.6
  6. 主题爬虫搜索Web页面策略的研究,62页,TP301.6 TP393.092
  7. 基于纹理的高质量矢量可视化研究,145页,TP301.6 TP391.41
  8. 基于智能优化算法的体绘制研究,133页,TP301.6 TP391.41
  9. 跨智能空间上下文共享研究,120页,TP301.5
  10. 基于多个通道的概率进程演算模型,68页,TP301
  11. 高可用双机容错系统软件健壮性测试,63页,TP302.8 TP311.52
  12. 商业自动化系统数据安全技术的研究,51页,TP309 F716
  13. CA认证中心密钥生成与私钥封装系统的设计与实现,79页,TP309.7
  14. 基于Linux的可穿戴计算机导航定位系统设计与实现,70页,TP302.1
  15. 同时多线程踪迹处理器后端实现与研究,47页,TP302.1
  16. 基于准则和策略的自治式多agent服务协同体系研究,134页,TP301
  17. 虚拟域可信链的设计与实现,69 页,TP309.1
  18. 可信计算平台中TOCTOU攻击的响应方法,67 页,TP309.1
  19. 高性能DSP指令控制部件优化设计研究,74页,TP302.2
  20. 用于灾难恢复的远程备份系统的研究,68页,TP309.3
中图分类: > TP301 > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法

© 2012 book.hzu.edu.cn