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

呂宏武，谷 雷，王慧強，鄒世辰，馮光升

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

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

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

呂宏武，谷 雷*，王慧強，鄒世辰，馮光升

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

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

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

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

0 引言

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

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

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

1 相關(guān)工作

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

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

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

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

2.1 檢查點成本模型

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

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

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

2)μ是運行平臺的平均無故障時間。

3)T是檢查點周期。

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

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

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

(1)

為了研究方便，不妨設(shè)C=E(Delayi)為檢查點延遲的數(shù)學(xué)期望，則N≈TIMEbase/(T-C)。設(shè)Tlost為故障損失的數(shù)學(xué)期望，本文考慮任意時刻內(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)，檢查點延遲和故障損失是對立的，當(dāng)周期T增大則故障損失增大；當(dāng)周期T減小則檢查點延遲增大。因此，這里定義一個概念“檢查點成本”。

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

根據(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)表示由檢查點延遲增加的成本，COSTFault(T)表示由故障損失增加的成本。

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

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

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

2.2.1 故障位置對故障損失時間的影響

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

WORK=T-(1-α)C

(5)

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

圖1 分層檢查點可能故障位置

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

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

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

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

(8)

2.2.2 消息日志對檢查點成本的影響因子

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

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

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

(9)

3 仿真實驗

3.1 仿真環(huán)境

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

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

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

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

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

3.2 仿真結(jié)果分析

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

圖2 不同周期的檢查點成本

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

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

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

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

4 結(jié)語

針對提升檢查點效率的問題，本文對檢查點的周期優(yōu)化的問題進(jìn)行了研究，通過分析可能故障位置與消息日志對檢查點成本造成的影響，提出了一種面向分層檢查點的周期計算模型。仿真實驗結(jié)果顯示，本文提出的檢查點周期計算模型與理論近似最優(yōu)檢查點成本平均誤差在5%以下，相對傳統(tǒng)檢查點周期優(yōu)化模型的平均誤差降低了20%。目前混合容錯技術(shù)越來越流行，故障預(yù)測與復(fù)制技術(shù)經(jīng)常與檢查點技術(shù)一起使用，下一步工作將嘗試對結(jié)合故障預(yù)測及復(fù)制技術(shù)的檢查點周期進(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] 鄢喜愛,楊金民,田華.雙機容錯系統(tǒng)中最佳檢查點間隔的分析[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é)同檢查點算法[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é)基金資助項目(61370212， 61402127， 61502118)；黑龍江省自然科學(xué)基金資助項目(F2015029)。

呂宏武(1983—)，男，山東日照人，講師，博士，CCF會員，主要研究方向：可用性、性能評價、云計算； 谷雷(1991—)，男，河南安陽人，碩士研究生，主要研究方向：高可用系統(tǒng)、網(wǎng)絡(luò)安全； 王慧強(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