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