呂宏武，谷 雷，王慧強(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)

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

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

0 引言

隨著大規(guī)模和超大規(guī)模集成電路的問(wèn)世，高性能計(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ù)會(huì)持續(xù)發(fā)展。然而在實(shí)際部署與運(yùn)行中人們發(fā)現(xiàn)，系統(tǒng)的高復(fù)雜性、高異構(gòu)性導(dǎo)致HPC系統(tǒng)時(shí)刻面臨著錯(cuò)誤、故障和失效對(duì)于系統(tǒng)可用性保障上的挑戰(zhàn)。Schroeder等[2]收集了兩個(gè)世界級(jí)的高性能計(jì)算平臺(tái)的故障數(shù)據(jù)，研究發(fā)現(xiàn)兩個(gè)高性能計(jì)算平臺(tái)每年的故障率在20～2 000次即平均8.7 h就會(huì)發(fā)生一次故障，且故障率與系統(tǒng)規(guī)模呈正比。由此可見(jiàn)容錯(cuò)技術(shù)對(duì)于HPC系統(tǒng)變得越來(lái)越重要。

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

然而隨著HPC系統(tǒng)結(jié)構(gòu)變得越來(lái)越復(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)對(duì)檢查點(diǎn)性能的影響。HPC系統(tǒng)在實(shí)際工作中會(huì)受到許多外因諸如電壓、環(huán)境溫度的影響而產(chǎn)生系統(tǒng)性能抖動(dòng)，這種性能抖動(dòng)非常小，在理論研究過(guò)程中一般會(huì)忽略這種抖動(dòng)而認(rèn)為系統(tǒng)性能是穩(wěn)定的，因此目前所有的檢查點(diǎn)周期優(yōu)化模型都是一種次優(yōu)模型，即近似最優(yōu)。本文首先將檢查點(diǎn)周期優(yōu)化抽象為一個(gè)非線性的檢查點(diǎn)成本模型；然后通過(guò)分析分層檢查點(diǎn)結(jié)構(gòu)的特點(diǎn)，根據(jù)該模型對(duì)分層檢查點(diǎn)的近似最優(yōu)周期進(jìn)行計(jì)算；最后通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了本文所提模型的有效性。

1 相關(guān)工作

檢查點(diǎn)技術(shù)核心思想是將程序的最近運(yùn)行狀態(tài)保存至檢查點(diǎn)內(nèi)，并在故障發(fā)生時(shí)通過(guò)讀取檢查點(diǎn)使程序恢復(fù)至最近正常狀態(tài)。因此，檢查點(diǎn)技術(shù)的關(guān)鍵是要保證程序進(jìn)程狀態(tài)的一致性。不同檢查點(diǎn)協(xié)議使用了不同的機(jī)制來(lái)保證進(jìn)程狀態(tài)的一致性，然而正是這些機(jī)制導(dǎo)致了檢查點(diǎn)技術(shù)在大規(guī)模HPC系統(tǒng)中出現(xiàn)性能降級(jí)。經(jīng)過(guò)檢查點(diǎn)技術(shù)的多年發(fā)展，目前有三類(lèi)非常成熟的檢查點(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ì)算工作，不會(huì)因?yàn)檫M(jìn)程阻塞浪費(fèi)執(zhí)行時(shí)間，減少了同一時(shí)刻參與存儲(chǔ)的進(jìn)程的數(shù)目，從而增加每個(gè)參與進(jìn)程的存儲(chǔ)帶寬，這樣就減少了每個(gè)進(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ù)值逼近方法對(duì)非協(xié)同檢查點(diǎn)的周期優(yōu)化進(jìn)行了研究，但是忽略了消息日志機(jī)制對(duì)檢查點(diǎn)讀取速度的積極影響。Zheng等[9]從故障感知的角度對(duì)非協(xié)同檢查點(diǎn)周期優(yōu)化作出了研究，其研究?jī)?nèi)容沒(méi)有考慮消息日志對(duì)檢查點(diǎn)文件大小的影響。Wang等[10]使用馬爾可夫鏈對(duì)協(xié)同檢查點(diǎn)周期優(yōu)化進(jìn)行了研究，卻沒(méi)有研究檢查點(diǎn)存儲(chǔ)給系統(tǒng)帶來(lái)的性能抖動(dòng)。

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

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

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

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

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

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

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

