呂宏武，谷 雷，王慧強(qiáng)，鄒世辰，馮光升

(哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150001)

(*通信作者電子郵箱guleicarter@gmail.com)

分層檢查點(diǎn)的近似最優(yōu)周期計(jì)算模型

呂宏武，谷 雷*，王慧強(qiáng)，鄒世辰，馮光升

(哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150001)

(*通信作者電子郵箱guleicarter@gmail.com)

針對大規(guī)模高性能計(jì)算(HPC)系統(tǒng)中檢查點(diǎn)效率提升問題，提出一種面向分層檢查點(diǎn)近似最優(yōu)周期計(jì)算模型。首先，通過分析一個HPC系統(tǒng)中應(yīng)用程序的執(zhí)行過程，將檢查點(diǎn)周期優(yōu)化抽象為一個非線性的檢查點(diǎn)成本模型；其次，通過分析可能故障位置推導(dǎo)出分層檢查點(diǎn)成本公式，并引入兩個減速因子和一個加速因子來模擬消息日志對分層檢查點(diǎn)造成的影響。仿真實(shí)驗(yàn)結(jié)果表明，所提模型與理論近似最優(yōu)周期檢查點(diǎn)成本平均誤差在5%以下，相對傳統(tǒng)檢查點(diǎn)周期優(yōu)化模型的平均誤差降低了20%，能夠有效提高檢查點(diǎn)的效率，提升HPC系統(tǒng)可用性。

高性能計(jì)算；容錯；分層檢查點(diǎn)；檢查點(diǎn)周期；近似最優(yōu)解

0 引言

隨著大規(guī)模和超大規(guī)模集成電路的問世，高性能計(jì)算(High Performance Computation, HPC)系統(tǒng)進(jìn)入高速發(fā)展期，根據(jù)International Exascale Software Project(IESP)的研究報(bào)告[1]顯示，HPC系統(tǒng)及其相關(guān)技術(shù)會持續(xù)發(fā)展。然而在實(shí)際部署與運(yùn)行中人們發(fā)現(xiàn)，系統(tǒng)的高復(fù)雜性、高異構(gòu)性導(dǎo)致HPC系統(tǒng)時(shí)刻面臨著錯誤、故障和失效對于系統(tǒng)可用性保障上的挑戰(zhàn)。Schroeder等[2]收集了兩個世界級的高性能計(jì)算平臺的故障數(shù)據(jù)，研究發(fā)現(xiàn)兩個高性能計(jì)算平臺每年的故障率在20～2 000次即平均8.7 h就會發(fā)生一次故障，且故障率與系統(tǒng)規(guī)模呈正比。由此可見容錯技術(shù)對于HPC系統(tǒng)變得越來越重要。

檢查點(diǎn)是目前HPC系統(tǒng)領(lǐng)域通常采用的容錯技術(shù)，通過在系統(tǒng)正常執(zhí)行時(shí)周期性地保存其最新狀態(tài)，在系統(tǒng)出現(xiàn)故障或失效等問題時(shí)，回滾到一致檢查點(diǎn)位置之后重新恢復(fù)執(zhí)行。采用檢查點(diǎn)的方式可以有效節(jié)省回滾恢復(fù)時(shí)間，延長系統(tǒng)可用時(shí)間，但是由于檢查點(diǎn)的設(shè)置與保存會占用一定的系統(tǒng)資源，因此檢查點(diǎn)周期的優(yōu)化直接關(guān)系到系統(tǒng)的容錯能力與恢復(fù)效率。檢查點(diǎn)周期是指系統(tǒng)設(shè)置并保存檢查點(diǎn)的時(shí)間間隔，通過對系統(tǒng)狀態(tài)與運(yùn)行情況進(jìn)行分析，選取合適的時(shí)間間隔進(jìn)行檢查點(diǎn)的設(shè)置與保存，一方面避免周期過小而導(dǎo)致檢查點(diǎn)頻繁設(shè)置保存對于系統(tǒng)資源的過度占用，一方面又避免周期過大導(dǎo)致系統(tǒng)回滾至過早的狀態(tài)。檢查點(diǎn)周期優(yōu)化的研究可以為檢查點(diǎn)協(xié)議提供最佳的性能，進(jìn)而提高大規(guī)模HPC系統(tǒng)的可用性。

