StudyandImplementationofFault

ToleranceforHeterogeneousParallel

ComputerCandidate：JiaJiaSupervisor：Prof.YangXuejunAdissertationSubmittedinpartialfulHllmentoftherequirements

forthedegreeofDoctorofEngineering

inComputerScienceandTechnology

GraduateSchoolofNationalUniversityofDefenseTechnology

Changsha,Hunan,P.R.ChinaSeptember,2011獨創(chuàng)性聲明本人聲明所呈交的學(xué)位論文是我本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。盡我所知,除了文中特別加以標(biāo)注和致謝的地方外,論文中不包含其他人已經(jīng)發(fā)表和撰寫過的研究成果，也不包含為獲得國防科學(xué)技術(shù)大學(xué)或其它教育機構(gòu)的學(xué)位或證書而使用過的材料。與我ー同工作的同志對本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說明并表示謝意。學(xué)位論文題目:異構(gòu)并行計算機容錯技術(shù)研究 學(xué)位論文作者簽名:日期: 年月日學(xué)位論文版權(quán)使用授權(quán)書本人完全了解國防科學(xué)技術(shù)大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定。本人授權(quán)國防科學(xué)技術(shù)大學(xué)可以保留并向國家有關(guān)部門或機構(gòu)送交論文的復(fù)印件和電子文檔，允許論文被查閱和借閱;可以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存、匯編學(xué)位論文。（保密學(xué)位論文在解密后適用本授權(quán)書。）學(xué)位論文題目:異構(gòu)并行計算機

