应用级checkpointing技术的研究与实现

论文摘要

随着系统规模的不断扩大和COTS器件制造工艺的不断发展,高性能计算机面临着严峻的可靠性挑战。应用级checkpointing技术是应对这一挑战的关键技术。但是,当前应用级checkpointing技术面临着性能优势无法充分发挥以及不方便使用的问题。本文致力于高效易用的应用级checkpointing技术的研究与实现,着重研究了应用级checkpoint的优化保存问题,应用级checkpoint全局状态一致性问题,多checkpoint的总开销最优化问题和应用级checkpointing技术易用性问题。本文的主要贡献可概括为以下几点:1、针对现有活跃变量分析方法不能对MPI并行程序进行准确分析的问题,我们定义了MPI并行程序进程间和进程内的定值-引用关系,并提出了MPI并行程序活跃变量分析方法——LAMP。LAMP克服了传统活跃变量分析方法既不能区分同一个变量在各进程上不同的活跃性、也不能分析跨进程定值-引用关系的缺点,它是优化应用级checkpoint数据量从而减小checkpoint开销的基础技术。2、深入研究了应用级checkpoint的优化保存问题。我们首先分析了MPI并行程序计算状态的组成,确定了对其中占主要部分的各进程计算状态进行优化的思想;然后提出了一种基于LAMP的应用级checkpointing技术。实验结果表明该技术能够有效减小checkpoint数据量和减小checkpoint开销。3、深入研究了全局checkpoint数据的一致性问题。我们提出了一个基于编译分析保持应用级checkpoint数据一致性的新方法。该方法不需要记录checkpointing期间的early或late消息,而是通过静态分析找出MPI程序中安全的checkpointing区域的方法,在安全的checkpointing区内保存应用级checkpoint时不需要记录任何消息。实验证明该方法简单有效。4、深入研究了多个checkpoint的总开销最小化问题,提出了一种优化设置多个checkpoint位置的方法。由于应用级checkpointing开销主要来自写checkpoint文件的时间,我们首先将求解最小的checkpoint总开销近似为求解最小的checkpoint总数据量。然后将多checkpoint的优化设置问题抽象为一个类似于0-1整数规划的数学问题。最后给出了两种求解算法。5、针对应用级checkpointing的易用性问题,我们设计并实现了一个源到源的预编译器ALEC,它可以非常方便地将普通的Fortran77/MPI程序转换成具有高效的应用级checkpointing功能的容错程序。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题背景
• 1.1.1 高性能计算的普及应用
• 1.1.2 高性能计算面临的可靠性挑战
• 1.2 相关研究工作
• 1.2.1 容错的基本概念和常用方法
• 1.2.2 Rollback-recovery 容错技术分析
• 1.2.3 优化checkpoint 开销的相关研究
• 1.2.4 相关工作小结
• 1.3 课题研究内容
• 1.3.1 课题来源
• 1.3.2 课题研究重点
• 1.3.3 课题研究难点
• 1.4 本文的主要工作和创新
• 1.5 Checkpointing 技术的几个术语
• 1.6 论文结构
• 第二章 MPI 并行程序活跃变量分析方法——LAMP
• 2.1 MPI 并行程序分析
• 2.1.1 并行编程模型
• 2.1.2 并行程序的实现方式
• 2.1.3 MPI 程序设计与执行的特点
• 2.2 MPI 程序的应用级checkpoint 数据
• 2.2.1 一个MPI 程序实例
• 2.2.2 并行程序活跃变量的定义
• 2.3 LAMP
• 2.3.1 分析块与MPI 程序流图
• 2.3.2 LAMP 分析方法
• 2.3.3 LAMP 方法举例
• 2.4 本章小节
• 第三章 基于LAMP 的应用级checkpointing 技术
• 3.1 求解指定checkpoint 位置各进程上的活跃变量集合的算法
• 3.1.1 初始分析
• 3.1.2 更新
• 3.1.3 Checkpoint 数据量最小化问题
• 3.1.4 增量式checkpointing
• 3.2 选择合适的checkpoint 位置
• 3.2.1 一般算法
• 3.2.2 简化算法
• 3.3 应用级checkpoint 的保存和恢复
• 3.3.1 保存和恢复应用程序的执行位置
• 3.3.2 保存和恢复应用状态
• 3.3.3 处理MPI 库状态
• 3.3.4 应用状态保存和恢复方法的特点
• 3.4 实验评估
• 3.4.1 实验方法
• 3.4.2 实验结果
• 3.5 本章小结
• 第四章 应用级checkpoint 数据的一致性问题研究
• 4.1 问题背景
• 4.1.1 一致性问题的几个基本概念
• 4.1.2 现有解决方法分析
• 4.1.3 小结
• 4.2 安全的checkpointing 区
• 4.2.1 强一致性的概念
• 4.2.2 安全的checkpointing 区
• 4.3 识别安全的checkpointing 区
• 4.3.1 MPI 程序特征分析
• 4.3.2 识别通信线/区
• 4.4 实验评估
• 4.4.1 实验设置
• 4.4.2 实验结果
• 4.5 本章小结
• 第五章 多checkpoint 的优化设置
• 5.1 问题背景
• 5.2 数学模型及求解
• 5.2.1 问题一：程序中已有N 个checkpoint 指令
• 5.2.2 问题二：程序中没有checkpoint 指令
• 5.3 实验评估
• 5.3.1 实验设置
• 5.3.2 实验结果
• 5.4 本章小结
• 第六章 ALEC 系统的设计与实现
• 6.1 ALEC 的结构和实现
• 6.1.1 词法分析
• 6.1.2 分块并创建流图
• 6.1.3 识别安全的checkpointing 区
• 6.1.4 活跃变量分析
• 6.1.5 Checkpoints 选择
• 6.1.6 插入保存与恢复代码
• 6.2 ALC-Tool 的设计方案
• 6.3 本章小结
• 第七章 结束语
• 7.1 工作总结
• 7.2 研究展望
• 致谢
• 参考文献
• 攻读博士学位期间已发表和待发表的论文
• 攻读博士学位期间参与的科研项目