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