然而隨著HPC系統(tǒng)結(jié)構(gòu)變得越來越復(fù)雜，檢查點(diǎn)周期優(yōu)化也面臨著狀態(tài)分析復(fù)雜度增加等一系列的挑戰(zhàn)。已有檢查點(diǎn)周期優(yōu)化的研究主要集中在不同的最優(yōu)化算法[3-4]和HPC系統(tǒng)結(jié)構(gòu)[5-6]上，卻忽略了檢查點(diǎn)結(jié)構(gòu)對檢查點(diǎn)性能的影響。HPC系統(tǒng)在實(shí)際工作中會受到許多外因諸如電壓、環(huán)境溫度的影響而產(chǎn)生系統(tǒng)性能抖動，這種性能抖動非常小，在理論研究過程中一般會忽略這種抖動而認(rèn)為系統(tǒng)性能是穩(wěn)定的，因此目前所有的檢查點(diǎn)周期優(yōu)化模型都是一種次優(yōu)模型，即近似最優(yōu)。本文首先將檢查點(diǎn)周期優(yōu)化抽象為一個非線性的檢查點(diǎn)成本模型；然后通過分析分層檢查點(diǎn)結(jié)構(gòu)的特點(diǎn)，根據(jù)該模型對分層檢查點(diǎn)的近似最優(yōu)周期進(jìn)行計(jì)算；最后通過仿真實(shí)驗(yàn)驗(yàn)證了本文所提模型的有效性。

1 相關(guān)工作

檢查點(diǎn)技術(shù)核心思想是將程序的最近運(yùn)行狀態(tài)保存至檢查點(diǎn)內(nèi)，并在故障發(fā)生時(shí)通過讀取檢查點(diǎn)使程序恢復(fù)至最近正常狀態(tài)。因此，檢查點(diǎn)技術(shù)的關(guān)鍵是要保證程序進(jìn)程狀態(tài)的一致性。不同檢查點(diǎn)協(xié)議使用了不同的機(jī)制來保證進(jìn)程狀態(tài)的一致性，然而正是這些機(jī)制導(dǎo)致了檢查點(diǎn)技術(shù)在大規(guī)模HPC系統(tǒng)中出現(xiàn)性能降級。經(jīng)過檢查點(diǎn)技術(shù)的多年發(fā)展，目前有三類非常成熟的檢查點(diǎn)協(xié)議：非協(xié)同檢查點(diǎn)協(xié)議、協(xié)同檢查點(diǎn)協(xié)議和分層檢查點(diǎn)協(xié)議。

分層檢查點(diǎn)[7]是一種最近提出的檢查點(diǎn)協(xié)議，它在結(jié)合協(xié)同檢查點(diǎn)與非協(xié)同檢查點(diǎn)優(yōu)點(diǎn)的同時(shí)克服了兩者的一些性能缺陷。分層檢查點(diǎn)的核心思想是在分布式系統(tǒng)中將分布在不同的計(jì)算節(jié)點(diǎn)中的進(jìn)程分組，其中進(jìn)程組內(nèi)使用協(xié)同檢查點(diǎn)，在進(jìn)程組間使用消息日志的非協(xié)同檢查點(diǎn)。這樣設(shè)計(jì)的優(yōu)點(diǎn)是進(jìn)程組之間相互獨(dú)立，因此當(dāng)某組進(jìn)程在設(shè)置檢查點(diǎn)的時(shí)候，其他組的進(jìn)程能夠并行地繼續(xù)自己的計(jì)算工作，不會因?yàn)檫M(jìn)程阻塞浪費(fèi)執(zhí)行時(shí)間，減少了同一時(shí)刻參與存儲的進(jìn)程的數(shù)目，從而增加每個參與進(jìn)程的存儲帶寬，這樣就減少了每個進(jìn)程檢查點(diǎn)設(shè)置的延時(shí)，并且，當(dāng)某節(jié)點(diǎn)發(fā)生故障，故障節(jié)點(diǎn)可以單獨(dú)恢復(fù)而不影響其他節(jié)點(diǎn)。

