异构并行计算机容错技术研究

StudyandImplementationofFault

ToleranceforHeterogeneousParallel

ComputerCandidate：JiaJiaSupervisor：Prof.YangXuejunAdissertationSubmittedinpartialfulHllmentoftherequirements

forthedegreeofDoctorofEngineering

inComputerScienceandTechnology

GraduateSchoolofNationalUniversityofDefenseTechnology

Changsha,Hunan,P.R.ChinaSeptember,2011独创性声明本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研究成果。尽我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学位或证书而使用过的材料。与我ー同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文题目:异构并行计算机容错技术研究 学位论文作者签名:日期: 年月日学位论文版权使用授权书本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允许论文被查阅和借阅;可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密学位论文在解密后适用本授权书。）学位论文题目:异构并行计算机

容错技术研究学位论文作者签名：日期：年月日作者指导教师签名： 日期: 年月日目录TOC\o"1-5"\h\z\o"CurrentDocument"摘要 i\o"CurrentDocument"Abstract iii\o"CurrentDocument"第一章绪论 1\o"CurrentDocument"课题背景 1异构并行计算机的兴起 1大规模并行系统的可靠性问题 4大规模异构并行计算机面临的可靠性挑战 6\o"CurrentDocument"容错研究基础 9容错基本概念 9故障类型 10故障模型 11\o"CurrentDocument"相关研究工作 11容错常用方法 11Rollback-recovery容错技术分析 13TMR容错技术分析 14Checkpointing容错技术分析 15优化checkpoint的相关研究 16异构并行计算机现有容错方法 17\o"CurrentDocument"本文主要研究内容 18\o"CurrentDocument"本文主要工作和创新 20\o"CurrentDocument"论文结构 21\o"CurrentDocument"第二章计算可接受模型 23\o"CurrentDocument"面向一般计算系统的计算可接受模型 23\o"CurrentDocument"面向异构并行计算系统的计算可接受模型 25\o"CurrentDocument"容错机制对异构系统可接受度的影响 27带TMR异构系统可接受模型分析 27带C/R异构系统可接受模型分析 30\o"CurrentDocument"本章小结 33第三章 基于异构系统故障传播行为分析的应用级checkpoint的数据量优化方法 35TOC\o"1-5"\h\z\o"CurrentDocument"问题背景 35CG调用 35CG调用流图 37异构系统故障传播与CG调用流图 39\o"CurrentDocument"异构系统故障传播行为 40CG间故障传播 41G点内故障传播 42\o"CurrentDocument"异构系统的应用级checkpoint数据优化方法 45基于故障传播行为的checkpoint数据分析 45Checkpoint的位置选择 47\o"CurrentDocument"实验评估 49实验方法 49实验结果 50\o"CurrentDocument"本章小结 54\o"CurrentDocument"第四章 异构系统应用级checkpoint的优化设置研究 55\o"CurrentDocument"问题背景 55异构系统程序特征分析 55问题提出 57\o"CurrentDocument"全局checkpoint数据保存开销最小化问题 58场景一:基于同步机制的checkpoint优化设置 58场景二:基于异步机制的checkpoint优化设置 65Checkpoint数据保存偏移量设置优化问题 71\o"CurrentDocument"实验评估 73实验方法 73实验结果 74\o"CurrentDocument"本章小结 76\o"CurrentDocument"第五章 面向GPU的多副本容错技术 79\o"CurrentDocument"基于冗余线程的GPU多副本容错技术的基本思想 79问题背景 79解决方案 80\o"CurrentDocument"RB-TMR的设计和实现方法 82创建冗余代理 83基于RB-TMR机制的GPUKernel的设计 84比较与投票 87第II贝TOC\o"1-5"\h\z\o"CurrentDocument"RB-TMR编译工具的设计与实现 90RB-TMR的编译实现框架 90前端分析器 91数据流分析器 91代码重写器 93\o"CurrentDocument"性能评估 94实验方法 94实验结果 95\o"CurrentDocument"本章小结 99\o"CurrentDocument"第六章 结论与展望 101\o"CurrentDocument"工作总结 101\o"CurrentDocument"研究展望 102\o"CurrentDocument"致谢 103\o"CurrentDocument"参考文献 105\o"CurrentDocument"作者在学期间取得的学术成果 117\o"CurrentDocument"作者在学期间参加的科研项目 119表目沃TOC\o"1-5"\h\z表3.1Checkpointing的时间开销 51表3.2Checkpoint数据存储空间开销 52表4.1Checkpoint数量 74表4.2Checkpoint数据保存时间开销 74表5.1无故障情况下带有三种容错机制的程序执行时间 96攵、、攵、、冬冬冬^图图图义、冬冬图图图冬冬图目录TOC\o"1-5"\h\z图1.1TOP500中机器的处理器数目统计图 2图1.2高性能计算机的性能发展趋势 2图1.3Intel处理器电源电压的变化趋势 4图1.4Top500前20台超级计算机系统的平均处理器核心数量 5图1.5不同规模下系统的MTBF变化趋势 6图1.6处理器和存储器的性能增长速度四 8图1.7故障、错误与失效三者的关系 9图1.8 容错方法分类 13图1.9 基本TMR系统结构 14图1.10 Checkpointing技术 15图2.1计算可接受模型的概念体系 23图2.2多次执行下程序运行结果的可接受 24图2.3异构并行系统上的程序执行 26TMR容错示意图 28GPUTMRDA-DA,的变化曲线 29带TMR系统单次执行与该系统多次执行可接受比较 30C/R容错示意图 31带C/R系统单次执行与该系统多次执行可接受比较 33同构与异构系统算法执行流程 36CUDA上的矩阵乘算法 36SWIM异构系统CG调用流图 38CG间的数据传播 39G点内故障传递 43G点内故障影响集求解算法 45CUDA上的Checkpointing流程 46一般算法的基本思想 48选择合适的checkpoint位置的一般算法 48无CPU-GPU传输状态checkpointing的执行时间增加比 513.11时间开销减少百分比 52图3.12有CPU-GPU传输状态checkpointing的优化收益 53图4.1异构系统体系结构 561^14.2异相系统矩・阵乘算法流程 戻图4.3 同步执行checkpointing的流程 59图4.4同步设置CPU-GPU端checkpoint 60图4.5 C_Struct的数据结构 61图4.6同步机制Checkpoint间隔与程序的期望执行时间“5。1 62图4.7模型(4.3)的求解算法 64图4.8异步执行checkpointing的流程 65图4.9异步设置CPU-GPU端checkpoint 66图4.10异步机制checkpoint间隔与程序的期望执行时间 69图4.11模型(4.12)的求解算法 71图4.12偏移量ん中的checkpoint位置选取 72佟14,13一次同步与异步checkpointing时间开销 75图4.14同步与异步设置下全局checkpointing时间开销 75图5.1两种容错方法 81图5.2ー个异构程序及对应的RB-TMR容错版本 82图5.3ー个Kernel的线程组织方式 83图5.4单GPU时的冗余代理线程组织方式 83图5.5多GPU时的冗余代理线程组织方式 84图5.6重设计的Kernel代码 85图5.7ー个异构程序示例 86图5.8多GPU的RB-TMR机制的示例代码 87图5.9TMR与RB-TMR比较投票机制流程 88图5.10多GPU的RB-TMR机制的示例代码 89图5.11 比较与投票算法 90图5.12TriKerneling的框架图 91图5.13 矩阵乘的CUDA程序 92图5.14矩阵乘CUDA程序的控制流图 93图5.15RB-TMR程序对比checkpointing程序的平均回滚次数 96图5.16RB-TMR程序对比checkpointing程序的执行时间 97图5.17RB-TMR程序对比TMR程序的执行时间 97图5.18RB-TMR对比checkpointing的容错开销 98图5.19RB-TMR对比TMR的容错开销 98摘要并行计算是实现超高性能计算的主要技术手段。当前,随着GPGPU性能的不断提高,利用CPU和GPU构建的异构并行系统已经成为高性能计算机领域的研究热点。然而随着并行计算系统规模的不断增长,高性能计算机面临严峻的挑战。由于异构并行系统更为复杂的体系结构以及其特有的性质,且商用GPGPU容错能カ较弱,所以由CPU和GPU构建的大规模异构并行系统的可靠性问题更为尖锐,尚缺乏实用的容错手段。本文针对异构并行计算机的容错技术展开研究,以异构并行系统硬件故障在软件中的传播行为为理论基础,对应用级checkpointing技术的保存数据量优化问题进行研究;分析了异构并行系统多checkpoint的全局开销最优化问题，并提出了设置方案;同时,针对异构并行系统提出了一种新的面向GPU的多副本容错技术RB-TMR,并对其所具备的关键机制进行了详细的研究与设计实现。本文的主要贡献如下:1、提出了一种面向一般计算系统的计算可接受模型。建立程序的执行结果可接受以及可接受度的定义,并进ー步定义程序多次执行的可接受和多次执行的可接受度，以此为基础得到可接受度的相关定理和推论。针对异构并行系统将可接受度的相关定理和推论进行了扩展,并建立异构并行系统的可接受模型，同时进ー步案例分析两种常见的容错技术checkpoint/restart和TMR应用到异构并行系统上时,对可接受模型的影响，从而给出容错机制的指导意见和优化方法。2、基于过程间相关性理论，提出了由CPU和GPU构成的异构并行系统中硬件故障在软件中传播行为描述方法,我们称其为故障传播模型。同时,根据故障传播模型,设计了针对该系统的checkpointing机制,并针对影响checkpoint/restart开销的主要问题之 checkpoint保存数据量进行了优化。实验证明该优化方法可以有效的减小开销，提高容错性能。3、深入研究了面向异构并行系统的多个checkpoint的全局开销最小化问题,提出了面向异构并行系统的同步及异步两种机制的多checkpoint全局开销最小化的优化设置方法。首先提出了两个针对优化设置多个checkpoint位置的基本问题。然后通过对异构并行系统体系结构和程序特性的分析,提出了基于两种机制的异构并行系统的多checkpoint设置方法;同步及异步机制的checkpoint设置方法。同时,根据checkpoint优化设置的两个具体问题分别对这两种机制进行优化设置分析和数学建模，并给出了相应的求解算法。4、提出了一种回滚机制与TMR技术相结合的容错技术RB-TMR。这ー技术可以有效应对fail-stop故障与瞬时故障两种类型的故障进行容错,我们给出了这一技术的实现方法,并针对异构并行系统体系结构及程序模型的特征对其中关键机制的设计进行了具体分析和讨论。同时,设计并实现了一个面向RB-TMR机制的源到源编译辅助工具,可以辅助用户面向CUDA程序完成RB-TMR机制的实现,减轻了用户实现RB-TMR机制的负担。实验结果表明RB-TMR技术能够实现较高的错误检出和纠正率,有效减小可能需要回滚恢复的概率,根据综合评定,其相对于传统checkpointing及TMR技术有更好的容错性能。关键词:高性能计算;异构并行计算机;容错;可接受;应用级checkpointing；过程间相关性;故障传播行为第ii贝AbstractParallelcomputingisamajorultra-high-performancecomputingtechnology.AstheperformanceofGPGPU(GeneralPurposecomputationonGraphicProcessingUnits)keepsimproving,heterogeneousparallelsystemsbuiltbasedonCPUandGPUbecomeahotresearchfieldofhigh-performancecomputers.However,withtheincreaseoftheparallelcomputingsystemsize,high-performancecomputersencounterseriouschallenges.Duetomorecomplicatedarchitectureanduniquefeaturesofheterogeneousparallelsystemsandweakfault-toleranceofGPGPU,largescaleheterogeneousparallelsystemsbuiltbasedonCPUandGPUundergoesanacutereliabilityissue,whichislackofpracticalmeans.Thispaperstudiesthefault-tolerancetechniqueofheterogeneousparallelsystems.Basedonthepropagationbehaviorsofhardwareerrorthatpropagatesinsoftwareinheterogeneousparallelsystems,thispaperoptimizescheckpointsizeofapplicationlevelcheckpointing,optimizestheglobaloverheadofmultiplecheckpointsinheterogeneousparallelsystemsandproposesconfigurationsolution,andexploresaGPU-orientedmulti-copiesfaulttolerancetechnique(RB-TMR).Themaincontributionsofthepaperaresummarizedasfollows:Ageneralcomputerorientedacceptancemodelisproposed.Theacceptanceanditsdegreeofprogramresultsandmultipletimesofprogramexecutionarefirstdefined.Basedonthem,theoremsandcorollariesregardingacceptancedegreeareobtained.Thispaperextendsthetheoremsandcorollariesinheterogeneousparallelsystemsandestablishestheacceptancemodelofheterogeneousparallelsystems.Casesareusedtoanalyzetheeffectoftwocommonfault-tolerancetechniques(checkpoint/restartandTMR)ontheacceptancemodelwhenthetwotechniquesareappliedinheterogeneousparallelsystems.Therefore,constructivesuggestionsandoptimizationmethodsforfault-tolerancemechanismareobtained.Basedonthetheoryaboutinter-proceduraldependence,amethodnamederrorpropagationmodelisproposed.ItdescribestheprorogationbehaviorofhardwareerrorinsoftwareinCPU-GPUheterogeneousparallelsystems.Usingthismodel,thesystem'scheckpointingmechanismisdesignedandthecheckpointsizeisoptimized.Experimentalresultsshowthatthismethodcaneffectivelyreducetheoverheadandimprovethefaulttoleranceperformance.Inordertominimizetheglobaloverheadofmultiplecheckpoints,thispaperproposesaplacementoptimizationmethodforbothsynchronizationandasynchronizationmechanismsinheterogeneousparallelsystems.Firstofall,twoessentialissuesofplacementoptimizationofmultiplecheckpointlocationsareproposed.Secondly,basedontheanalysisofarchitectureandprogramfeatures,twomethodsof国防科学技术大学研究生院博士学位论文checkpointplacementinheterogeneousparallelsystemsareproposed:synchronouscheckpointplacementandasynchronouscheckpointplacement).Further,forthetwoissues,thetwomethodsareanalyzedandmodeledandtheirsolutionalgorithmsaregiven.Afault-tolerancetechnique(RB-TMR)combiningrollbackmechanismandTMRtechniqueisproposed.Itcaneffectivelyofferfault-toleranceforfail-stopfaultandtransientfault.Weimplementthistechniqueaccordingtoarchitectureandprogramfeaturesofheterogeneousparallelsystems.Besides,asource-to-sourcecompileassistanttoolisdesignedfortheRB-TMRtechnique.ThetoolcanassistusersinimplementingtheRB-TMRtechniqueinCUDAprograms,alleviatingtheirburdens.ExperimentalresultsexhibitthattheRB-TMRtechniquecanachievehigherrorcheckingandcorrectionrateaswellasdecreasestheprobabilityofrollback.ItisconcludedthattheRB-TMRtechniquedemonstratesbetterfault-toleranceperformancethantheconventionalcheckpointingandTMRtechnique.Keywords：High-performancecomputing,heterogeneousparallelsystems,fault-tolerance,acceptance,application-levelcheckpointing,inter-proceduraldependence,faultpropagationbehavior第一章绪论课题背景大规模科学计算一直是推动高性能计算机迅速发展的主要动カ。今天的科学家更加依赖于高性能计算机来处理空前庞大的数据集以及实现空前复杂的模拟仿真。当前,随着GPGPU(GeneralPurposecomputationonGraphicProcessingUnits)“性能的不断提高,利用CPU和GPU(GraphicsProcessingUnits)构建的异构系统已经成为高性能计算机⑵す领域的研究热点,我国首台千万亿次计算机天河(Tianhe-1A)⑷就是一个典型案例。另ー方面,随着并行计算系统规模的不断增长，系统可靠性越来越低，已成为并行计算向大规模扩展的ー个不容忽视的制约因素。由于商用GPGPU容错能力较弱,所以由CPU和GPU构建的大规模异构并行系统的可靠性问题更为尖锐，尚缺乏实用的容错手段。因此,对于面向异构并行计算机的容错技术研究也变得尤为重要。异构并行计算机的兴起随着计算机技术的高速发展,高性能计算机已成为基础科学领域研究中必不可少的工具。当前,高性能计算可用于解决国防建设和经济发展中重大应用问题的基础性、前瞻性与战略性关键技术,广泛应用于核武器研究、生物信息技术、医疗和新药研究、计算化学、GIS、CAE、气象预报、エ业设计以及环境保护等与国家安全和国民经济密切相关的各个领域。随着竞争的加剧和应用的普及，高性能计算技术已从少数军工部门和国家实验室普遍进入到各大公司、企业和院校。科学研究、工业制造和商业活动中越来越多地使用高性能计算机来解决实际问题。日本政府于2007年启动了一项超长期天气预报计划。借助于日本海洋科学技术中心横浜研究所的“地球模拟器(EarthSimulator)w»对未来30年内可能发生的台风、暴风雪、干旱以及其它恶劣天气进行预测。计算结果可以帮助政府提前采取应对灾害天气的相应措施，减小经济损失。美国GM、GE、日本Nissan等著名大公司拥有总计算能力超过10万亿次的高性能计算机用于新产品的研发。Google公司一直在努力争取使用户的请求可以在0.5秒内处理完成［叫为了实现这一目标，Google公司开发了一个大规模的集群系统Googleclustero在2003年初,Googlecluster就拥有了超过30,000个处理器,并且仍在不断扩展规模以提高性能此ユ近年来,随着高性能计算技术的普遍应用,高性能计算机的发展呈现出两大