容錯技術(shù)研究學(xué)位論文作者簽名：日期：年月日作者指導(dǎo)教師簽名： 日期: 年月日目錄TOC\o"1-5"\h\z\o"CurrentDocument"摘要 i\o"CurrentDocument"Abstract iii\o"CurrentDocument"第一章緒論 1\o"CurrentDocument"課題背景 1異構(gòu)并行計算機的興起 1大規(guī)模并行系統(tǒng)的可靠性問題 4大規(guī)模異構(gòu)并行計算機面臨的可靠性挑戰(zhàn) 6\o"CurrentDocument"容錯研究基礎(chǔ) 9容錯基本概念 9故障類型 10故障模型 11\o"CurrentDocument"相關(guān)研究工作 11容錯常用方法 11Rollback-recovery容錯技術(shù)分析 13TMR容錯技術(shù)分析 14Checkpointing容錯技術(shù)分析 15優(yōu)化checkpoint的相關(guān)研究 16異構(gòu)并行計算機現(xiàn)有容錯方法 17\o"CurrentDocument"本文主要研究內(nèi)容 18\o"CurrentDocument"本文主要工作和創(chuàng)新 20\o"CurrentDocument"論文結(jié)構(gòu) 21\o"CurrentDocument"第二章計算可接受模型 23\o"CurrentDocument"面向一般計算系統(tǒng)的計算可接受模型 23\o"CurrentDocument"面向異構(gòu)并行計算系統(tǒng)的計算可接受模型 25\o"CurrentDocument"容錯機制對異構(gòu)系統(tǒng)可接受度的影響 27帶TMR異構(gòu)系統(tǒng)可接受模型分析 27帶C/R異構(gòu)系統(tǒng)可接受模型分析 30\o"CurrentDocument"本章小結(jié) 33第三章 基于異構(gòu)系統(tǒng)故障傳播行為分析的應(yīng)用級checkpoint的數(shù)據(jù)量優(yōu)化方法 35TOC\o"1-5"\h\z\o"CurrentDocument"問題背景 35CG調(diào)用 35CG調(diào)用流圖 37異構(gòu)系統(tǒng)故障傳播與CG調(diào)用流圖 39\o"CurrentDocument"異構(gòu)系統(tǒng)故障傳播行為 40CG間故障傳播 41G點內(nèi)故障傳播 42\o"CurrentDocument"異構(gòu)系統(tǒng)的應(yīng)用級checkpoint數(shù)據(jù)優(yōu)化方法 45基于故障傳播行為的checkpoint數(shù)據(jù)分析 45Checkpoint的位置選擇 47\o"CurrentDocument"實驗評估 49實驗方法 49實驗結(jié)果 50\o"CurrentDocument"本章小結(jié) 54\o"CurrentDocument"第四章 異構(gòu)系統(tǒng)應(yīng)用級checkpoint的優(yōu)化設(shè)置研究 55\o"CurrentDocument"問題背景 55異構(gòu)系統(tǒng)程序特征分析 55問題提出 57\o"CurrentDocument"全局checkpoint數(shù)據(jù)保存開銷最小化問題 58場景一:基于同步機制的checkpoint優(yōu)化設(shè)置 58場景二:基于異步機制的checkpoint優(yōu)化設(shè)置 65Checkpoint數(shù)據(jù)保存偏移量設(shè)置優(yōu)化問題 71\o"CurrentDocument"實驗評估 73實驗方法 73實驗結(jié)果 74\o"CurrentDocument"本章小結(jié) 76\o"CurrentDocument"第五章 面向GPU的多副本容錯技術(shù) 79\o"CurrentDocument"基于冗余線程的GPU多副本容錯技術(shù)的基本思想 79問題背景 79解決方案 80\o"CurrentDocument"RB-TMR的設(shè)計和實現(xiàn)方法 82創(chuàng)建冗余代理 83基于RB-TMR機制的GPUKernel的設(shè)計 84比較與投票 87第II貝TOC\o"1-5"\h\z\o"CurrentDocument"RB-TMR編譯工具的設(shè)計與實現(xiàn) 90RB-TMR的編譯實現(xiàn)框架 90前端分析器 91數(shù)據(jù)流分析器 91代碼重寫器 93\o"CurrentDocument"性能評估 94實驗方法 94實驗結(jié)果 95\o"CurrentDocument"本章小結(jié) 99\o"CurrentDocument"第六章 結(jié)論與展望 101\o"CurrentDocument"工作總結(jié) 101\o"CurrentDocument"研究展望 102\o"CurrentDocument"致謝 103\o"CurrentDocument"參考文獻(xiàn) 105\o"CurrentDocument"作者在學(xué)期間取得的學(xué)術(shù)成果 117\o"CurrentDocument"作者在學(xué)期間參加的科研項目 119表目沃TOC\o"1-5"\h\z表3.1Checkpointing的時間開銷 51表3.2Checkpoint數(shù)據(jù)存儲空間開銷 52表4.1Checkpoint數(shù)量 74表4.2Checkpoint數(shù)據(jù)保存時間開銷 74表5.1無故障情況下帶有三種容錯機制的程序執(zhí)行時間 96攵、、攵、、冬冬冬^圖圖圖義、冬冬圖圖圖冬冬圖目錄TOC\o"1-5"\h\z圖1.1TOP500中機器的處理器數(shù)目統(tǒng)計圖 2圖1.2高性能計算機的性能發(fā)展趨勢 2圖1.3Intel處理器電源電壓的變化趨勢 4圖1.4Top500前20臺超級計算機系統(tǒng)的平均處理器核心數(shù)量 5圖1.5不同規(guī)模下系統(tǒng)的MTBF變化趨勢 6圖1.6處理器和存儲器的性能增長速度四 8圖1.7故障、錯誤與失效三者的關(guān)系 9圖1.8 容錯方法分類 13圖1.9 基本TMR系統(tǒng)結(jié)構(gòu) 14圖1.10 Checkpointing技術(shù) 15圖2.1計算可接受模型的概念體系 23圖2.2多次執(zhí)行下程序運行結(jié)果的可接受 24圖2.3異構(gòu)并行系統(tǒng)上的程序執(zhí)行 26TMR容錯示意圖 28GPUTMRDA-DA,的變化曲線 29帶TMR系統(tǒng)單次執(zhí)行與該系統(tǒng)多次執(zhí)行可接受比較 30C/R容錯示意圖 31帶C/R系統(tǒng)單次執(zhí)行與該系統(tǒng)多次執(zhí)行可接受比較 33同構(gòu)與異構(gòu)系統(tǒng)算法執(zhí)行流程 36CUDA上的矩陣乘算法 36SWIM異構(gòu)系統(tǒng)CG調(diào)用流圖 38CG間的數(shù)據(jù)傳播 39G點內(nèi)故障傳遞 43G點內(nèi)故障影響集求解算法 45CUDA上的Checkpointing流程 46一般算法的基本思想 48選擇合適的checkpoint位置的一般算法 48無CPU-GPU傳輸狀態(tài)checkpointing的執(zhí)行時間增加比 513.11時間開銷減少百分比 52圖3.12有CPU-GPU傳輸狀態(tài)checkpointing的優(yōu)化收益 53圖4.1異構(gòu)系統(tǒng)體系結(jié)構(gòu) 561^14.2異相系統(tǒng)矩?陣乘算法流程 戻圖4.3 同步執(zhí)行checkpointing的流程 59圖4.4同步設(shè)置CPU-GPU端checkpoint 60圖4.5 C_Struct的數(shù)據(jù)結(jié)構(gòu) 61圖4.6同步機制Checkpoint間隔與程序的期望執(zhí)行時間“5。1 62圖4.7模型(4.3)的求解算法 64圖4.8異步執(zhí)行checkpointing的流程 65圖4.9異步設(shè)置CPU-GPU端checkpoint 66圖4.10異步機制checkpoint間隔與程序的期望執(zhí)行時間 69圖4.11模型(4.12)的求解算法 71圖4.12偏移量ん中的checkpoint位置選取 72佟14,13一次同步與異步checkpointing時間開銷 75圖4.14同步與異步設(shè)置下全局checkpointing時間開銷 75圖5.1兩種容錯方法 81圖5.2ー個異構(gòu)程序及對應(yīng)的RB-TMR容錯版本 82圖5.3ー個Kernel的線程組織方式 83圖5.4單GPU時的冗余代理線程組織方式 83圖5.5多GPU時的冗余代理線程組織方式 84圖5.6重設(shè)計的Kernel代碼 85圖5.7ー個異構(gòu)程序示例 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程序?qū)Ρ萩heckpointing程序的平均回滾次數(shù) 96圖5.16RB-TMR程序?qū)Ρ萩heckpointing程序的執(zhí)行時間 97圖5.17RB-TMR程序?qū)Ρ萒MR程序的執(zhí)行時間 97圖5.18RB-TMR對比checkpointing的容錯開銷 98圖5.19RB-TMR對比TMR的容錯開銷 98摘要并行計算是實現(xiàn)超高性能計算的主要技術(shù)手段。當(dāng)前,隨著GPGPU性能的不斷提高,利用CPU和GPU構(gòu)建的異構(gòu)并行系統(tǒng)已經(jīng)成為高性能計算機領(lǐng)域的研究熱點。然而隨著并行計算系統(tǒng)規(guī)模的不斷增長,高性能計算機面臨嚴(yán)峻的挑戰(zhàn)。由于異構(gòu)并行系統(tǒng)更為復(fù)雜的體系結(jié)構(gòu)以及其特有的性質(zhì),且商用GPGPU容錯能カ較弱,所以由CPU和GPU構(gòu)建的大規(guī)模異構(gòu)并行系統(tǒng)的可靠性問題更為尖銳,尚缺乏實用的容錯手段。本文針對異構(gòu)并行計算機的容錯技術(shù)展開研究,以異構(gòu)并行系統(tǒng)硬件故障在軟件中的傳播行為為理論基礎(chǔ),對應(yīng)用級checkpointing技術(shù)的保存數(shù)據(jù)量優(yōu)化問題進(jìn)行研究;分析了異構(gòu)并行系統(tǒng)多checkpoint的全局開銷最優(yōu)化問題，并提出了設(shè)置方案;同時,針對異構(gòu)并行系統(tǒng)提出了一種新的面向GPU的多副本容錯技術(shù)RB-TMR,并對其所具備的關(guān)鍵機制進(jìn)行了詳細(xì)的研究與設(shè)計實現(xiàn)。本文的主要貢獻(xiàn)如下:1、提出了一種面向一般計算系統(tǒng)的計算可接受模型。建立程序的執(zhí)行結(jié)果可接受以及可接受度的定義,并進(jìn)ー步定義程序多次執(zhí)行的可接受和多次執(zhí)行的可接受度，以此為基礎(chǔ)得到可接受度的相關(guān)定理和推論。針對異構(gòu)并行系統(tǒng)將可接受度的相關(guān)定理和推論進(jìn)行了擴展,并建立異構(gòu)并行系統(tǒng)的可接受模型，同時進(jìn)ー步案例分析兩種常見的容錯技術(shù)checkpoint/restart和TMR應(yīng)用到異構(gòu)并行系統(tǒng)上時,對可接受模型的影響，從而給出容錯機制的指導(dǎo)意見和優(yōu)化方法。2、基于過程間相關(guān)性理論，提出了由CPU和GPU構(gòu)成的異構(gòu)并行系統(tǒng)中硬件故障在軟件中傳播行為描述方法,我們稱其為故障傳播模型。同時,根據(jù)故障傳播模型,設(shè)計了針對該系統(tǒng)的checkpointing機制,并針對影響checkpoint/restart開銷的主要問題之 checkpoint保存數(shù)據(jù)量進(jìn)行了優(yōu)化。實驗證明該優(yōu)化方法可以有效的減小開銷，提高容錯性能。3、深入研究了面向異構(gòu)并行系統(tǒng)的多個checkpoint的全局開銷最小化問題,提出了面向異構(gòu)并行系統(tǒng)的同步及異步兩種機制的多checkpoint全局開銷最小化的優(yōu)化設(shè)置方法。首先提出了兩個針對優(yōu)化設(shè)置多個checkpoint位置的基本問題。然后通過對異構(gòu)并行系統(tǒng)體系結(jié)構(gòu)和程序特性的分析,提出了基于兩種機制的異構(gòu)并行系統(tǒng)的多checkpoint設(shè)置方法;同步及異步機制的checkpoint設(shè)置方法。同時,根據(jù)checkpoint優(yōu)化設(shè)置的兩個具體問題分別對這兩種機制進(jìn)行優(yōu)化設(shè)置分析和數(shù)學(xué)建模，并給出了相應(yīng)的求解算法。4、提出了一種回滾機制與TMR技術(shù)相結(jié)合的容錯技術(shù)RB-TMR。這ー技術(shù)可以有效應(yīng)對fail-stop故障與瞬時故障兩種類型的故障進(jìn)行容錯,我們給出了這一技術(shù)的實現(xiàn)方法,并針對異構(gòu)并行系統(tǒng)體系結(jié)構(gòu)及程序模型的特征對其中關(guān)鍵機制的設(shè)計進(jìn)行了具體分析和討論。同時,設(shè)計并實現(xiàn)了一個面向RB-TMR機制的源到源編譯輔助工具,可以輔助用戶面向CUDA程序完成RB-TMR機制的實現(xiàn),減輕了用戶實現(xiàn)RB-TMR機制的負(fù)擔(dān)。實驗結(jié)果表明RB-TMR技術(shù)能夠?qū)崿F(xiàn)較高的錯誤檢出和糾正率,有效減小可能需要回滾恢復(fù)的概率,根據(jù)綜合評定,其相對于傳統(tǒng)checkpointing及TMR技術(shù)有更好的容錯性能。關(guān)鍵詞:高性能計算;異構(gòu)并行計算機;容錯;可接受;應(yīng)用級checkpointing；過程間相關(guān)性;故障傳播行為第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國防科學(xué)技術(shù)大學(xué)研究生院博士學(xué)位論文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第一章緒論課題背景大規(guī)模科學(xué)計算一直是推動高性能計算機迅速發(fā)展的主要動カ。今天的科學(xué)家更加依賴于高性能計算機來處理空前龐大的數(shù)據(jù)集以及實現(xiàn)空前復(fù)雜的模擬仿真。當(dāng)前,隨著GPGPU(GeneralPurposecomputationonGraphicProcessingUnits)“性能的不斷提高,利用CPU和GPU(GraphicsProcessingUnits)構(gòu)建的異構(gòu)系統(tǒng)已經(jīng)成為高性能計算機⑵す領(lǐng)域的研究熱點,我國首臺千萬億次計算機天河(Tianhe-1A)⑷就是一個典型案例。另ー方面,隨著并行計算系統(tǒng)規(guī)模的不斷增長，系統(tǒng)可靠性越來越低，已成為并行計算向大規(guī)模擴展的ー個不容忽視的制約因素。由于商用GPGPU容錯能力較弱,所以由CPU和GPU構(gòu)建的大規(guī)模異構(gòu)并行系統(tǒng)的可靠性問題更為尖銳，尚缺乏實用的容錯手段。因此,對于面向異構(gòu)并行計算機的容錯技術(shù)研究也變得尤為重要。異構(gòu)并行計算機的興起隨著計算機技術(shù)的高速發(fā)展,高性能計算機已成為基礎(chǔ)科學(xué)領(lǐng)域研究中必不可少的工具。當(dāng)前,高性能計算可用于解決國防建設(shè)和經(jīng)濟發(fā)展中重大應(yīng)用問題的基礎(chǔ)性、前瞻性與戰(zhàn)略性關(guān)鍵技術(shù),廣泛應(yīng)用于核武器研究、生物信息技術(shù)、醫(yī)療和新藥研究、計算化學(xué)、GIS、CAE、氣象預(yù)報、エ業(yè)設(shè)計以及環(huán)境保護(hù)等與國家安全和國民經(jīng)濟密切相關(guān)的各個領(lǐng)域。隨著競爭的加劇和應(yīng)用的普及，高性能計算技術(shù)已從少數(shù)軍工部門和國家實驗室普遍進(jìn)入到各大公司、企業(yè)和院校。科學(xué)研究、工業(yè)制造和商業(yè)活動中越來越多地使用高性能計算機來解決實際問題。日本政府于2007年啟動了一項超長期天氣預(yù)報計劃。借助于日本海洋科學(xué)技術(shù)中心橫浜研究所的“地球模擬器(EarthSimulator)w?對未來30年內(nèi)可能發(fā)生的臺風(fēng)、暴風(fēng)雪、干旱以及其它惡劣天氣進(jìn)行預(yù)測。計算結(jié)果可以幫助政府提前采取應(yīng)對災(zāi)害天氣的相應(yīng)措施，減小經(jīng)濟損失。美國GM、GE、日本Nissan等著名大公司擁有總計算能力超過10萬億次的高性能計算機用于新產(chǎn)品的研發(fā)。Google公司一直在努力爭取使用戶的請求可以在0.5秒內(nèi)處理完成［叫為了實現(xiàn)這一目標(biāo)，Google公司開發(fā)了一個大規(guī)模的集群系統(tǒng)Googleclustero在2003年初,Googlecluster就擁有了超過30,000個處理器,并且仍在不斷擴展規(guī)模以提高性能此ユ近年來,隨著高性能計算技術(shù)的普遍應(yīng)用,高性能計算機的發(fā)展呈現(xiàn)出兩大