從檢查點(diǎn)結(jié)構(gòu)的角度進(jìn)行檢查點(diǎn)周期優(yōu)化的研究才剛剛起步。Jin等[8]使用數(shù)值逼近方法對非協(xié)同檢查點(diǎn)的周期優(yōu)化進(jìn)行了研究，但是忽略了消息日志機(jī)制對檢查點(diǎn)讀取速度的積極影響。Zheng等[9]從故障感知的角度對非協(xié)同檢查點(diǎn)周期優(yōu)化作出了研究，其研究內(nèi)容沒有考慮消息日志對檢查點(diǎn)文件大小的影響。Wang等[10]使用馬爾可夫鏈對協(xié)同檢查點(diǎn)周期優(yōu)化進(jìn)行了研究，卻沒有研究檢查點(diǎn)存儲給系統(tǒng)帶來的性能抖動。

2 分層檢查點(diǎn)近似最優(yōu)周期計(jì)算模型

2.1 檢查點(diǎn)成本模型

在HPC系統(tǒng)中，一個使用分層檢查點(diǎn)的應(yīng)用程序的執(zhí)行過程可以用以下定義描述。

定義1 一個應(yīng)用程序的執(zhí)行過程是一個5元組{TIMEbase,μ,T,Delay,LOST},其中，T、Delay都是有窮集合，并且

1)TIMEbase是應(yīng)用程序的規(guī)模，即應(yīng)用程序無開銷(不設(shè)置檢查點(diǎn)、無故障)的基礎(chǔ)運(yùn)行時(shí)間。

2)μ是運(yùn)行平臺的平均無故障時(shí)間。

3)T是檢查點(diǎn)周期。

4)Delay是檢查點(diǎn)延遲的集合，Delay={Delay1,Delay2,…,DelayN}。其中：N是設(shè)置檢查點(diǎn)的次數(shù)，Delayi是存儲檢查點(diǎn)而消耗的時(shí)間，1≤i≤N。

5)LOST是故障損失時(shí)間，LOST={LOST1,LOST2,…,LOSTM}，其中，M是故障發(fā)生次數(shù)。特別的，LOSTi=Fi+Di+Ri，F(xiàn)i是故障發(fā)生到最近檢查點(diǎn)的任務(wù)丟失時(shí)間，Di是故障后停機(jī)時(shí)間，Ri是恢復(fù)花費(fèi)的時(shí)間，0≤i≤M。

根據(jù)上述定義，可以發(fā)現(xiàn)一個應(yīng)用程序在HPC系統(tǒng)中的執(zhí)行時(shí)間除了與其規(guī)模相關(guān)之外，還與檢查點(diǎn)延遲和故障損失時(shí)間相關(guān)。因此可以得到一個通用HPC系統(tǒng)環(huán)境下、使用分層檢查點(diǎn)的應(yīng)用程序的運(yùn)行時(shí)間如式(1)：

(1)

為了研究方便，不妨設(shè)C=E(Delayi)為檢查點(diǎn)延遲的數(shù)學(xué)期望，則N≈TIMEbase/(T-C)。設(shè)Tlost為故障損失的數(shù)學(xué)期望，本文考慮任意時(shí)刻內(nèi)發(fā)生故障的概率是相同的，因此Tlost=E(LOSTi)=T/2+D+R。將上述等式代入式(1)可得式(2)：

TIME=TIMEbase+TIMEbase/(T-C)×C+M(T/2+D+R)

(2)

根據(jù)式(2)可以發(fā)現(xiàn)，檢查點(diǎn)延遲和故障損失是對立的，當(dāng)周期T增大則故障損失增大；當(dāng)周期T減小則檢查點(diǎn)延遲增大。因此，這里定義一個概念“檢查點(diǎn)成本”。