趋势:ー是广泛使用通用的、低成本的商用器件(Commericaloff-the-shelf,COTS),以缩短研制周期和降低研制成本;二是系统规模持续增长,以满足科研和生产活动对更高计算能力的不断追求。图1.!显示了近6年来Top500⑷中机器的处理器数目统计情况,由此可见高性能计算机包含的处理器数在不断增加。但同时,低可靠的COTS器件的广泛使用降低了高性能计算机各结点的可靠性，也降低了系统的整体可靠性;而系统规模的大幅增长则会显著降低系统的平均故障间隔时间(MeanTimeBetweenFailures,MTBF)〇图!.1TOP500中机器的处理器数目统计图图1.2高性能计算机的性能发展趋势为「满足高性能计算领域日益攀升的计算需求,高性能计算机系统的规模不断增大,峰值计算速度不断提高。超级计算机的峰值计算速度基本遵循一千倍”定律，即每十年系统性能提升1000倍。目前超级计算机已经突破千万亿次大关,正在向百万万亿次系统迈进。图1.2给出了Top500⑷中的高性能计算机从1993年一直到2011年的性能发展情况以及未来的趋势。可以看到,无论排名第一还是最后一名,其发展情况都是ー样的,其中当前排名第一的日本计算机ー“京”的峰值性能已经达到了8.162Pflop/s,而到2019年,这ー数值将达到1Eflop/s,是当前最快计算机的1000倍。就目前看来这是极为惊人的数字,但是按照以往的发展趋势来看,这ー预测毫不为过。由于高性能计算领域中处理器制程、架构技术、多核技术、节能技术、软件优化技术的高速发展,以及各大厂商对于高新产品不遗余力的快速部署与应用，使得现今的高性能计算正在以更快的速度发展。近10年以来,微处理器已经逐渐从依靠提高处理器频率转向增加处理器并行度的方式来获得持续的性能提升。自2000年以来,处理器频率发展十分缓慢,取而代之的是处理器核数量的增加，以此维持微处理器继续沿摩尔定律发展。因此，以CELL网、Clearspeed⑼和GPU1'01为代表的众核体系结构应运而生。与多核微处理器相比,众核体系结构将更多的晶体管应用于计算单元,有效提高了芯片的性能功耗比;与此同时,众核体系结构具有相对简单的控制逻辑，因此通常作为通用微处理器的加速部件,以提高典型科学计算应用的计算速度。近年来，在各种新的架构及加速部件飞速兴起和发展的同时,GPU也得到了高速的发展。由于GPU适合于并行数值计算的特性,使得高性能计算领域对其ー直看好,而在此基础上发展起来的GPGPU更是由于强大的并行处理能力和可编程流水线,使得其在面对单指令流多数据流（SIMD）且数据处理的运算量要远大于数据调度和传输的需求时,能够取得远超传统CPU的性能。由此而发展起来的由CPU和GPU构建的异构并行计算机也受到越来越多研究者的关注。事实上,利用GPU的计算能力进行高性能计算的异构并行计算机已经受到绝大多数科学领域的研究人员的青睐,包括大气模型,高能量物理,宇宙学,量子化学,分子动力学,甚至药物设计⑴】。当前,随着异构并行处理思想的逐渐成熟以及异构并行体系结构技术的发展,国际上越来越多的异构并行系统涌现出来。HP、IBM、Cray等各大厂商都纷纷推出了自己的异构并行计算机,我国的异构并行计算机也在这次高性能计算机系统发展的研究热潮中脱颖而出。由国防科学技术大学研制的天河一号高性能计算机系统荣登2010年11月Top500排名之首,实现了我国千万亿次高性能计算机零的突破;此外，由曙光公司研制的星云系统在Top500中位列第三,这两台高性能计算机系统的发布极大地提高了我国在国际高性能计算领域的地位。而在最新发布的2011年Top500排名中,前五台超级计算机中有三台都是采用了异构并行体系结构模型。可以看出,异构并行系统作为ー种新兴的体系结构,逐渐被越来越多的高性能计算研究机构采纳,其高效能优势将有力推动高性能计算的发展。最后需要说明的是，文章在后面章节中出现的异构系统是我们对于由CPU和GPU构建的异构并行系统的简称，与异构并行计算机和异构并行系统的概念是相同的。大规模并行系统的可靠性问题可靠性是高性能计算领域的经典问题之一。随着高性能计算在应用领域的逐渐普及和发展,以及大规模并行系统规模的不断扩大,提高可靠性的需求越来越迫切;而高性能计算机所呈现出的发展趋势则使得可靠性问题面临着更加严峻的挑战。微处理器的可靠性问题目前,微处理器芯片制造工艺已经达到数十纳米的量级,例如Intel公布的32纳米Corei3,i5,i7处理器［⑵⑶和AMD公布的45纳米Phenom处理器口支随着集成电路的特征尺寸不断减小,工作频率不断提高,芯片的供电电压也在不断降低,图1.3显示了!ntel处理器供电电压逐年降低的情况けL图1.3Intel图1.3Intel处理器电源电压的变化趋势(と36"10>A_ddns工作电压低意味着保持稳定的逻辑状态所需要的电量少,也就是说逻辑状态翻转所需要的电量少,根据文献［16］,在目前的工艺水平下,逻辑状态翻转所需要的电量已经达到了若干个飞库这ー量级。因此随着集成电路特征尺寸的减小、电源电压的降低和频率的升高，微处理器对各种电磁场、辐射源等外界环境的干扰将更加敏感，并可能引发错误的操作,导致了微处理器的故障发生率不断攀升,微处理器的可靠性不断降低〇另一方面,微处理器的功耗密度在不断增加,功耗密度每18-24月增加一倍,这称为功耗的摩尔定律“久功耗密度的增加使得热量对系统可靠性的影响加剧;改善的工艺往往采用更低的供电电压,这会导致切换电流的噪声影响恶化。这些因素都会影响系统部件的可靠性,从而进ー步影响了系统的可靠性。系统部件的温度在不断上升,一般来说,在2ドC基础上,温度每升高10"C,系统的失效率就会提高一倍"明系统规模扩大对可靠性的影响直到目前为止,提高计算机性能的主要手段仍是增加处理器数目。图1.4给岀了2000年以来Top500前20台超级计算机的处理器数目平均值。由此可见,高性能计算机的规模在迅速扩大。当前世界上最快也是规模最大的计算机,日本的“京”由68544个SPARC64VHIfx处理器组成,每个处理器均内置8个内核,总内核数量高达548,352个ひ】。而排在第20名的CrayXE6,其处理器核心数也达到了42,712〇从可靠性理论的角度看,如果单个部件的可靠性是固定的,那么在没有额外容错措施的情况下,构成系统的部件越多系统的可靠性就会越低。160000160000140000120000100000800006000040000200000图1.4Top500前20台超级计算机系统的平均处理器核心数量图1.5给出了在单结点可靠度R=0.99999的情况下,根据图1.4中的节点数量计算而得出的系统MTBF时间。MTBF的计算公式为:MTBF«—\-Rn其中N为节点数量。由图1.5中可以看出,系统的MTBF随系统规模的增大,降低幅度也很大,在处理器规模为148933时,MTBF只有1.3小时左右。图1.5不同规模下系统的MTBF变化趋势相关数据显示,当一台大规模的!BM/LLNLASCIWhite系统在持续运行过程中,其MTBF最多不超过40个小时1电,而一台拥有8000个节点的Google集群系统,其单节点失效率达到了2-3%/年のし那么换ー种说法,其MTBF也仅仅为36小时⑶】。可见,系统规模的急剧扩大必将导致系统的平均故障时间间隔(MTBF)大幅降低。另一方面,目前的科学计算程序往往需要连续运行几天甚至几个月，例如BlueGene上的蛋白质折叠(protein-folding)程序需要运行好几个月,科学计算程序难以在大规模系统上正确地完成计算。所以,可靠性问题已成为高性能计算机发展的重大挑战之一。Petaflop规模的计算的成功取决于大规模系统可靠性技术的发展，如何确保其上运行的科学计算程序能够正确地完成是大规模计算机系统必须解决的重大问题之一［22,231。大规模异构并行计算机面临的可靠性挑战异构并行计算机由于具有强大的GPU并行处理能力,使其与传统的同构系统相比拥有更高的并行计算性能。然而由于其更为复杂的架构、更高的功耗和不同于目前已经比较成熟的同构系统计算机的编程模型,使得异构并行计算机面临更多方面的问题。与大规模并行系统所面临的可靠性问题相同,由于商用GPU的可靠性相比通用处理器来说更低,因此异构并行计算机的可靠性问题也更为严峻。虽然GPU拥有超越CPU的强大计算能力,但是它并不能取代CPU来处理一些一般事务性的应用。一般的异构系统由CPU和GPU组成,它们之间通过PCI-E总线相连,各自的存储系统可以通过DMA操作来进行大块的数据传输。当ー个异构程序在异构系统上运行时,CPU和GPU之间是ー种主从关系,CPU负责主控程序的执行,以调用的方式启动GPU进行异步运算,同时与GPU进行通信;GPU响应CPU发起的调用,并完成计算。可见,异构并行计算机在体系结构上相对于传统的同构计算机更为复杂，而这种体系结构所具有的特性也为其带来了许多新的问题。因此对于异构并行计算机而言,所需考虑的可能会影响其可靠性的因素也必然更多。«编程复杂引发的可靠性问题异构并行系统的出现进ー步增加了大规模并行系统编程难度陰旬,由于异构并行系统集成有多种类型的处理器,而不同类型的处理器可能具有不同的体系结构抽象层次，因此异构混合编程模型成为当前异构并行系统编程的主要方式。通常,异构混合编程模型融合有多种不同抽象层次的编程模型,极大地增加了大规模并行系统的编程和调试难度。此外，由于GPU具有极高数量的核心和超高的并行计算能力，其利用并行多线程来处理海量的数据，更为复杂的线程及寄存器管理机制也导致了程序员需要更加细致地分配和使用各类系统资源。以NVIDIA提供的CUDA编程模型为例,程序员需要综合考虑线程空间、寄存器、片上软件管理存储等资源以最大化GPU的执行性能。这些都使得面向异构并行系统的编程变得更为复杂和困难，而将一般的科学计算程序修改为专门应用于异并行系统时也更容易出现错误,由此引发可靠性问题。•GPU部件的可靠性问题GPU中晶体管的集成度相比CPU更高,同时具有更多的流计算单元以供计算,NVIDIA最新发布的Fermi架构GPU具有512个处理器核心。因此其可靠度相对于CPU更低。«功耗引发的可靠性问题在整个异构系统的计算过程中GPU负载了绝大部分计算,这也使其功耗更高。虽然相对以往的处理器而言,以CELL和GPU等为代表的加速部件已经有效地提高了系统性能功耗比，缓解了高性能计算的功耗问题，但是对于大规模高性能的异构并行计算机而言,其高功耗问题依然存在の，2句。当前的大规模异构并行系统中，Tianhe-IA系统功耗是4.04MW127],而星云(Nebulae)也达到了2.58MW。巨大的功耗会使系统部件的温度升高,高温环境下运行也提高了芯片的失效率,从而导致计算机系统可靠度的下降。•存储引发的可靠性问题如同一般计算机的内存ー样,GPU的存储系统主要也是用于存储GPU端计算