趨勢:ー是廣泛使用通用的、低成本的商用器件(Commericaloff-the-shelf,COTS),以縮短研制周期和降低研制成本;二是系統(tǒng)規(guī)模持續(xù)增長,以滿足科研和生產(chǎn)活動對更高計算能力的不斷追求。圖1.!顯示了近6年來Top500⑷中機器的處理器數(shù)目統(tǒng)計情況,由此可見高性能計算機包含的處理器數(shù)在不斷增加。但同時,低可靠的COTS器件的廣泛使用降低了高性能計算機各結(jié)點的可靠性，也降低了系統(tǒng)的整體可靠性;而系統(tǒng)規(guī)模的大幅增長則會顯著降低系統(tǒng)的平均故障間隔時間(MeanTimeBetweenFailures,MTBF)〇圖!.1TOP500中機器的處理器數(shù)目統(tǒng)計圖圖1.2高性能計算機的性能發(fā)展趨勢為「滿足高性能計算領(lǐng)域日益攀升的計算需求,高性能計算機系統(tǒng)的規(guī)模不斷增大,峰值計算速度不斷提高。超級計算機的峰值計算速度基本遵循一千倍”定律，即每十年系統(tǒng)性能提升1000倍。目前超級計算機已經(jīng)突破千萬億次大關(guān),正在向百萬萬億次系統(tǒng)邁進(jìn)。圖1.2給出了Top500⑷中的高性能計算機從1993年一直到2011年的性能發(fā)展情況以及未來的趨勢。可以看到,無論排名第一還是最后一名,其發(fā)展情況都是ー樣的,其中當(dāng)前排名第一的日本計算機ー“京”的峰值性能已經(jīng)達(dá)到了8.162Pflop/s,而到2019年,這ー數(shù)值將達(dá)到1Eflop/s,是當(dāng)前最快計算機的1000倍。就目前看來這是極為驚人的數(shù)字,但是按照以往的發(fā)展趨勢來看,這ー預(yù)測毫不為過。由于高性能計算領(lǐng)域中處理器制程、架構(gòu)技術(shù)、多核技術(shù)、節(jié)能技術(shù)、軟件優(yōu)化技術(shù)的高速發(fā)展,以及各大廠商對于高新產(chǎn)品不遺余力的快速部署與應(yīng)用，使得現(xiàn)今的高性能計算正在以更快的速度發(fā)展。近10年以來,微處理器已經(jīng)逐漸從依靠提高處理器頻率轉(zhuǎn)向增加處理器并行度的方式來獲得持續(xù)的性能提升。自2000年以來,處理器頻率發(fā)展十分緩慢,取而代之的是處理器核數(shù)量的增加，以此維持微處理器繼續(xù)沿摩爾定律發(fā)展。因此，以CELL網(wǎng)、Clearspeed⑼和GPU1'01為代表的眾核體系結(jié)構(gòu)應(yīng)運而生。與多核微處理器相比,眾核體系結(jié)構(gòu)將更多的晶體管應(yīng)用于計算單元,有效提高了芯片的性能功耗比;與此同時,眾核體系結(jié)構(gòu)具有相對簡單的控制邏輯，因此通常作為通用微處理器的加速部件,以提高典型科學(xué)計算應(yīng)用的計算速度。近年來，在各種新的架構(gòu)及加速部件飛速興起和發(fā)展的同時,GPU也得到了高速的發(fā)展。由于GPU適合于并行數(shù)值計算的特性,使得高性能計算領(lǐng)域?qū)ζ洎`直看好,而在此基礎(chǔ)上發(fā)展起來的GPGPU更是由于強大的并行處理能力和可編程流水線,使得其在面對單指令流多數(shù)據(jù)流（SIMD）且數(shù)據(jù)處理的運算量要遠(yuǎn)大于數(shù)據(jù)調(diào)度和傳輸?shù)男枨髸r,能夠取得遠(yuǎn)超傳統(tǒng)CPU的性能。由此而發(fā)展起來的由CPU和GPU構(gòu)建的異構(gòu)并行計算機也受到越來越多研究者的關(guān)注。事實上,利用GPU的計算能力進(jìn)行高性能計算的異構(gòu)并行計算機已經(jīng)受到絕大多數(shù)科學(xué)領(lǐng)域的研究人員的青睞,包括大氣模型,高能量物理,宇宙學(xué),量子化學(xué),分子動力學(xué),甚至藥物設(shè)計⑴】。當(dāng)前,隨著異構(gòu)并行處理思想的逐漸成熟以及異構(gòu)并行體系結(jié)構(gòu)技術(shù)的發(fā)展,國際上越來越多的異構(gòu)并行系統(tǒng)涌現(xiàn)出來。HP、IBM、Cray等各大廠商都紛紛推出了自己的異構(gòu)并行計算機,我國的異構(gòu)并行計算機也在這次高性能計算機系統(tǒng)發(fā)展的研究熱潮中脫穎而出。由國防科學(xué)技術(shù)大學(xué)研制的天河一號高性能計算機系統(tǒng)榮登2010年11月Top500排名之首,實現(xiàn)了我國千萬億次高性能計算機零的突破;此外，由曙光公司研制的星云系統(tǒng)在Top500中位列第三,這兩臺高性能計算機系統(tǒng)的發(fā)布極大地提高了我國在國際高性能計算領(lǐng)域的地位。而在最新發(fā)布的2011年Top500排名中,前五臺超級計算機中有三臺都是采用了異構(gòu)并行體系結(jié)構(gòu)模型。可以看出,異構(gòu)并行系統(tǒng)作為ー種新興的體系結(jié)構(gòu),逐漸被越來越多的高性能計算研究機構(gòu)采納,其高效能優(yōu)勢將有力推動高性能計算的發(fā)展。最后需要說明的是，文章在后面章節(jié)中出現(xiàn)的異構(gòu)系統(tǒng)是我們對于由CPU和GPU構(gòu)建的異構(gòu)并行系統(tǒng)的簡稱，與異構(gòu)并行計算機和異構(gòu)并行系統(tǒng)的概念是相同的。大規(guī)模并行系統(tǒng)的可靠性問題可靠性是高性能計算領(lǐng)域的經(jīng)典問題之一。隨著高性能計算在應(yīng)用領(lǐng)域的逐漸普及和發(fā)展,以及大規(guī)模并行系統(tǒng)規(guī)模的不斷擴大,提高可靠性的需求越來越迫切;而高性能計算機所呈現(xiàn)出的發(fā)展趨勢則使得可靠性問題面臨著更加嚴(yán)峻的挑戰(zhàn)。微處理器的可靠性問題目前,微處理器芯片制造工藝已經(jīng)達(dá)到數(shù)十納米的量級,例如Intel公布的32納米Corei3,i5,i7處理器［⑵⑶和AMD公布的45納米Phenom處理器口支隨著集成電路的特征尺寸不斷減小,工作頻率不斷提高,芯片的供電電壓也在不斷降低,圖1.3顯示了!ntel處理器供電電壓逐年降低的情況けL圖1.3Intel圖1.3Intel處理器電源電壓的變化趨勢(と36"10>A_ddns工作電壓低意味著保持穩(wěn)定的邏輯狀態(tài)所需要的電量少,也就是說邏輯狀態(tài)翻轉(zhuǎn)所需要的電量少,根據(jù)文獻(xiàn)［16］,在目前的工藝水平下,邏輯狀態(tài)翻轉(zhuǎn)所需要的電量已經(jīng)達(dá)到了若干個飛庫這ー量級。因此隨著集成電路特征尺寸的減小、電源電壓的降低和頻率的升高，微處理器對各種電磁場、輻射源等外界環(huán)境的干擾將更加敏感，并可能引發(fā)錯誤的操作,導(dǎo)致了微處理器的故障發(fā)生率不斷攀升,微處理器的可靠性不斷降低〇另一方面,微處理器的功耗密度在不斷增加,功耗密度每18-24月增加一倍,這稱為功耗的摩爾定律“久功耗密度的增加使得熱量對系統(tǒng)可靠性的影響加劇;改善的工藝往往采用更低的供電電壓,這會導(dǎo)致切換電流的噪聲影響惡化。這些因素都會影響系統(tǒng)部件的可靠性,從而進(jìn)ー步影響了系統(tǒng)的可靠性。系統(tǒng)部件的溫度在不斷上升,一般來說,在2ドC基礎(chǔ)上,溫度每升高10"C,系統(tǒng)的失效率就會提高一倍"明系統(tǒng)規(guī)模擴大對可靠性的影響直到目前為止,提高計算機性能的主要手段仍是增加處理器數(shù)目。圖1.4給岀了2000年以來Top500前20臺超級計算機的處理器數(shù)目平均值。由此可見,高性能計算機的規(guī)模在迅速擴大。當(dāng)前世界上最快也是規(guī)模最大的計算機,日本的“京”由68544個SPARC64VHIfx處理器組成,每個處理器均內(nèi)置8個內(nèi)核,總內(nèi)核數(shù)量高達(dá)548,352個ひ】。而排在第20名的CrayXE6,其處理器核心數(shù)也達(dá)到了42,712〇從可靠性理論的角度看,如果單個部件的可靠性是固定的,那么在沒有額外容錯措施的情況下,構(gòu)成系統(tǒng)的部件越多系統(tǒng)的可靠性就會越低。160000160000140000120000100000800006000040000200000圖1.4Top500前20臺超級計算機系統(tǒng)的平均處理器核心數(shù)量圖1.5給出了在單結(jié)點可靠度R=0.99999的情況下,根據(jù)圖1.4中的節(jié)點數(shù)量計算而得出的系統(tǒng)MTBF時間。MTBF的計算公式為:MTBF?—\-Rn其中N為節(jié)點數(shù)量。由圖1.5中可以看出,系統(tǒng)的MTBF隨系統(tǒng)規(guī)模的增大,降低幅度也很大,在處理器規(guī)模為148933時,MTBF只有1.3小時左右。圖1.5不同規(guī)模下系統(tǒng)的MTBF變化趨勢相關(guān)數(shù)據(jù)顯示,當(dāng)一臺大規(guī)模的!BM/LLNLASCIWhite系統(tǒng)在持續(xù)運行過程中,其MTBF最多不超過40個小時1電,而一臺擁有8000個節(jié)點的Google集群系統(tǒng),其單節(jié)點失效率達(dá)到了2-3%/年のし那么換ー種說法,其MTBF也僅僅為36小時⑶】。可見,系統(tǒng)規(guī)模的急劇擴大必將導(dǎo)致系統(tǒng)的平均故障時間間隔(MTBF)大幅降低。另一方面,目前的科學(xué)計算程序往往需要連續(xù)運行幾天甚至幾個月，例如BlueGene上的蛋白質(zhì)折疊(protein-folding)程序需要運行好幾個月,科學(xué)計算程序難以在大規(guī)模系統(tǒng)上正確地完成計算。所以,可靠性問題已成為高性能計算機發(fā)展的重大挑戰(zhàn)之一。Petaflop規(guī)模的計算的成功取決于大規(guī)模系統(tǒng)可靠性技術(shù)的發(fā)展，如何確保其上運行的科學(xué)計算程序能夠正確地完成是大規(guī)模計算機系統(tǒng)必須解決的重大問題之一［22,231。大規(guī)模異構(gòu)并行計算機面臨的可靠性挑戰(zhàn)異構(gòu)并行計算機由于具有強大的GPU并行處理能力,使其與傳統(tǒng)的同構(gòu)系統(tǒng)相比擁有更高的并行計算性能。然而由于其更為復(fù)雜的架構(gòu)、更高的功耗和不同于目前已經(jīng)比較成熟的同構(gòu)系統(tǒng)計算機的編程模型,使得異構(gòu)并行計算機面臨更多方面的問題。與大規(guī)模并行系統(tǒng)所面臨的可靠性問題相同,由于商用GPU的可靠性相比通用處理器來說更低,因此異構(gòu)并行計算機的可靠性問題也更為嚴(yán)峻。雖然GPU擁有超越CPU的強大計算能力,但是它并不能取代CPU來處理一些一般事務(wù)性的應(yīng)用。一般的異構(gòu)系統(tǒng)由CPU和GPU組成,它們之間通過PCI-E總線相連,各自的存儲系統(tǒng)可以通過DMA操作來進(jìn)行大塊的數(shù)據(jù)傳輸。當(dāng)ー個異構(gòu)程序在異構(gòu)系統(tǒng)上運行時,CPU和GPU之間是ー種主從關(guān)系,CPU負(fù)責(zé)主控程序的執(zhí)行,以調(diào)用的方式啟動GPU進(jìn)行異步運算,同時與GPU進(jìn)行通信;GPU響應(yīng)CPU發(fā)起的調(diào)用,并完成計算。可見,異構(gòu)并行計算機在體系結(jié)構(gòu)上相對于傳統(tǒng)的同構(gòu)計算機更為復(fù)雜，而這種體系結(jié)構(gòu)所具有的特性也為其帶來了許多新的問題。因此對于異構(gòu)并行計算機而言,所需考慮的可能會影響其可靠性的因素也必然更多。?編程復(fù)雜引發(fā)的可靠性問題異構(gòu)并行系統(tǒng)的出現(xiàn)進(jìn)ー步增加了大規(guī)模并行系統(tǒng)編程難度陰旬,由于異構(gòu)并行系統(tǒng)集成有多種類型的處理器,而不同類型的處理器可能具有不同的體系結(jié)構(gòu)抽象層次，因此異構(gòu)混合編程模型成為當(dāng)前異構(gòu)并行系統(tǒng)編程的主要方式。通常,異構(gòu)混合編程模型融合有多種不同抽象層次的編程模型,極大地增加了大規(guī)模并行系統(tǒng)的編程和調(diào)試難度。此外，由于GPU具有極高數(shù)量的核心和超高的并行計算能力，其利用并行多線程來處理海量的數(shù)據(jù)，更為復(fù)雜的線程及寄存器管理機制也導(dǎo)致了程序員需要更加細(xì)致地分配和使用各類系統(tǒng)資源。以NVIDIA提供的CUDA編程模型為例,程序員需要綜合考慮線程空間、寄存器、片上軟件管理存儲等資源以最大化GPU的執(zhí)行性能。這些都使得面向異構(gòu)并行系統(tǒng)的編程變得更為復(fù)雜和困難，而將一般的科學(xué)計算程序修改為專門應(yīng)用于異并行系統(tǒng)時也更容易出現(xiàn)錯誤,由此引發(fā)可靠性問題。?GPU部件的可靠性問題GPU中晶體管的集成度相比CPU更高,同時具有更多的流計算單元以供計算,NVIDIA最新發(fā)布的Fermi架構(gòu)GPU具有512個處理器核心。因此其可靠度相對于CPU更低。?功耗引發(fā)的可靠性問題在整個異構(gòu)系統(tǒng)的計算過程中GPU負(fù)載了絕大部分計算,這也使其功耗更高。雖然相對以往的處理器而言,以CELL和GPU等為代表的加速部件已經(jīng)有效地提高了系統(tǒng)性能功耗比，緩解了高性能計算的功耗問題，但是對于大規(guī)模高性能的異構(gòu)并行計算機而言,其高功耗問題依然存在の，2句。當(dāng)前的大規(guī)模異構(gòu)并行系統(tǒng)中，Tianhe-IA系統(tǒng)功耗是4.04MW127],而星云(Nebulae)也達(dá)到了2.58MW。巨大的功耗會使系統(tǒng)部件的溫度升高,高溫環(huán)境下運行也提高了芯片的失效率,從而導(dǎo)致計算機系統(tǒng)可靠度的下降。?存儲引發(fā)的可靠性問題如同一般計算機的內(nèi)存ー樣,GPU的存儲系統(tǒng)主要也是用于存儲GPU端計算