定義2 檢查點(diǎn)成本表示為規(guī)模為TIMEbase、檢查點(diǎn)周期為T的應(yīng)用程序?yàn)榱双@得容錯能力在執(zhí)行時(shí)間方面增加的成本，即檢查點(diǎn)延遲、故障損失在運(yùn)行時(shí)間期望中占的比值。

根據(jù)定義2，可以得到式(3)。結(jié)合式(1)可以得到式(4)：

COST(T)=(TIME(T)-TIMEbase)/TIME(T)

(3)

COST(T)=COSTDelay(T)+COSTFault(T)-COSTDelay(T)COSTFault(T)

(4) 其中：COSTDelay(T)表示由檢查點(diǎn)延遲增加的成本，COSTFault(T)表示由故障損失增加的成本。

在長度為T的周期內(nèi)到達(dá)的故障數(shù)量可以抽象成一個參數(shù)是β=T/μ的泊松過程。為了確保每個周期只發(fā)生一個故障，本文給出一個約束條件使π≤0.03。因此，給出一個校正參數(shù)η使得T≤ημ。通過觀察式(4)可以周期優(yōu)化問題被抽象成了一個周期為[C,ημ]的非線性優(yōu)化，且經(jīng)計(jì)算可得η=0.27。

2.2 檢查點(diǎn)成本模型優(yōu)化

根據(jù)2.1節(jié)抽象出的非線性模型，本節(jié)針對分層檢查點(diǎn)來進(jìn)行模型優(yōu)化?？紤]一個在分布式并行環(huán)境下、緊耦合的應(yīng)用程序。假設(shè)有G組進(jìn)程，每組進(jìn)程擁有q個處理器，且各組檢查點(diǎn)在一個周期內(nèi)順序設(shè)置檢查點(diǎn)。其中，設(shè)D(q)和R(q)分別為停機(jī)時(shí)間和恢復(fù)時(shí)間。

2.2.1 故障位置對故障損失時(shí)間的影響

由于檢查點(diǎn)需要被保存到穩(wěn)定的存儲器中，則檢查點(diǎn)在存儲階段給應(yīng)用程序的執(zhí)行帶來了延遲。本文引入?yún)?shù)α來表示這種影響，0≤α≤1。因此，一個檢查點(diǎn)周期內(nèi)應(yīng)用程序的有效工作量如式(5)所示：

WORK=T-(1-α)C

(5)

如圖1所示，故障可能發(fā)生的位置被參數(shù)α分為了工作時(shí)間和減速工作時(shí)間。其中，當(dāng)故障發(fā)生在減速工作時(shí)間的時(shí)候，本文以進(jìn)程組Gg的視角來看故障發(fā)生的位置有三種情況：組Gg設(shè)置檢查點(diǎn)之前，組Gg設(shè)置檢查點(diǎn)期間與組Gg設(shè)置檢查點(diǎn)之后。

圖1 分層檢查點(diǎn)可能故障位置

根據(jù)圖1可以得到任務(wù)丟失時(shí)間F=Tlost+Tslow，工作時(shí)間和減速工作時(shí)間的Fw和Fs分別如式(6)和式(7)所示：

式(6)中第一項(xiàng)表示故障發(fā)生在工作時(shí)間內(nèi)Fw的概率。由于分層檢查點(diǎn)組間相互獨(dú)立且順序設(shè)置檢查點(diǎn)，所以只需要重新執(zhí)行組Gg和其后所有分組丟失的工作。因此，故障發(fā)生在工作時(shí)間的概率為(T-GC(q))/2，Tlost的數(shù)學(xué)期望為(T-GC(q))/2，Tslow的數(shù)學(xué)期望為(G-g+1)αC(q)，其中1≤g≤G。