时所必需的或者计算处理后的临时数据,一般GPU存储系统都采用RAM存储器,这一存储器虽然具有超高的访问速度,但也具有易失性和对静电敏感等特性,容易造成数据流失及由于故障而引发数据错误,因此其可靠性必然远低于计算机中的硬盘等外存设备。•通信引发的可靠性问题异构并行计算机在运行大规模的科学计算程序时,需要CPU与GPU之间的不断通信,因此PCI-E总线作为CPU和GPU通信的外部设备，其可靠性问题对于整个系统就显得至关重要。同时,由于GPU端存储空间非常小,而在大规模计算时可能需要保存大量的状态数据，这就使得GPU在保存所需数据时必须将数据传输到CPU端，进行CPU与GPU的数据传递,而在多次大量数据的传输过程中也可能会出现由故障引发的错误,这对于当前的各种大规模科学计算程序而言,异构并行计算机在通信的数据传输过程中出现由故障引发错误的概率将会是极大的,由通信而导致的可靠性问题极为严峻。可见,由于异构并行计算机对于CPU和GPU间通信的高依赖性,针对异构并行计算机在通信可靠性问题上的研究也更为至关重要。•通信瓶颈导致容错困难从80年代以来,处理器性能的年增长速度曾一度超过50%,而存储器性能的年增长速度平均只有7%[2叫如图1.6所示。这使得处理器和存储器之间的速度差距越来越大，导致了“存储墙”问题的出现128,2叫而随着多核处理器以及各种加速部件的出现,“存储墙”问题不但没有缓解反而变得更加严重,这ー问题对于具有超高并行计算能力的异构并行系统来说同样存在MT”1980 1985 1990 1995 2000 2005 2010Ywr1980 1985 1990 1995 2000 2005 2010Ywr图1.6处理器和存储器的性能增长速度ゆ】同时,异构并行系统还存在通信瓶颈的问题。在进行大规模科学计算时,由于PCI-E总线的带宽速度所限，当CPU与GPU进行通信时如果有大量的数据信息时，就会严重影响异构并行系统的性能。另ー方面，当容错技术应用于异构并行系统时，由于冗余机制同样需要保存大量的状态数据,那么在GPU超越CPU计算能力几十倍的同时,如果没有一个比现在带宽快几十倍的总线支持的话,其所获得的容错性能也会大打折扣,甚至使得一些容错技术根本无法应用于异构并行系统。容错技术的受限对系统的可靠性也会产生巨大的影响。以上这些都是有可能降低异构并行系统可靠性的因素，且随着异构并行计算机规模的不断扩大,其可靠性问题也会更加的严峻。由此可见,异构并行计算机在具有更为复杂的体系结构和超高的并行计算性能的同时也为其可靠性带来了诸多问题以及前所未有的挑战。本文专门就异构并行计算机的可靠性问题,对面向异构并行计算机的容错技术展开研究，对于异构系统上不同的故障类型及不同容错技术基于异构系统特性的合理应用及优化方法进行讨论和分析。虽然异构并行系统的可靠性问题更为复杂,也面临许多新的问题，但由于异构并行系统的特有的性质,也带了很多新的思路和研究空间，使得对于异构并行系统的容错技术研究更有意义。容错研究基础容错基本概念容错是系统的ー种能力——在发生故障时仍能完成预定的功能。1967年,Avizienis在文献［33］中第一次提出了容错的概念:“如果在发生逻辑故障的情况下,系统中的程序仍然能够正确地执行,那么我们就称这个系统是可容错的。”通常有三个描述故障的术语:故障（Fault）＞错误（Error）和失效（Failure）〇这三个概念因コ川的关系如图1.7所示。物理级 计算级 系统级图1.7故障、错误与失效三者的关系故障是系统的硬件中发生的物理缺陷、设计制造的不完善或软件中隐含的错误。错误是系统中的某一部分由于故障而产生了非正常的行为或状态的现象。失效是系统在运行到ー定的时间,或在一定的条件下偏离它预期设计的要求或规定的功能。故障、错误与失效构成一个因果链,即故障引起错误,错误又引起失效。故障会造成错误,但并不总是故障ー出现就立即会产生错误,从故障发生至由于该故障而产生错误的时间间隔称为故障潜伏期(faultlatency);同样,错误会造成失效,但并不总是错误ー发生就会造成失效。从错误发生至由于该错误而造成失效的时间间隔称为错误潜伏期(errorlatency)。从故障发生至造成失效的时间间隔称为失效潜伏期(failurelatency),是故障潜伏期和错误潜伏期之和。故障的来源很多,可能是设计、生产、装配过程中的缺陷,也可能是使用过程中外部因素的影响。事先检测出所有设计和生产过程中的故障是极其困难的,有些故障只在特定条件下オ会引起错误。例如,1994年,人们发现IntelPentiumI微处理器在计算特定浮点除法时得到不正确的结果。比如5505(X)1除以294911得到18.66600093而不是18.66665197。问题的原因是除法算法用到了一张包含1066个值的表,其中的5个单元原本应该存放常数+2,但是实际上是空的,处理器把它们看作〇い叫电子器件在使用过程中可能会受到电カ问题和宇宙辐射的影响而发生故障，而这种故障几乎不可能完全消除。研究表明一个典型的计算机系统每个月要经历120次电カ问题后汽在海平面的高度上,如果想要完全防止所有粒子对电子器件的影响,至少需要6英尺厚的混凝土屋顶巨曳故障类型设计容错机制,首先需要确定故障的类型。按照故障的来源,可分为硬件故障和软件故障。这里我们不考虑系统边界外的故障,如操作员的过失导致的系统失效问题。按照故障的持久性，硬件故障分为瞬时故障、永久故障和间歇故障。瞬时故障只存在ー小段时间,一般来说,发生在某个逻辑单元上的瞬时故障在下一次该逻辑单元被写入时就会消失。瞬时故障在计算机系统的存储部件中是最主要的故障类型。据统计，存储系统中发生的的故障98%都是瞬时故障〔37】。瞬时故障的发生多是由于环境的影响,例如alpha粒子,宇宙射线的照射等等。永久故障来源于硬件的制造缺陷,例如短路、断路等。除非采取一定的修补措施,否则永久故障将一直存在。间歇故障类似于瞬时故障,不同的是,间歇故障会在某段时间内连续发生。间歇故障意味着硬件的老化，如果不加以修补就会转化成永久故障。与硬件不同,软件不会磨损,不会老化，因此软件故障仅来源于设计错误和实现错误。尽管现有的软件测试、验证和调试技术已经能够在很大的程度上提高软件的正确性，但仍然无法完全排除软件体系结构和具体实现中存在的缺陷。尽管可以通过升级对软件故障进行修复，但升级的同时也可能引入新的bugo因此,在计算机系统中,软件故障也是比较常见的故障类型。在高性能计算机系统上运行的科学计算程序相对于一般的应用程序来说具有一定的特殊性。科学计算程序一般代码规模不大,但计算量和数据量却是海量的,并且运行时间比较长,所以在高性能计算机系统中,我们将更多的注意力集中在针对硬件故障的容错技术上。故障模型按照故障在系统中的传播以及对系统的影响，一般可以将故障归结为两类模型,fail-stop模型和Byzantine模型13用。fail-stop模型网描述了一种比较乐观的情形,即故障发生后,除了发生故障的部件以外，系统中其他部分都不会受到该故障的影响〔轴。实际上,完全的fail-stop模型几乎是不存在的，因为故障总会在系统中传播一定的距离。例如，由于现代微处理器很少会在寄存器上添加类似ECC校验这样的保护措施，因此某个寄存器的故障所导致的数据错误一般都会沿着定义引用关系传播到其他寄存器中。再例如并行系统在运行某个程序时,如果某个结点由于电源、温度等原因停机,那么在操作系统或运行时环境检测到该故障并报错之前,其他结点可能由于与故障结点存在数据依赖关系而受到了故障的影响。fail-stop故障模型可描述并行计算中进程挂起或崩溃的情况い制。］,是并行计算领域最常用的故障模型。Byzantine模型［现描述了非常普遍的故障类型,即故障发生后,其结果会在系统传播一定的范围图"的。例如,在并行系统中,如果并行执行的多个进程中有某个进程由于硬件故障导致某些变量的值发生了错误，那么这些错误将有可能沿着通信操作传播到其他进程,造成其他进程上的计算错误,而这种错误往往会传播到程序的结果中,引起失效。Byzantine模型可以表示任意故障,但检测这类故障非常困难ゆラ％在异构并行机系统中,这两种类型的故障都较常见，因此本文的研究也是针对这两种故障类型的不同容错技术。相关研究工作本课题主要针对异构并行计算机的容错技术进行研究，为此,我们进行了大量的调研工作，下面针对并行应用的容错技术的研究工作进行总结。这些相关技术的研究和进展对本课题的工作具有很大的启发和指导意义。本节中我们概括了近年来计算机系统容错技术的现有研究成果和相关技术、方法和实践工作,并在最后对当前面向异构并行系统的现有的一些容错技术及研究成果进行总结和介绍。容错常用方法容错的基本途径是冗余。通过冗余来提高可靠性的思想最早是在20世纪50年代由JohnvonNeumann所提出来的网。冗余可分为两大类:空间冗余和时间冗余。空间冗余是指通过提供额外的资源如器件、函数或数据来实现容错。时间冗余则是指通过重复计算过程或数据传输过程来实现容错。根据额外添加的冗余资源的不同,空间冗余又分为硬件冗余(比如三模冗余,TMR)、软件冗余(比如多版本,Multi-version)和信息冗余(纠错码,如ErrorCorrectionCode,ECC)〇我们将并行计算领域的各种容错方法大致分为以下四类:1.基于算法的容错(Algorithm-basedfaulttolerance)2,并行复算(Parallelrecomputing).算法相关的容错(Algorithm-dependentfaulttolerance).回滚恢复(Rollback-recovey)基于算法的容错技术主要是面向数值运算应用特别是矩阵运算应用的容错技术。它的基本思想是对计算数据进行某种编码,在算法执行过程中检查这种编码是否仍然保留，从而判断是否发生了错误⑻々叫并行复算是由国防科学技术大学计算机学院杨学军教授等人提出的新的容错技术ワリ。并行复算的核心思想是:在发生故障时,将故障处理器上因故障而丢失的负载分配到剩余的无故障处理器上并行的重算,以加快故障恢复速度ル】。并行复算方法并不要求额外添加资源，只是利用了现有的冗余的硬件资源(如处理器和结点内存),因此我们认为它属于时间冗余的容错方法。并行复算特别适合计算密集型的应用。在这类应用中,每个进程分配到的计算量很大,采用并行复算的方法来恢复故障进程上的计算可以显著缩短容错的时间开销⑺フ叫尽管并行复算技术是一种很有潜力的容错技术，但与任何其它新技术ー样，并行复算也存在ー些还需进ー步研究解决的问题(比如在通信较多的应用中如何发挥并行复算的性能优势)。算法相关的容错方法是ー类特殊的容错方法,它是根据某些并行算法的特点开发的有针对性的容错方法,可以达到非常低的容错开销。美国圣地亚国家实验室最先开展了这类容错方法的研究174］。对于某些算法，例如异步并行直接搜索(AsynchronousParallelDirectSearch),ー小部分数据的丢失不会影响计算任务的正确执行。在这种情况下,不需要故障通知和故障恢复等步骤,算法可实现天然的容错け®］。还有些并行算法,尽管它们必须恢复故障时丢失的所有数据才能正确执行,但是可以根据算法的特点设计非常高效的容错方法向朋］。对于算法相关的容错方法,需要程序员对算法非常了解，并能充分利用算法某些特点精心设计出独特而高效的容错方案,因此,这种方法对程序员的要求很高,并且只能个例研究,难以推广。回滚恢复的基本思想是计算过程中周期性地保存计算状态,当故障发生后,

应用程序回滚到之前保存的某个状态处重新开始执行冈ホ"。回滚恢复方法要求重复执行从故障前的某个状态到故障发生处之间的计算过程,但是一般要求额外的存储空间保存恢复所需的计算状态数据,因此这种容错方法结合了时间冗余和空间冗余。图1.8列出了几种常用的容错方法。在分布式和并行计算领域,回滚恢复方法得到普遍关注和广泛应用。软件儿 Multi-version冗余硬件冗余TMR软件儿 Multi-version冗余ECCABFT<Parallelrecomputing

时间冗余・Rollback-recovery图1.8容错方法分类Rollback-recovery容错技术分析Rollback-recovery最开始起源于分布式系统领域,它假设故障是fail-stop类型。在分布式系统领域,容错的目标是关键系统（如web服务器和空中交通管制系统）的零停工期（zerodowntime）[871〇而本文所关注的高性能计算领域中容错的目标则是在一定故障概率下使程序执行完成的期望时间最短18用。另外,与高性能计算机上的大规模科学计算程序相比，分布式系统上的程序在执行期间通信的频率和传递的数据量要小得多。因此，有些在分布式系统领域表现良好的容错技术并不适合高性能计算领域,有些则需要改进才能应用到高性能计算领域。本节通过对Rollback-recovery技术的分析来揭示本文我们选择应用级checkpointing技术作为研究对象的原因，同时也为后续的新的相关容错技术的研究的展开打下基础。Rollback-recovery将系统（分布式系统或高性能计算系统）看作一组应用进程的集合。这些进程可以通过网络相互通信，并且能够访问ー个称之为稳定存储器（stablestorage）的存储设备网。每个进程的执行被看作一组状态间隔（stateintervals）序列,每个状态间隔从一个非确定性事件（如用户输入或消息到达）开始，直到下ー个非确定性事件。各进程在无故障运行期间周期性地将恢复计算所需的信息（即checkpoint,也叫计算状态）保存到稳定存储器;发生故障后,利用checkpoint恢复到保存该checkpoint时的计算状态。通过这种方式,Rollback-recovery技术减小了故障造成的损失。关于Rollback-recovery正确性的一般条件是“如果系统的内部状态与故障前的可观察行为是一致的,则系统可正确恢复"1901〇整个应用的计算状态是各进程的checkpoint的集合。由于各进程之间可能发生消息传递,因此,Rollback-recovery协议要维护进程内部交互的信息以及应用与外部交互的信息。Rollback-recovery技术可分为两大类:checkpoint-based（也称checkpointing）和log-based（也称message-logging）〇本文所研究的面向异构并行系统的容错技术都涉及到了Rollback-recovery容错机制,在后文的阐述中会对如何使用这一机制作进ー步的描述和讨论。TMR容错技术分析三模冗余（TripleModularRedundancy,TMR）出“是N模冗余的特例（^=3）,TMR常作为其他冗余技术的基础，是在实际应用中最为广泛使用的冗余技术。个基本的TMR系统的结构如图1.9所示。三个相同的模块接收同一个输入，产生的三个结果送至多数投票器投票表决。投票器的输出取决于它的三个输入中的多数一方的结果。若有一个模块出现故障,则另外两个正常模块的输出可将故障模块的错误输出掩盖,因而不会在投票器输出端产生差错。可以看出,三模冗余结构使系统可以正常工作的条件是:或三模都正常，或三模中任意二模正常。模块I图1.9基本TMR系统结构三模冗余中,具备几种关键机制:比较、投票、赋值与标记（mask）机制。其中比较机制就是通过对通信时三个副本各自的结果进行比对,从而达到对故障进行检测的目的;投票机制就是在有副本出现不同结果时对三个副本的结果进行表决投票,选取出两个相同的，将其视为正确结果，并赋值给出现不同结果的副本,可见投票和赋值是一起使用的。当然,如果在投票失败,即三个副本结果各不相同时,系统不予赋值,而是视作全部出现故障而直接重启计算。最后的标记机制就是在投票结束后对出现不同的副本不予赋值，而是标记出来，以剩下的两

个副本继续进行计算。综上所述,三模冗余是ー种故障屏蔽技术(FaultMaskingTechnology)1371,它可以防止系统中的故障在该系统的信息结构中产生差错,利用冗余资源将故障影响掩盖起来,或隔离或校正,从而达到容错目的。本文所研究的容错技术就涉及到了三模冗余机制,因此我们对三模冗余机制在异构并行系统上的应用展开了深入的研究。Checkpointing容错技术分析Checkpointing是一种广泛应用于大规模科学计算领域中的容错技术。该技术是在程序执行期间将计算状态周期性的保存到可靠存储器上四“00】。如果某个进程失效，所有进程都必须回滚到最近一个checkpoint处继续计算。Checkpointing分为两种基本的方法:系统级checkpointing(system-levelcheckpointing,SLC)和应用级checkpointing(application-levelcheckpointing,ALC)〇Memory系统级ApplicaiijtajjjI?FGcef：fiorRegisters0班耶観》@日解観!も血!Memory《も应用级ApplicaiijtajjjI?FGcef：fiorRegisters0班耶観》@日解観!も血!Memory《も应用级Disk图1.10Checkpointing技术系统级checkpointing将应用状态在存储器上进行映像(core-dump-stylesnapshots),即将所有进程的地址空间内容(堆、栈和全局变量)、寄存器信息和通信库状态存储到稳定存储介质上这种方法对应用是完全透明的,如图1.10(a)所示。但是,在大规模并行系统中，应用状态可能占用大量的存储空间,因此所有进程同时读写checkpoints的I/O数据量很大,从而使!/O成为大规模并行系统軍checkpointing技术的性能瓶颈肉。关多数应用甲,整个计算状态可以通过T关键数据结构进行恢复。应用级checkpointing通过减小需要保存的数据量来改善性能〔皿』。3】,该技术允许用户指定checkpointing的时机并选择尽可能少的信息进行保存"0叫应用级checkpointing的基本思想是通过修改应用代码,保存问题的关键状态而非整个系统状态,如图1.10(b)所示。目前对于许多大规模平台上的应用,例如IBMBlueGene和ASCI,手工实现的应用级checkpointing是默认的容错方法。然而,应用级checkpointing仍然要求无故障进程在恢复时回滚,重算上一个checkpoint到故障时刻之间的任务，这造成了计算时间的浪费。综上所述，checkpointing技术是目前大规模并行计算领域广泛接受的容错技术,系统级checkpointing虽然对用户透明,但时空开销均比较大。应用级checkpointing虽然速一定程度上减小了应用状态的保存量,但仍需要全系统(包括无故障进程)回滚,浪费了计算资源。本文就将checkpointing技术作为研究重点,并着重对于应用级checkpointing技术在异构并行计算机上的实现进行了深入研究。在这里我们对文中所用的checkpointing技术的相关术语进行说明:Checkpointing技术:中文中译为检查点技术,文中统ー用“checkpointing技术”作为这ー技术的专用名词来进行相关描述。Checkpoint!这个名词形式术语的基本含义是恢复程序执行所需的计算状态数据。本文中常用于修饰其它名词，如checkpoint位置、checkpoint指令等。Checkpoint数据:含义与checkpoint相同,只是为了强调所指的是数据。Checkpoint时机：从程序动态执行的角度看到的保存checkpoint数据的时间位置。Checkpoint位置：从程序静态代码的角度看到的checkpoint指令或checkpoint调用插入的空间位置。Checkpoint/Restart技术：与checkpointing技术概念相同,之所以加入restart有强调回滚恢复机制的意思,是对带有回滚机制的checkpointing技术的完整表述。文中对这两个术语酌情使用。优化checkpoint的相关研究针对checkpointing技术的改进工作主要集中于减小checkpointing技术的状态保存开销。文献［106-108］提出了disklesscheckpointing技术,它用高速的内存代替低速的磁盘来存放checkpoint文件，并对各计算结点内存中的checkpoint进行编码运算,并将编码结果保存到checkpointingprocessors〇在大规模科学计算中，这种方法对内存容量的要求比较高。Disklesscheckpointing技术中利用ー个冗余结点的资源，将各个结点的关键状态保存到冗余结点上,在出现ー个结点失效的情况下，应用通过冗余结点恢复失效结点的数据,这种方法可以容忍ー个结点失效的情况,但是仍需保存系统状态到冗余结点,这使得它的规模难以扩展。减少每个checkpoint的大小是提高应用级checkpointing性能的关键。根据程序行为进行优化分析（如排除特定的变量或数据结构）和不需要程序行为的优化方法（如压缩checkpoint大小）是两类优化checkpoint大小的基本方法。应用级checkpointing的自动化采用根据程序行为进行分析的方法优化checkpoint大小。CATCH“091首次使用编译技术辅助优化checkpointing〇CATCH使用profiling技术确定程序中不同点处的checkpoint的可能大小,然后使用学习算法在保证两次checkpoint间隔的前提下帮助用户选择在checkpoint大小最小的位置进行checkpointing〇び系统中,Daniel等基于自己实现的堆管理机制对C/MPI中动态分配的堆区域进行优化⑴叫Plank等人通过数据流分析,找出存储器中的“dead”数据和"read-only”数据，并在checkpoint中删除这些数据""LYang等人将传统编译技术中的定值一引用分析扩展到了MPI并行程序,并基于该技术分析各个进程上checkpoint位置处的活跃变量并保存到checkpoint中”⑵⑶。另外，对于某些特定的并行算法,存在其它有效的容错方法。对于某些算法,ー小部分数据的丢失不会影响计算任务的正确执行。在这种情况下,不需要故障通知和故障恢复等步骤,算法可实现自然容错。根据并行迭代和矩阵乘算法的特点,Bosilca和Chen分别提出了checkpoint-free的容错机制""」⑶。将checkpoint文件的加载和故障恢复计算进行重叠”⑹由］是加速故障恢复的另一手段。Tanenbaum等人利用虚存页式管理机制记录checkpoint中故障恢复计算真正需要的内存页”的,在故障恢复时，只要这些页被加载，就可以开始进行故障恢复计算。Li和Lan提出的FREM机制1”刀在每次checkpoint之后的一段时间内（称为trackingwindow）对进程的存储访问进行跟踪，将这段时间内被访问的存储位置记录在ー个数据结构中。在故障恢复的时候，优先从checkpoint文件中读取由该数据结构指向的存储位置,然后立即开始故障恢复计算。Checkpoint文件剩余部分的加载将与故障恢复计算重叠进行。异构并行计算机现有容错方法当前针对异构系统的容错问题所采用的大都是硬件冗余和软件冗余技术。JeremyW.Sheaffer和NVIDIA研究小组的DavidP.Luebke等人在2007年设计了ー种面向超级计算领域的GPGPU可靠性的硬件冗余和恢复机制［”旬,NishantGeorge等人也在2008年DSN会议上提出了基于硬件双模冗余和同步数据流技术的异构系统的容错方案“351,但是这些通过增加冗余硬件的容错方法都并不适用于现在被广泛使用的普通GPU。在硬件冗余技术提出的同时,基于软件容错的机制也被越来越多的研究者所关注MartinDimitrov等人提出了一种冗余执行kernel的方式来对GPU上发生的瞬时故障进行故障检测い旬。AnthonyE.Gregerson等人分析了时间冗余、空间