時所必需的或者計算處理后的臨時數(shù)據(jù),一般GPU存儲系統(tǒng)都采用RAM存儲器,這一存儲器雖然具有超高的訪問速度,但也具有易失性和對靜電敏感等特性,容易造成數(shù)據(jù)流失及由于故障而引發(fā)數(shù)據(jù)錯誤,因此其可靠性必然遠(yuǎn)低于計算機中的硬盤等外存設(shè)備。?通信引發(fā)的可靠性問題異構(gòu)并行計算機在運行大規(guī)模的科學(xué)計算程序時,需要CPU與GPU之間的不斷通信,因此PCI-E總線作為CPU和GPU通信的外部設(shè)備，其可靠性問題對于整個系統(tǒng)就顯得至關(guān)重要。同時,由于GPU端存儲空間非常小,而在大規(guī)模計算時可能需要保存大量的狀態(tài)數(shù)據(jù)，這就使得GPU在保存所需數(shù)據(jù)時必須將數(shù)據(jù)傳輸?shù)紺PU端，進(jìn)行CPU與GPU的數(shù)據(jù)傳遞,而在多次大量數(shù)據(jù)的傳輸過程中也可能會出現(xiàn)由故障引發(fā)的錯誤,這對于當(dāng)前的各種大規(guī)模科學(xué)計算程序而言,異構(gòu)并行計算機在通信的數(shù)據(jù)傳輸過程中出現(xiàn)由故障引發(fā)錯誤的概率將會是極大的,由通信而導(dǎo)致的可靠性問題極為嚴(yán)峻。可見,由于異構(gòu)并行計算機對于CPU和GPU間通信的高依賴性,針對異構(gòu)并行計算機在通信可靠性問題上的研究也更為至關(guān)重要。?通信瓶頸導(dǎo)致容錯困難從80年代以來,處理器性能的年增長速度曾一度超過50%,而存儲器性能的年增長速度平均只有7%[2叫如圖1.6所示。這使得處理器和存儲器之間的速度差距越來越大，導(dǎo)致了“存儲墻”問題的出現(xiàn)128,2叫而隨著多核處理器以及各種加速部件的出現(xiàn),“存儲墻”問題不但沒有緩解反而變得更加嚴(yán)重,這ー問題對于具有超高并行計算能力的異構(gòu)并行系統(tǒng)來說同樣存在MT”1980 1985 1990 1995 2000 2005 2010Ywr1980 1985 1990 1995 2000 2005 2010Ywr圖1.6處理器和存儲器的性能增長速度ゆ】同時,異構(gòu)并行系統(tǒng)還存在通信瓶頸的問題。在進(jìn)行大規(guī)模科學(xué)計算時,由于PCI-E總線的帶寬速度所限，當(dāng)CPU與GPU進(jìn)行通信時如果有大量的數(shù)據(jù)信息時，就會嚴(yán)重影響異構(gòu)并行系統(tǒng)的性能。另ー方面，當(dāng)容錯技術(shù)應(yīng)用于異構(gòu)并行系統(tǒng)時，由于冗余機制同樣需要保存大量的狀態(tài)數(shù)據(jù),那么在GPU超越CPU計算能力幾十倍的同時,如果沒有一個比現(xiàn)在帶寬快幾十倍的總線支持的話,其所獲得的容錯性能也會大打折扣,甚至使得一些容錯技術(shù)根本無法應(yīng)用于異構(gòu)并行系統(tǒng)。容錯技術(shù)的受限對系統(tǒng)的可靠性也會產(chǎn)生巨大的影響。以上這些都是有可能降低異構(gòu)并行系統(tǒng)可靠性的因素，且隨著異構(gòu)并行計算機規(guī)模的不斷擴大,其可靠性問題也會更加的嚴(yán)峻。由此可見,異構(gòu)并行計算機在具有更為復(fù)雜的體系結(jié)構(gòu)和超高的并行計算性能的同時也為其可靠性帶來了諸多問題以及前所未有的挑戰(zhàn)。本文專門就異構(gòu)并行計算機的可靠性問題,對面向異構(gòu)并行計算機的容錯技術(shù)展開研究，對于異構(gòu)系統(tǒng)上不同的故障類型及不同容錯技術(shù)基于異構(gòu)系統(tǒng)特性的合理應(yīng)用及優(yōu)化方法進(jìn)行討論和分析。雖然異構(gòu)并行系統(tǒng)的可靠性問題更為復(fù)雜,也面臨許多新的問題，但由于異構(gòu)并行系統(tǒng)的特有的性質(zhì),也帶了很多新的思路和研究空間，使得對于異構(gòu)并行系統(tǒng)的容錯技術(shù)研究更有意義。容錯研究基礎(chǔ)容錯基本概念容錯是系統(tǒng)的ー種能力——在發(fā)生故障時仍能完成預(yù)定的功能。1967年,Avizienis在文獻(xiàn)［33］中第一次提出了容錯的概念:“如果在發(fā)生邏輯故障的情況下,系統(tǒng)中的程序仍然能夠正確地執(zhí)行,那么我們就稱這個系統(tǒng)是可容錯的。”通常有三個描述故障的術(shù)語:故障（Fault）＞錯誤（Error）和失效（Failure）〇這三個概念因コ川的關(guān)系如圖1.7所示。物理級 計算級 系統(tǒng)級圖1.7故障、錯誤與失效三者的關(guān)系故障是系統(tǒng)的硬件中發(fā)生的物理缺陷、設(shè)計制造的不完善或軟件中隱含的錯誤。錯誤是系統(tǒng)中的某一部分由于故障而產(chǎn)生了非正常的行為或狀態(tài)的現(xiàn)象。失效是系統(tǒng)在運行到ー定的時間,或在一定的條件下偏離它預(yù)期設(shè)計的要求或規(guī)定的功能。故障、錯誤與失效構(gòu)成一個因果鏈,即故障引起錯誤,錯誤又引起失效。故障會造成錯誤,但并不總是故障ー出現(xiàn)就立即會產(chǎn)生錯誤,從故障發(fā)生至由于該故障而產(chǎn)生錯誤的時間間隔稱為故障潛伏期(faultlatency);同樣,錯誤會造成失效,但并不總是錯誤ー發(fā)生就會造成失效。從錯誤發(fā)生至由于該錯誤而造成失效的時間間隔稱為錯誤潛伏期(errorlatency)。從故障發(fā)生至造成失效的時間間隔稱為失效潛伏期(failurelatency),是故障潛伏期和錯誤潛伏期之和。故障的來源很多,可能是設(shè)計、生產(chǎn)、裝配過程中的缺陷,也可能是使用過程中外部因素的影響。事先檢測出所有設(shè)計和生產(chǎn)過程中的故障是極其困難的,有些故障只在特定條件下オ會引起錯誤。例如,1994年,人們發(fā)現(xiàn)IntelPentiumI微處理器在計算特定浮點除法時得到不正確的結(jié)果。比如5505(X)1除以294911得到18.66600093而不是18.66665197。問題的原因是除法算法用到了一張包含1066個值的表,其中的5個單元原本應(yīng)該存放常數(shù)+2,但是實際上是空的,處理器把它們看作〇い叫電子器件在使用過程中可能會受到電カ問題和宇宙輻射的影響而發(fā)生故障，而這種故障幾乎不可能完全消除。研究表明一個典型的計算機系統(tǒng)每個月要經(jīng)歷120次電カ問題后汽在海平面的高度上,如果想要完全防止所有粒子對電子器件的影響,至少需要6英尺厚的混凝土屋頂巨曳故障類型設(shè)計容錯機制,首先需要確定故障的類型。按照故障的來源,可分為硬件故障和軟件故障。這里我們不考慮系統(tǒng)邊界外的故障,如操作員的過失導(dǎo)致的系統(tǒng)失效問題。按照故障的持久性，硬件故障分為瞬時故障、永久故障和間歇故障。瞬時故障只存在ー小段時間,一般來說,發(fā)生在某個邏輯單元上的瞬時故障在下一次該邏輯單元被寫入時就會消失。瞬時故障在計算機系統(tǒng)的存儲部件中是最主要的故障類型。據(jù)統(tǒng)計，存儲系統(tǒng)中發(fā)生的的故障98%都是瞬時故障〔37】。瞬時故障的發(fā)生多是由于環(huán)境的影響,例如alpha粒子,宇宙射線的照射等等。永久故障來源于硬件的制造缺陷,例如短路、斷路等。除非采取一定的修補措施,否則永久故障將一直存在。間歇故障類似于瞬時故障,不同的是,間歇故障會在某段時間內(nèi)連續(xù)發(fā)生。間歇故障意味著硬件的老化，如果不加以修補就會轉(zhuǎn)化成永久故障。與硬件不同,軟件不會磨損,不會老化，因此軟件故障僅來源于設(shè)計錯誤和實現(xiàn)錯誤。盡管現(xiàn)有的軟件測試、驗證和調(diào)試技術(shù)已經(jīng)能夠在很大的程度上提高軟件的正確性，但仍然無法完全排除軟件體系結(jié)構(gòu)和具體實現(xiàn)中存在的缺陷。盡管可以通過升級對軟件故障進(jìn)行修復(fù)，但升級的同時也可能引入新的bugo因此,在計算機系統(tǒng)中,軟件故障也是比較常見的故障類型。在高性能計算機系統(tǒng)上運行的科學(xué)計算程序相對于一般的應(yīng)用程序來說具有一定的特殊性。科學(xué)計算程序一般代碼規(guī)模不大,但計算量和數(shù)據(jù)量卻是海量的,并且運行時間比較長,所以在高性能計算機系統(tǒng)中,我們將更多的注意力集中在針對硬件故障的容錯技術(shù)上。故障模型按照故障在系統(tǒng)中的傳播以及對系統(tǒng)的影響，一般可以將故障歸結(jié)為兩類模型,fail-stop模型和Byzantine模型13用。fail-stop模型網(wǎng)描述了一種比較樂觀的情形,即故障發(fā)生后,除了發(fā)生故障的部件以外，系統(tǒng)中其他部分都不會受到該故障的影響〔軸。實際上,完全的fail-stop模型幾乎是不存在的，因為故障總會在系統(tǒng)中傳播一定的距離。例如，由于現(xiàn)代微處理器很少會在寄存器上添加類似ECC校驗這樣的保護(hù)措施，因此某個寄存器的故障所導(dǎo)致的數(shù)據(jù)錯誤一般都會沿著定義引用關(guān)系傳播到其他寄存器中。再例如并行系統(tǒng)在運行某個程序時,如果某個結(jié)點由于電源、溫度等原因停機,那么在操作系統(tǒng)或運行時環(huán)境檢測到該故障并報錯之前,其他結(jié)點可能由于與故障結(jié)點存在數(shù)據(jù)依賴關(guān)系而受到了故障的影響。fail-stop故障模型可描述并行計算中進(jìn)程掛起或崩潰的情況い制。］,是并行計算領(lǐng)域最常用的故障模型。Byzantine模型［現(xiàn)描述了非常普遍的故障類型,即故障發(fā)生后,其結(jié)果會在系統(tǒng)傳播一定的范圍圖"的。例如,在并行系統(tǒng)中,如果并行執(zhí)行的多個進(jìn)程中有某個進(jìn)程由于硬件故障導(dǎo)致某些變量的值發(fā)生了錯誤，那么這些錯誤將有可能沿著通信操作傳播到其他進(jìn)程,造成其他進(jìn)程上的計算錯誤,而這種錯誤往往會傳播到程序的結(jié)果中,引起失效。Byzantine模型可以表示任意故障,但檢測這類故障非常困難ゆラ％在異構(gòu)并行機系統(tǒng)中,這兩種類型的故障都較常見，因此本文的研究也是針對這兩種故障類型的不同容錯技術(shù)。相關(guān)研究工作本課題主要針對異構(gòu)并行計算機的容錯技術(shù)進(jìn)行研究，為此,我們進(jìn)行了大量的調(diào)研工作，下面針對并行應(yīng)用的容錯技術(shù)的研究工作進(jìn)行總結(jié)。這些相關(guān)技術(shù)的研究和進(jìn)展對本課題的工作具有很大的啟發(fā)和指導(dǎo)意義。本節(jié)中我們概括了近年來計算機系統(tǒng)容錯技術(shù)的現(xiàn)有研究成果和相關(guān)技術(shù)、方法和實踐工作,并在最后對當(dāng)前面向異構(gòu)并行系統(tǒng)的現(xiàn)有的一些容錯技術(shù)及研究成果進(jìn)行總結(jié)和介紹。容錯常用方法容錯的基本途徑是冗余。通過冗余來提高可靠性的思想最早是在20世紀(jì)50年代由JohnvonNeumann所提出來的網(wǎng)。冗余可分為兩大類:空間冗余和時間冗余。空間冗余是指通過提供額外的資源如器件、函數(shù)或數(shù)據(jù)來實現(xiàn)容錯。時間冗余則是指通過重復(fù)計算過程或數(shù)據(jù)傳輸過程來實現(xiàn)容錯。根據(jù)額外添加的冗余資源的不同,空間冗余又分為硬件冗余(比如三模冗余,TMR)、軟件冗余(比如多版本,Multi-version)和信息冗余(糾錯碼,如ErrorCorrectionCode,ECC)〇我們將并行計算領(lǐng)域的各種容錯方法大致分為以下四類:1.基于算法的容錯(Algorithm-basedfaulttolerance)2,并行復(fù)算(Parallelrecomputing).算法相關(guān)的容錯(Algorithm-dependentfaulttolerance).回滾恢復(fù)(Rollback-recovey)基于算法的容錯技術(shù)主要是面向數(shù)值運算應(yīng)用特別是矩陣運算應(yīng)用的容錯技術(shù)。它的基本思想是對計算數(shù)據(jù)進(jìn)行某種編碼,在算法執(zhí)行過程中檢查這種編碼是否仍然保留，從而判斷是否發(fā)生了錯誤⑻々叫并行復(fù)算是由國防科學(xué)技術(shù)大學(xué)計算機學(xué)院楊學(xué)軍教授等人提出的新的容錯技術(shù)ワリ。并行復(fù)算的核心思想是:在發(fā)生故障時,將故障處理器上因故障而丟失的負(fù)載分配到剩余的無故障處理器上并行的重算,以加快故障恢復(fù)速度ル】。并行復(fù)算方法并不要求額外添加資源，只是利用了現(xiàn)有的冗余的硬件資源(如處理器和結(jié)點內(nèi)存),因此我們認(rèn)為它屬于時間冗余的容錯方法。并行復(fù)算特別適合計算密集型的應(yīng)用。在這類應(yīng)用中,每個進(jìn)程分配到的計算量很大,采用并行復(fù)算的方法來恢復(fù)故障進(jìn)程上的計算可以顯著縮短容錯的時間開銷⑺フ叫盡管并行復(fù)算技術(shù)是一種很有潛力的容錯技術(shù)，但與任何其它新技術(shù)ー樣，并行復(fù)算也存在ー些還需進(jìn)ー步研究解決的問題(比如在通信較多的應(yīng)用中如何發(fā)揮并行復(fù)算的性能優(yōu)勢)。算法相關(guān)的容錯方法是ー類特殊的容錯方法,它是根據(jù)某些并行算法的特點開發(fā)的有針對性的容錯方法,可以達(dá)到非常低的容錯開銷。美國圣地亞國家實驗室最先開展了這類容錯方法的研究174］。對于某些算法，例如異步并行直接搜索(AsynchronousParallelDirectSearch),ー小部分?jǐn)?shù)據(jù)的丟失不會影響計算任務(wù)的正確執(zhí)行。在這種情況下,不需要故障通知和故障恢復(fù)等步驟,算法可實現(xiàn)天然的容錯け?］。還有些并行算法,盡管它們必須恢復(fù)故障時丟失的所有數(shù)據(jù)才能正確執(zhí)行,但是可以根據(jù)算法的特點設(shè)計非常高效的容錯方法向朋］。對于算法相關(guān)的容錯方法,需要程序員對算法非常了解，并能充分利用算法某些特點精心設(shè)計出獨特而高效的容錯方案,因此,這種方法對程序員的要求很高,并且只能個例研究,難以推廣。回滾恢復(fù)的基本思想是計算過程中周期性地保存計算狀態(tài),當(dāng)故障發(fā)生后,

應(yīng)用程序回滾到之前保存的某個狀態(tài)處重新開始執(zhí)行岡ホ"。回滾恢復(fù)方法要求重復(fù)執(zhí)行從故障前的某個狀態(tài)到故障發(fā)生處之間的計算過程,但是一般要求額外的存儲空間保存恢復(fù)所需的計算狀態(tài)數(shù)據(jù),因此這種容錯方法結(jié)合了時間冗余和空間冗余。圖1.8列出了幾種常用的容錯方法。在分布式和并行計算領(lǐng)域,回滾恢復(fù)方法得到普遍關(guān)注和廣泛應(yīng)用。軟件兒 Multi-version冗余硬件冗余TMR軟件兒 Multi-version冗余ECCABFT<Parallelrecomputing

時間冗余?Rollback-recovery圖1.8容錯方法分類Rollback-recovery容錯技術(shù)分析Rollback-recovery最開始起源于分布式系統(tǒng)領(lǐng)域,它假設(shè)故障是fail-stop類型。在分布式系統(tǒng)領(lǐng)域,容錯的目標(biāo)是關(guān)鍵系統(tǒng)（如web服務(wù)器和空中交通管制系統(tǒng)）的零停工期（zerodowntime）[871〇而本文所關(guān)注的高性能計算領(lǐng)域中容錯的目標(biāo)則是在一定故障概率下使程序執(zhí)行完成的期望時間最短18用。另外,與高性能計算機上的大規(guī)模科學(xué)計算程序相比，分布式系統(tǒng)上的程序在執(zhí)行期間通信的頻率和傳遞的數(shù)據(jù)量要小得多。因此，有些在分布式系統(tǒng)領(lǐng)域表現(xiàn)良好的容錯技術(shù)并不適合高性能計算領(lǐng)域,有些則需要改進(jìn)才能應(yīng)用到高性能計算領(lǐng)域。本節(jié)通過對Rollback-recovery技術(shù)的分析來揭示本文我們選擇應(yīng)用級checkpointing技術(shù)作為研究對象的原因，同時也為后續(xù)的新的相關(guān)容錯技術(shù)的研究的展開打下基礎(chǔ)。Rollback-recovery將系統(tǒng)（分布式系統(tǒng)或高性能計算系統(tǒng)）看作一組應(yīng)用進(jìn)程的集合。這些進(jìn)程可以通過網(wǎng)絡(luò)相互通信，并且能夠訪問ー個稱之為穩(wěn)定存儲器（stablestorage）的存儲設(shè)備網(wǎng)。每個進(jìn)程的執(zhí)行被看作一組狀態(tài)間隔（stateintervals）序列,每個狀態(tài)間隔從一個非確定性事件（如用戶輸入或消息到達(dá)）開始，直到下ー個非確定性事件。各進(jìn)程在無故障運行期間周期性地將恢復(fù)計算所需的信息（即checkpoint,也叫計算狀態(tài)）保存到穩(wěn)定存儲器;發(fā)生故障后,利用checkpoint恢復(fù)到保存該checkpoint時的計算狀態(tài)。通過這種方式,Rollback-recovery技術(shù)減小了故障造成的損失。關(guān)于Rollback-recovery正確性的一般條件是“如果系統(tǒng)的內(nèi)部狀態(tài)與故障前的可觀察行為是一致的,則系統(tǒng)可正確恢復(fù)"1901〇整個應(yīng)用的計算狀態(tài)是各進(jìn)程的checkpoint的集合。由于各進(jìn)程之間可能發(fā)生消息傳遞,因此,Rollback-recovery協(xié)議要維護(hù)進(jìn)程內(nèi)部交互的信息以及應(yīng)用與外部交互的信息。Rollback-recovery技術(shù)可分為兩大類:checkpoint-based（也稱checkpointing）和log-based（也稱message-logging）〇本文所研究的面向異構(gòu)并行系統(tǒng)的容錯技術(shù)都涉及到了Rollback-recovery容錯機制,在后文的闡述中會對如何使用這一機制作進(jìn)ー步的描述和討論。TMR容錯技術(shù)分析三模冗余（TripleModularRedundancy,TMR）出“是N模冗余的特例（^=3）,TMR常作為其他冗余技術(shù)的基礎(chǔ)，是在實際應(yīng)用中最為廣泛使用的冗余技術(shù)。個基本的TMR系統(tǒng)的結(jié)構(gòu)如圖1.9所示。三個相同的模塊接收同一個輸入，產(chǎn)生的三個結(jié)果送至多數(shù)投票器投票表決。投票器的輸出取決于它的三個輸入中的多數(shù)一方的結(jié)果。若有一個模塊出現(xiàn)故障,則另外兩個正常模塊的輸出可將故障模塊的錯誤輸出掩蓋,因而不會在投票器輸出端產(chǎn)生差錯。可以看出,三模冗余結(jié)構(gòu)使系統(tǒng)可以正常工作的條件是:或三模都正常，或三模中任意二模正常。模塊I圖1.9基本TMR系統(tǒng)結(jié)構(gòu)三模冗余中,具備幾種關(guān)鍵機制:比較、投票、賦值與標(biāo)記（mask）機制。其中比較機制就是通過對通信時三個副本各自的結(jié)果進(jìn)行比對,從而達(dá)到對故障進(jìn)行檢測的目的;投票機制就是在有副本出現(xiàn)不同結(jié)果時對三個副本的結(jié)果進(jìn)行表決投票,選取出兩個相同的，將其視為正確結(jié)果，并賦值給出現(xiàn)不同結(jié)果的副本,可見投票和賦值是一起使用的。當(dāng)然,如果在投票失敗,即三個副本結(jié)果各不相同時,系統(tǒng)不予賦值,而是視作全部出現(xiàn)故障而直接重啟計算。最后的標(biāo)記機制就是在投票結(jié)束后對出現(xiàn)不同的副本不予賦值，而是標(biāo)記出來，以剩下的兩

個副本繼續(xù)進(jìn)行計算。綜上所述,三模冗余是ー種故障屏蔽技術(shù)(FaultMaskingTechnology)1371,它可以防止系統(tǒng)中的故障在該系統(tǒng)的信息結(jié)構(gòu)中產(chǎn)生差錯,利用冗余資源將故障影響掩蓋起來,或隔離或校正,從而達(dá)到容錯目的。本文所研究的容錯技術(shù)就涉及到了三模冗余機制,因此我們對三模冗余機制在異構(gòu)并行系統(tǒng)上的應(yīng)用展開了深入的研究。Checkpointing容錯技術(shù)分析Checkpointing是一種廣泛應(yīng)用于大規(guī)模科學(xué)計算領(lǐng)域中的容錯技術(shù)。該技術(shù)是在程序執(zhí)行期間將計算狀態(tài)周期性的保存到可靠存儲器上四“00】。如果某個進(jìn)程失效，所有進(jìn)程都必須回滾到最近一個checkpoint處繼續(xù)計算。Checkpointing分為兩種基本的方法:系統(tǒng)級checkpointing(system-levelcheckpointing,SLC)和應(yīng)用級checkpointing(application-levelcheckpointing,ALC)〇Memory系統(tǒng)級ApplicaiijtajjjI?FGcef：fiorRegisters0班耶観》@日解観!も血!Memory《も應(yīng)用級ApplicaiijtajjjI?FGcef：fiorRegisters0班耶観》@日解観!も血!Memory《も應(yīng)用級Disk圖1.10Checkpointing技術(shù)系統(tǒng)級checkpointing將應(yīng)用狀態(tài)在存儲器上進(jìn)行映像(core-dump-stylesnapshots),即將所有進(jìn)程的地址空間內(nèi)容(堆、棧和全局變量)、寄存器信息和通信庫狀態(tài)存儲到穩(wěn)定存儲介質(zhì)上這種方法對應(yīng)用是完全透明的,如圖1.10(a)所示。但是,在大規(guī)模并行系統(tǒng)中，應(yīng)用狀態(tài)可能占用大量的存儲空間,因此所有進(jìn)程同時讀寫checkpoints的I/O數(shù)據(jù)量很大,從而使!/O成為大規(guī)模并行系統(tǒng)軍checkpointing技術(shù)的性能瓶頸肉。關(guān)多數(shù)應(yīng)用甲,整個計算狀態(tài)可以通過T關(guān)鍵數(shù)據(jù)結(jié)構(gòu)進(jìn)行恢復(fù)。應(yīng)用級checkpointing通過減小需要保存的數(shù)據(jù)量來改善性能〔皿』。3】,該技術(shù)允許用戶指定checkpointing的時機并選擇盡可能少的信息進(jìn)行保存"0叫應(yīng)用級checkpointing的基本思想是通過修改應(yīng)用代碼,保存問題的關(guān)鍵狀態(tài)而非整個系統(tǒng)狀態(tài),如圖1.10(b)所示。目前對于許多大規(guī)模平臺上的應(yīng)用,例如IBMBlueGene和ASCI,手工實現(xiàn)的應(yīng)用級checkpointing是默認(rèn)的容錯方法。然而,應(yīng)用級checkpointing仍然要求無故障進(jìn)程在恢復(fù)時回滾,重算上一個checkpoint到故障時刻之間的任務(wù)，這造成了計算時間的浪費。綜上所述，checkpointing技術(shù)是目前大規(guī)模并行計算領(lǐng)域廣泛接受的容錯技術(shù),系統(tǒng)級checkpointing雖然對用戶透明,但時空開銷均比較大。應(yīng)用級checkpointing雖然速一定程度上減小了應(yīng)用狀態(tài)的保存量,但仍需要全系統(tǒng)(包括無故障進(jìn)程)回滾,浪費了計算資源。本文就將checkpointing技術(shù)作為研究重點,并著重對于應(yīng)用級checkpointing技術(shù)在異構(gòu)并行計算機上的實現(xiàn)進(jìn)行了深入研究。在這里我們對文中所用的checkpointing技術(shù)的相關(guān)術(shù)語進(jìn)行說明:Checkpointing技術(shù):中文中譯為檢查點技術(shù),文中統(tǒng)ー用“checkpointing技術(shù)”作為這ー技術(shù)的專用名詞來進(jìn)行相關(guān)描述。Checkpoint!這個名詞形式術(shù)語的基本含義是恢復(fù)程序執(zhí)行所需的計算狀態(tài)數(shù)據(jù)。本文中常用于修飾其它名詞，如checkpoint位置、checkpoint指令等。Checkpoint數(shù)據(jù):含義與checkpoint相同,只是為了強調(diào)所指的是數(shù)據(jù)。Checkpoint時機：從程序動態(tài)執(zhí)行的角度看到的保存checkpoint數(shù)據(jù)的時間位置。Checkpoint位置：從程序靜態(tài)代碼的角度看到的checkpoint指令或checkpoint調(diào)用插入的空間位置。Checkpoint/Restart技術(shù)：與checkpointing技術(shù)概念相同,之所以加入restart有強調(diào)回滾恢復(fù)機制的意思,是對帶有回滾機制的checkpointing技術(shù)的完整表述。文中對這兩個術(shù)語酌情使用。優(yōu)化checkpoint的相關(guān)研究針對checkpointing技術(shù)的改進(jìn)工作主要集中于減小checkpointing技術(shù)的狀態(tài)保存開銷。文獻(xiàn)［106-108］提出了disklesscheckpointing技術(shù),它用高速的內(nèi)存代替低速的磁盤來存放checkpoint文件，并對各計算結(jié)點內(nèi)存中的checkpoint進(jìn)行編碼運算,并將編碼結(jié)果保存到checkpointingprocessors〇在大規(guī)模科學(xué)計算中，這種方法對內(nèi)存容量的要求比較高。Disklesscheckpointing技術(shù)中利用ー個冗余結(jié)點的資源，將各個結(jié)點的關(guān)鍵狀態(tài)保存到冗余結(jié)點上,在出現(xiàn)ー個結(jié)點失效的情況下，應(yīng)用通過冗余結(jié)點恢復(fù)失效結(jié)點的數(shù)據(jù),這種方法可以容忍ー個結(jié)點失效的情況,但是仍需保存系統(tǒng)狀態(tài)到冗余結(jié)點,這使得它的規(guī)模難以擴展。減少每個checkpoint的大小是提高應(yīng)用級checkpointing性能的關(guān)鍵。根據(jù)程序行為進(jìn)行優(yōu)化分析（如排除特定的變量或數(shù)據(jù)結(jié)構(gòu)）和不需要程序行為的優(yōu)化方法（如壓縮checkpoint大小）是兩類優(yōu)化checkpoint大小的基本方法。應(yīng)用級checkpointing的自動化采用根據(jù)程序行為進(jìn)行分析的方法優(yōu)化checkpoint大小。CATCH“091首次使用編譯技術(shù)輔助優(yōu)化checkpointing〇CATCH使用profiling技術(shù)確定程序中不同點處的checkpoint的可能大小,然后使用學(xué)習(xí)算法在保證兩次checkpoint間隔的前提下幫助用戶選擇在checkpoint大小最小的位置進(jìn)行checkpointing〇び系統(tǒng)中,Daniel等基于自己實現(xiàn)的堆管理機制對C/MPI中動態(tài)分配的堆區(qū)域進(jìn)行優(yōu)化⑴叫Plank等人通過數(shù)據(jù)流分析,找出存儲器中的“dead”數(shù)據(jù)和"read-only”數(shù)據(jù)，并在checkpoint中刪除這些數(shù)據(jù)""LYang等人將傳統(tǒng)編譯技術(shù)中的定值一引用分析擴展到了MPI并行程序,并基于該技術(shù)分析各個進(jìn)程上checkpoint位置處的活躍變量并保存到checkpoint中”⑵⑶。另外，對于某些特定的并行算法,存在其它有效的容錯方法。對于某些算法,ー小部分?jǐn)?shù)據(jù)的丟失不會影響計算任務(wù)的正確執(zhí)行。在這種情況下,不需要故障通知和故障恢復(fù)等步驟,算法可實現(xiàn)自然容錯。根據(jù)并行迭代和矩陣乘算法的特點,Bosilca和Chen分別提出了checkpoint-free的容錯機制""」⑶。將checkpoint文件的加載和故障恢復(fù)計算進(jìn)行重疊”⑹由］是加速故障恢復(fù)的另一手段。Tanenbaum等人利用虛存頁式管理機制記錄checkpoint中故障恢復(fù)計算真正需要的內(nèi)存頁”的,在故障恢復(fù)時，只要這些頁被加載，就可以開始進(jìn)行故障恢復(fù)計算。Li和Lan提出的FREM機制1”刀在每次checkpoint之后的一段時間內(nèi)（稱為trackingwindow）對進(jìn)程的存儲訪問進(jìn)行跟蹤，將這段時間內(nèi)被訪問的存儲位置記錄在ー個數(shù)據(jù)結(jié)構(gòu)中。在故障恢復(fù)的時候，優(yōu)先從checkpoint文件中讀取由該數(shù)據(jù)結(jié)構(gòu)指向的存儲位置,然后立即開始故障恢復(fù)計算。Checkpoint文件剩余部分的加載將與故障恢復(fù)計算重疊進(jìn)行。異構(gòu)并行計算機現(xiàn)有容錯方法當(dāng)前針對異構(gòu)系統(tǒng)的容錯問題所采用的大都是硬件冗余和軟件冗余技術(shù)。JeremyW.Sheaffer和NVIDIA研究小組的DavidP.Luebke等人在2007年設(shè)計了ー種面向超級計算領(lǐng)域的GPGPU可靠性的硬件冗余和恢復(fù)機制［”旬,NishantGeorge等人也在2008年DSN會議上提出了基于硬件雙模冗余和同步數(shù)據(jù)流技術(shù)的異構(gòu)系統(tǒng)的容錯方案“351,但是這些通過增加冗余硬件的容錯方法都并不適用于現(xiàn)在被廣泛使用的普通GPU。在硬件冗余技術(shù)提出的同時,基于軟件容錯的機制也被越來越多的研究者所關(guān)注MartinDimitrov等人提出了一種冗余執(zhí)行kernel的方式來對GPU上發(fā)生的瞬時故障進(jìn)行故障檢測い旬。AnthonyE.Gregerson等人分析了時間冗余、空間