式(7)中第一項(xiàng)表示故障發(fā)生在減速工作時(shí)間內(nèi)Fs的概率。設(shè)當(dāng)故障發(fā)生時(shí)已經(jīng)有s組進(jìn)程完成了檢查點(diǎn)設(shè)置，即故障發(fā)生在s+1組且s+1正在設(shè)置檢查點(diǎn)，其中0≤s≤g-1。圖1中減速工作時(shí)間內(nèi)三種可能故障位置Tlost和Tslow的數(shù)學(xué)期望如式(6)中大括號中每項(xiàng)所示。

結(jié)合式(5)～(7)，可以得到一個分層檢查點(diǎn)成本公式(8)：

(8)

2.2.2 消息日志對檢查點(diǎn)成本的影響因子

分層檢查點(diǎn)協(xié)議在組間使用了非協(xié)調(diào)檢查點(diǎn)，其中的消息日志機(jī)制分別對程序的執(zhí)行、重執(zhí)行時(shí)間與檢查點(diǎn)文件的大小造成了影響，從而影響了本文對檢查點(diǎn)周期的優(yōu)化。為了更精確地計(jì)算檢查點(diǎn)周期，將引入三個新的參數(shù)來表示這種影響。

在進(jìn)程被分成若干組的條件下，組間的事件日志必須存儲在可靠的存儲器中，這樣才能在故障之后獨(dú)立恢復(fù)指定組。然而存儲事件日志為應(yīng)用程序帶來了額外開銷，使用一個減速因子λ來表示這種影響，0<λ<1，典型的λ≈0.98[12]。相反，消息日志對故障之后的恢復(fù)有積極影響。因?yàn)榻M內(nèi)消息存儲在本地內(nèi)存并在恢復(fù)的時(shí)候可以直接訪問。因此，本文模型引入一個加速因子ρ,其中ρ的典型區(qū)間為[1,2][13]。由上述兩個影響因子的典型值區(qū)間可以看出，消息日志的有效載荷開銷只占一個很小的百分比，對某些應(yīng)用則可以縮短一半的恢復(fù)時(shí)間。

除此之外，由于組內(nèi)消息被不斷記錄，消息日志機(jī)制同時(shí)也影響了檢查點(diǎn)文件的大小，進(jìn)而影響了分層檢查點(diǎn)的檢查點(diǎn)延遲。為了表示由于檢查點(diǎn)文件增大對應(yīng)用程序執(zhí)行造成的影響，引入一個減速因子β,則C(q)=C0(q)(1+βλWORK)。其中β的計(jì)算公式隨著應(yīng)用程序的變化而變化。例如在一個二維三階的模板計(jì)算中β=(2sp)/(9b3)，其中sp是處理器的速度，b是模板計(jì)算中每個處理器計(jì)算矩陣的大小?？梢缘玫揭粋€優(yōu)化后的檢查點(diǎn)式(9)：

(9)

3 仿真實(shí)驗(yàn)

3.1 仿真環(huán)境

仿真實(shí)驗(yàn)環(huán)境由4臺計(jì)算機(jī)組成一個分布式集群環(huán)境，計(jì)算機(jī)配置均為：IntelE4500CPU，2GB內(nèi)存，500GB硬盤。并行應(yīng)用程序使用了NASParallelBenchmarks中的二維模板計(jì)算程序MG，同時(shí)使用Guermouche等[11]提出的HydEE作為分層檢查點(diǎn)協(xié)議具體實(shí)現(xiàn)。故障注入程序的故障分布服Weibull分布，同時(shí)，相同節(jié)點(diǎn)在一個檢查點(diǎn)周期內(nèi)產(chǎn)生故障重疊概率不超過3%，即η=0.27，其參數(shù)如表1所示。本文仿真環(huán)境下的具體參數(shù)如表2所示。其中，λ和ρ的值分別參考文獻(xiàn)[12]和文獻(xiàn)[13]。根據(jù)仿真環(huán)境結(jié)合式(8)計(jì)算可得不同平均無故障時(shí)間(MeanTimeBeforeFault,MTBF)條件下理論最優(yōu)檢查點(diǎn)與檢查點(diǎn)成本如表3所示。

表1 故障注入程序參數(shù)

