容错并行算法的研究与分析
发布时间：2023-09-18 19:31
随着系统规模的增加,大规模并行计算机的平均故障间隔时间远低于许多大规模科学应用的运行时间,因此大规模科学应用必须能够容忍硬件错误。传统的回滚恢复协议是目前大规模系统中常用的容错技术,在恢复时失效进程上的计算全部在一个处理器上重算。这是对计算资源的浪费,也使得恢复时间不可能小于前一个检查点和故障发生时刻之间的时间间隔。 为了缩短故障恢复时间,本文提出了一种新的容错方法:容错并行算法。文章从容错并行算法的理论基础、概念、设计方法及支撑工具等几个方法对容错并行算法进行了深入的研究,并对容错并行算法的性能进行了分析和测试。本文所做的创新工作主要体现在以下几点: 1、给出了并行计算在系统出现故障的情况下的可靠性定义,并基于任务依赖图给出了并行计算可靠性的定量分析方法;基于此分析方法,分析和比较了时间冗余和空间冗余的容错技术对并行计算可靠性的影响。 2、为了缩短故障恢复时间,有效提高并行计算的可靠性,提出了一种新的容错方法:容错并行算法。容错并行算法执行时在数据保存段保存计算的中间状态以保证故障时正确的复算;发生故障时未发生故障的处理器通过在线的方式感知故障处理机的故障,并自动通过并行复算恢复故障...
【文章页数】：136 页
【学位级别】：博士
【文章目录】：
摘要
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 研究展望
致谢
参考文献
攻读博士学位期间已发表和待发表的论文
攻读博士学位期间参与的科研项目
本文编号：3848146
【文章页数】：136 页
【学位级别】：博士
【文章目录】：
摘要
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 研究展望
致谢
参考文献
攻读博士学位期间已发表和待发表的论文
攻读博士学位期间参与的科研项目
本文编号：3848146
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/3848146.html