4)Delay是檢查點(diǎn)延遲的集合，Delay={Delay1,Delay2,…,DelayN}。其中：N是設(shè)置檢查點(diǎn)的次數(shù)，Delayi是存儲(chǔ)檢查點(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)一個(gè)應(yīng)用程序在HPC系統(tǒng)中的執(zhí)行時(shí)間除了與其規(guī)模相關(guān)之外，還與檢查點(diǎn)延遲和故障損失時(shí)間相關(guān)。因此可以得到一個(gè)通用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)延遲和故障損失是對(duì)立的，當(dāng)周期T增大則故障損失增大；當(dāng)周期T減小則檢查點(diǎn)延遲增大。因此，這里定義一個(gè)概念“檢查點(diǎn)成本”。

定義2 檢查點(diǎn)成本表示為規(guī)模為T(mén)IMEbase、檢查點(diǎn)周期為T(mén)的應(yīng)用程序?yàn)榱双@得容錯(cuò)能力在執(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)表示由故障損失增加的成本。

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

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

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

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

由于檢查點(diǎn)需要被保存到穩(wěn)定的存儲(chǔ)器中，則檢查點(diǎn)在存儲(chǔ)階段給應(yīng)用程序的執(zhí)行帶來(lái)了延遲。本文引入?yún)?shù)α來(lái)表示這種影響，0≤α≤1。因此，一個(gè)檢查點(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的視角來(lái)看故障發(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)中大括號(hào)中每項(xiàng)所示。

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

(8)

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

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

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

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

(9)

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

3.1 仿真環(huán)境

仿真實(shí)驗(yàn)環(huán)境由4臺(tái)計(jì)算機(jī)組成一個(gè)分布式集群環(huán)境，計(jì)算機(jī)配置均為：IntelE4500CPU，2GB內(nèi)存，500GB硬盤(pán)。并行應(yīng)用程序使用了NASParallelBenchmarks中的二維模板計(jì)算程序MG，同時(shí)使用Guermouche等[11]提出的HydEE作為分層檢查點(diǎn)協(xié)議具體實(shí)現(xiàn)。故障注入程序的故障分布服Weibull分布，同時(shí)，相同節(jié)點(diǎn)在一個(gè)檢查點(diǎn)周期內(nèi)產(chǎn)生故障重疊概率不超過(guò)3%，即η=0.27，其參數(shù)如表1所示。本文仿真環(huán)境下的具體參數(shù)如表2所示。其中，λ和ρ的值分別參考文獻(xiàn)[12]和文獻(xiàn)[13]。根據(jù)仿真環(huán)境結(jié)合式(8)計(jì)算可得不同平均無(wú)故障時(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]兩個(gè)區(qū)間中均勻分布。首先，在兩種情況下運(yùn)行程序MG，記錄每個(gè)周期程序MG正常運(yùn)行完成的時(shí)間并計(jì)算檢查點(diǎn)成本COST，結(jié)果如圖2所示。其次，擬合實(shí)驗(yàn)結(jié)果曲線，與本文方法、文獻(xiàn)[6]提出的模型進(jìn)行對(duì)比，結(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呈上升趨勢(shì)。呈現(xiàn)上述分布規(guī)律的原因是:當(dāng)周期T較小時(shí)，檢查點(diǎn)周期內(nèi)有效工作較少、檢查點(diǎn)延遲較高。特別的，當(dāng)周期T的值接近C時(shí)，應(yīng)用程序幾乎無(wú)法運(yùn)行。當(dāng)周期T較大時(shí)，應(yīng)用程序在單個(gè)周期T內(nèi)有效工作時(shí)間變長(zhǎng)，故障概率增大，故障損失增大。除此之外，在大于理論周期值時(shí)，圖2呈現(xiàn)出明顯的斜率不同，其原因是因?yàn)殡S著MTBF值的減小，單位時(shí)間內(nèi)故障概率會(huì)增加，則故障損失的數(shù)學(xué)期望會(huì)變大。

圖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較大情況下平均誤差較小；而文獻(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)成本，但是在周期超過(guò)其理論最優(yōu)值之后檢查點(diǎn)成本快速升高，并且在MTBF較大的情況下升高速度更快。文獻(xiàn)[6]的主要優(yōu)點(diǎn)在于采用了馬爾可夫鏈對(duì)分布式環(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é)議對(duì)檢查點(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%以下，相對(duì)文獻(xiàn)[6]所提方法的平均誤差降低了20%；2)檢查點(diǎn)結(jié)構(gòu)對(duì)檢查點(diǎn)成本影響非常大，針對(duì)檢查點(diǎn)結(jié)構(gòu)對(duì)檢查點(diǎn)周期進(jìn)行優(yōu)化可以得到更精確的結(jié)果。

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

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

4 結(jié)語(yǔ)

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

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

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