表2 仿真環(huán)境參數(shù)

表3 理論最優(yōu)檢查點(diǎn)周期與成本

根據(jù)上文約束C≤T≤ημ，設(shè)應(yīng)用程序的檢查點(diǎn)周期分別在[0.82,32.4]和[0.82,64.8]兩個區(qū)間中均勻分布。首先，在兩種情況下運(yùn)行程序MG，記錄每個周期程序MG正常運(yùn)行完成的時(shí)間并計(jì)算檢查點(diǎn)成本COST，結(jié)果如圖2所示。其次，擬合實(shí)驗(yàn)結(jié)果曲線，與本文方法、文獻(xiàn)[6]提出的模型進(jìn)行對比，結(jié)果如圖3～4所示。

3.2 仿真結(jié)果分析

由圖2中點(diǎn)的分布可知，圖2(a)中周期T=9.2時(shí)檢查點(diǎn)成本最COST小為9.9%；圖2(b)中，周期T=14.6時(shí)檢查點(diǎn)成本最COST小為7.1%。在遠(yuǎn)離理論周期時(shí)，COST呈上升趨勢。呈現(xiàn)上述分布規(guī)律的原因是:當(dāng)周期T較小時(shí)，檢查點(diǎn)周期內(nèi)有效工作較少、檢查點(diǎn)延遲較高。特別的，當(dāng)周期T的值接近C時(shí)，應(yīng)用程序幾乎無法運(yùn)行。當(dāng)周期T較大時(shí)，應(yīng)用程序在單個周期T內(nèi)有效工作時(shí)間變長，故障概率增大，故障損失增大。除此之外，在大于理論周期值時(shí)，圖2呈現(xiàn)出明顯的斜率不同，其原因是因?yàn)殡S著MTBF值的減小，單位時(shí)間內(nèi)故障概率會增加，則故障損失的數(shù)學(xué)期望會變大。

圖2 不同周期的檢查點(diǎn)成本

由圖3(a)和圖4(a)的中的曲線可知，在仿真分布式環(huán)境、不同MTBF情況下，本文提出的周期計(jì)算模型更加符合實(shí)際情況。由圖3(b)和圖4(b)中的折線可知，本文提出的周期計(jì)算模型與實(shí)際運(yùn)行情況的檢查點(diǎn)成本誤差在3%～5%變化，且MTBF較大情況下平均誤差較?。欢墨I(xiàn)[6]提出的檢查點(diǎn)周期檢查點(diǎn)成本誤差較大，在1%～50%變化。其中，圖中橫坐標(biāo)為檢查點(diǎn)周期，縱坐標(biāo)為檢查點(diǎn)成本誤差。特別的，當(dāng)文獻(xiàn)[6]的優(yōu)化模型在其最優(yōu)檢查點(diǎn)周期附近可以較好地計(jì)算檢查點(diǎn)成本，但是在周期超過其理論最優(yōu)值之后檢查點(diǎn)成本快速升高，并且在MTBF較大的情況下升高速度更快。文獻(xiàn)[6]的主要優(yōu)點(diǎn)在于采用了馬爾可夫鏈對分布式環(huán)境的檢查點(diǎn)周期進(jìn)行優(yōu)化，較好地模擬了分布式環(huán)境中程序運(yùn)行狀態(tài)的轉(zhuǎn)移；其主要缺點(diǎn)在于關(guān)注HPC系統(tǒng)結(jié)構(gòu)的同時(shí)忽略了檢查點(diǎn)協(xié)議對檢查點(diǎn)成本的影響，將故障損失時(shí)間均攤至檢查點(diǎn)延遲上，故而出現(xiàn)了圖3(b)和圖4(b)中高誤差的現(xiàn)象。

根據(jù)仿真結(jié)果可以得出以下結(jié)論：1)本文提出的檢查點(diǎn)周期計(jì)算模型與理論近似最優(yōu)檢查點(diǎn)成本平均誤差在5%以下，相對文獻(xiàn)[6]所提方法的平均誤差降低了20%；2)檢查點(diǎn)結(jié)構(gòu)對檢查點(diǎn)成本影響非常大，針對檢查點(diǎn)結(jié)構(gòu)對檢查點(diǎn)周期進(jìn)行優(yōu)化可以得到更精確的結(jié)果。

圖3 μ=120 s時(shí)的兩種算法對比結(jié)果

圖4 μ=240 s時(shí)的兩種算法對比結(jié)果

4 結(jié)語

針對提升檢查點(diǎn)效率的問題，本文對檢查點(diǎn)的周期優(yōu)化的問題進(jìn)行了研究，通過分析可能故障位置與消息日志對檢查點(diǎn)成本造成的影響，提出了一種面向分層檢查點(diǎn)的周期計(jì)算模型。仿真實(shí)驗(yàn)結(jié)果顯示，本文提出的檢查點(diǎn)周期計(jì)算模型與理論近似最優(yōu)檢查點(diǎn)成本平均誤差在5%以下，相對傳統(tǒng)檢查點(diǎn)周期優(yōu)化模型的平均誤差降低了20%。目前混合容錯技術(shù)越來越流行，故障預(yù)測與復(fù)制技術(shù)經(jīng)常與檢查點(diǎn)技術(shù)一起使用，下一步工作將嘗試對結(jié)合故障預(yù)測及復(fù)制技術(shù)的檢查點(diǎn)周期進(jìn)行優(yōu)化。

References)

[1] DONGARRA J, BECKMAN P, MOORE T, et al.The international exascale software project roadmap [J].International Journal of High Performance Computing Applications, 2011, 25(1): 3-60.

[2] SCHROEDER B, GIBSON G A.A large-scale study of failures in high-performance computing systems [J].IEEE Transactions on Dependable and Secure Computing, 2010, 7(4): 337-350.

[3] YOUNG J W.A first order approximation to the optimum checkpoint interval [J].Communications of the ACM, 1974, 17(9): 530-531.

[4] DALY J T.A higher order estimate of the optimum checkpoint interval for restart dumps [J].Future Generation Computer Systems, 2006, 22(3): 303-312.

[5] 鄢喜愛,楊金民,田華.雙機(jī)容錯系統(tǒng)中最佳檢查點(diǎn)間隔的分析[J].計(jì)算機(jī)工程,2007,33(5):283-285.(YAN X A, YANG J M, TIAN H.Analysis of best checkpoint interval of duplicated fault tolerance system [J].Computer Engineering, 2007, 33(5): 283-285.)

[6] GE Y, YANG Y, ZHU C.Study of the best checkpoint interval in the distributed simulation system based on virtualization technology [C]// AMCCE 2015: Proceedings of 2015 International Conference on Automation, Mechanical Control and Computational Engineering.Amsterdam: Atlantis Press, 2015: 193-197.

[7] 黃瓊,尚利宏,周密,等.一種面向大規(guī)模并行系統(tǒng)的分組協(xié)同檢查點(diǎn)算法[J].計(jì)算機(jī)研究與發(fā)展,2010,47(S1):158-163.(HUANG Q, SHANG L H, ZHOU M, et al.A group-based coordinated checkpointing algorithm for large-scale parallel system [J].Journal of Computer Research and Development, 2010, 47(S1): 158-163.)

[8] JIN H, CHEN Y, ZHU H, et al.Optimizing HPC fault-tolerant environment: An analytical approach [C]// ICPP 2010: Proceedings of the 2010 39th International Conference on Parallel Processing.Piscataway, NJ: IEEE, 2010: 525-534.

[9] ZHENG Z, LAN Z.Reliability-aware scalability models for high performance computing [C]// CLUSTER’ 09: Proceedings of 2009 IEEE International Conference on Cluster Computing and Workshops.Piscataway, NJ: IEEE, 2009: 1-9.

[10] WANG L, PATTABIRAMAN K, KALBARCZYK Z, et al.Modeling coordinated checkpointing for large-scale supercomputers [C]// DSN 2005: Proceedings of the 2005 International Conference on Dependable Systems and Networks.Piscataway, NJ: IEEE, 2005: 812-821.

[11] GUERMOUCHE A, ROPARS T, SNIR M, et al.HydEE: failure containment without event logging for large scale send-deterministic mpi applications [C]// IPDPS 2012: Proceedings of 2012 IEEE 26th International Conference on Parallel & Distributed Processing Symposium.Piscataway, NJ: IEEE, 2012: 1216-1227.

[12] BOUTEILLER A, HERAULT T, BOSILCA G, et al.Correlated set coordination in fault tolerant message logging protocols [C]// Euro-Par’ 11: Proceedings of the 17th International Conference on Parallel Processing.Berlin: Springer, 2011: 51-64.

[13] BOUTEILLER A, BOSILCA G, DONGARRA J.Redesigning the message logging model for high performance [J].Concurrency and Computation: Practice and Experience, 2010, 22(16): 2196-2211.

This work is partially supported by National Natural Science Foundation of China (61370212, 61402127, 61502118), the Natural Science Foundation of Heilongjiang Province (F2015029).

LYU Hongwu, born in 1983, Ph.D., lecturer.His research interests include availability, performance evaluation, cloud computation.

GU Lei, born in 1991, M.S.candidate.His research interests include high availability system, network security.

WANG Huiqiang, born in 1960, Ph.D., professor.His research interests include network security, future network.

ZOU Shichen, born in 1988, Ph.D.candidate.His research interests include trust guarantee, trust management.

FENG Guangsheng, born in 1980, Ph.D., lecturer.His research interests include network security, cognitive network.

Quasi-optimal period computation model for hierarchical checkpoint protocol

LYU Hongwu, GU Lei*, WANG Huiqiang, ZOU Shichen, FENG Guangsheng

(CollegeofComputerScienceandTechnology,HarbinEngineeringUniversity,HarbinHeilongjiang150001,China)

With the increase of High Performance Computation (HPC) system scale, it’s very important to increase the efficiency of the checkpoint.A model to compute the quasi-optimal period for hierarchical checkpoint protocol was proposed.First, the execution of an application in HPC system was assessed, and checkpoint period optimization problem was abstracted as the nonlinear checkpoint cost model.Second, the hierarchical checkpoint cost formula was derived by simulating the possible fault location; two deceleration parameters and an acceleration parameter were introduced to reflect the impact of message logging on the hierarchical checkpoint.The simulation results show that, compared with the quasi-optimal period checkpoint cost, the average error value of the proposed model is below 5%, which is 20% less than that of the traditional model based on Markov chain.The proposed model can signally increase the efficiency of the hierarchical checkpoint protocol; meanwhile enhance the availability of the HPC system.

High Performance Computation (HPC); fault tolerance; hierarchical checkpoint; checkpoint period; quasi-optimal solution

2016-07-20;

2016-08-05。

國家自然科學(xué)基金資助項(xiàng)目(61370212， 61402127， 61502118)；黑龍江省自然科學(xué)基金資助項(xiàng)目(F2015029)。

呂宏武(1983—)，男，山東日照人，講師，博士，CCF會員，主要研究方向：可用性、性能評價(jià)、云計(jì)算； 谷雷(1991—)，男，河南安陽人，碩士研究生，主要研究方向：高可用系統(tǒng)、網(wǎng)絡(luò)安全； 王慧強(qiáng)(1960—)，男，黑龍江哈爾濱人，教授，博士，CCF會員，主要研究方向：網(wǎng)絡(luò)安全、未來網(wǎng)絡(luò)； 鄒世辰(1988—)，男，黑龍江哈爾濱人，博士研究生，CCF會員，主要研究方向：可信性保障、信任管理； 馮光升(1980—)，男，山東禹城人，講師，博士，CCF會員，主要研究方向：網(wǎng)絡(luò)安全、認(rèn)知網(wǎng)絡(luò)。

1001-9081(2017)01-0103-05

10.11772/j.issn.1001-9081.2017.01.0103

TP399; TP302

A