高瑋軍，張春霞，楊 杰，師 陽(yáng)

蘭州理工大學(xué) 計(jì)算機(jī)與通信學(xué)院，蘭州 730050

1 引言

科學(xué)工作流為科學(xué)研究提供了一種流程定義和自動(dòng)運(yùn)行的平臺(tái)，可以屏蔽底層繁瑣的計(jì)算過(guò)程以此簡(jiǎn)化科學(xué)實(shí)驗(yàn)?？蒲腥藛T只需關(guān)注專業(yè)問(wèn)題的處理，從而使得科學(xué)實(shí)驗(yàn)?zāi)軌蚋憬?、高效地進(jìn)行。在科學(xué)研究領(lǐng)域，例如：生物基因?qū)W、天文學(xué)、物理學(xué)、地震學(xué)等大規(guī)模應(yīng)用中，工作流包含許多細(xì)粒度計(jì)算任務(wù)，任務(wù)間存在復(fù)雜的依賴關(guān)系。這些任務(wù)通常只需要幾秒鐘或幾分鐘的執(zhí)行時(shí)間，任務(wù)實(shí)際執(zhí)行時(shí)間可能比系統(tǒng)開(kāi)銷（系統(tǒng)中除執(zhí)行用戶計(jì)算以外的其他開(kāi)銷）更短[1]。系統(tǒng)開(kāi)銷是分布式計(jì)算中普遍存在的問(wèn)題，也是科學(xué)工作流應(yīng)用程序的性能可以顯著提升的主要原因[2]。隨著網(wǎng)格計(jì)算、云計(jì)算等分布式環(huán)境的出現(xiàn)和硬件設(shè)備的優(yōu)化，系統(tǒng)開(kāi)銷問(wèn)題更加凸顯，嚴(yán)重影響了科學(xué)工作流的執(zhí)行效率。

任務(wù)聚類方法對(duì)具有某一特征的任務(wù)進(jìn)行聚集生成聚類，系統(tǒng)以類為單位進(jìn)行調(diào)度。該方法雖然增加了作業(yè)運(yùn)行耗時(shí)，但是顯著地降低了系統(tǒng)的總開(kāi)銷[3]。文獻(xiàn)[4]結(jié)合計(jì)算任務(wù)劃分技術(shù)與任務(wù)聚類，解決了數(shù)據(jù)密集型地震模擬工作流（CyberShake）在求解時(shí)間方面所面臨的問(wèn)題。細(xì)粒度任務(wù)的低性能問(wèn)題在廣泛使用的分布式平臺(tái)中更加凸顯，其中資源的調(diào)度開(kāi)銷和隊(duì)列等待占用的時(shí)間較長(zhǎng)。文獻(xiàn)[5]為了減少工作流的總運(yùn)行時(shí)間和云資源使用，提出了一種基于任務(wù)分組和復(fù)制技術(shù)的調(diào)度算法，來(lái)降低用戶執(zhí)行成本。針對(duì)跨地域跨學(xué)科的科學(xué)研究工作中，普遍存在數(shù)據(jù)傳輸開(kāi)銷嚴(yán)重影響系統(tǒng)運(yùn)行效率的問(wèn)題，任務(wù)聚類方法被用于數(shù)據(jù)放置策略和資源調(diào)度策略中[6]，以減少數(shù)據(jù)傳輸所產(chǎn)生的時(shí)間開(kāi)銷。科學(xué)工作流執(zhí)行過(guò)程中存在故障風(fēng)險(xiǎn)，而大部分任務(wù)聚類算法及其優(yōu)化算法并未考慮故障對(duì)系統(tǒng)的影響。

在任務(wù)聚類算法執(zhí)行后，工作流系統(tǒng)以類為基本單位進(jìn)行調(diào)度和執(zhí)行，類中有一個(gè)任務(wù)失敗，整個(gè)類被標(biāo)記為失敗。解決任務(wù)失敗問(wèn)題最常用的方法是重試失敗的作業(yè)、備份技術(shù)、設(shè)置檢查點(diǎn)[7-9]。對(duì)于運(yùn)行周期比較長(zhǎng)的作業(yè)，備份技術(shù)會(huì)造成嚴(yán)重的資源浪費(fèi)。為了減少資源浪費(fèi)，可以按周期檢查作業(yè)執(zhí)行情況，以限制重試的任務(wù)量。由于檢查點(diǎn)機(jī)制實(shí)現(xiàn)相對(duì)重試技術(shù)較為復(fù)雜，執(zhí)行檢查點(diǎn)的開(kāi)銷會(huì)同樣會(huì)限制系統(tǒng)的運(yùn)行效率。Chen等人[10]針對(duì)瞬時(shí)故障提問(wèn)題提出了任務(wù)/作業(yè)故障模型，并提出了動(dòng)態(tài)重聚類算法（DR）。隨后又提出了三種任務(wù)容錯(cuò)聚類方法，可以有效地解決任務(wù)失敗的問(wèn)題[11]。文獻(xiàn)[12]提出了一種新的基于簇的異構(gòu)最早完成時(shí)間（CHEFT）的啟發(fā)式算法，利用資源預(yù)配置后的空閑時(shí)間運(yùn)行已失敗的任務(wù)，來(lái)增強(qiáng)云環(huán)境中科學(xué)工作流的容錯(cuò)機(jī)制。文獻(xiàn)[13]對(duì)現(xiàn)有的云平臺(tái)容錯(cuò)機(jī)制進(jìn)行分析，對(duì)科學(xué)工作流應(yīng)用程序中出現(xiàn)的特定故障，討論和推薦解決故障的容錯(cuò)方法和容錯(cuò)模型?，F(xiàn)有的容錯(cuò)聚類算法忽略了聚類可能會(huì)導(dǎo)致負(fù)載不平衡問(wèn)題[14-15]，這種不平衡會(huì)導(dǎo)致下一層任務(wù)的釋放延遲，系統(tǒng)的總運(yùn)行時(shí)間也會(huì)隨之增加。

工作流分解是處理負(fù)載不平衡的常用技術(shù)[16-17]，該方法將科學(xué)工作流劃分成多個(gè)子工作流，子工作流可以高效地并行執(zhí)行。但是對(duì)工作流進(jìn)行分割會(huì)增加中間數(shù)據(jù)管理開(kāi)銷，同時(shí)，可以進(jìn)行分割的工作流種類也比較受限。文獻(xiàn)[18]提出了一種基于路徑平衡的費(fèi)用優(yōu)化算法，能夠有效地增大了費(fèi)用優(yōu)化空間。文獻(xiàn)[19]提出了三種衡量指標(biāo)來(lái)量化描述不平衡問(wèn)題，根據(jù)運(yùn)行時(shí)間不平衡、依賴關(guān)系不平衡、位置關(guān)系不平衡提出了三種平衡聚類算法，有效縮短了系統(tǒng)總運(yùn)行時(shí)間。

容錯(cuò)聚類算法在有效解決故障問(wèn)題的同時(shí)，也面臨著負(fù)載不平衡問(wèn)題，本文結(jié)合水平運(yùn)行時(shí)間平衡策略與現(xiàn)有的容錯(cuò)聚類算法，提出了一種平衡重聚類算法。通過(guò)平衡聚類的運(yùn)行時(shí)間以實(shí)現(xiàn)負(fù)載平衡，在提高系統(tǒng)運(yùn)行效率的同時(shí)保證系統(tǒng)的健壯性。

2 定義與基礎(chǔ)理論

2.1 動(dòng)態(tài)重聚類（DR）

負(fù)載不平衡：在不考慮任務(wù)運(yùn)行時(shí)間存在差異的情況下將科學(xué)工作流中多個(gè)任務(wù)合并為一個(gè)聚類，可能會(huì)導(dǎo)致聚類的之間的運(yùn)行時(shí)間差異較大，造成虛擬機(jī)運(yùn)行時(shí)間嚴(yán)重不平衡。

如圖1 所示，任務(wù) t 1，t2，t3 和 t 4 為相互獨(dú)立的任務(wù)，其中t1，t2，t3，t4 的任務(wù)運(yùn)行時(shí)間分別是10 s，10 s，30 s，30 s。

圖1 初始任務(wù)集

當(dāng)有兩個(gè)聚類時(shí)，水平聚類（HC）方法運(yùn)行結(jié)果如圖2 所示，將任務(wù)t1 和任務(wù)t2 合并為聚類J1，將任務(wù)t3和任務(wù)t4聚為J2。則聚類J1的運(yùn)行時(shí)間為20 s，聚類J2的運(yùn)行時(shí)間為60 s，聚類J1 和J2 的運(yùn)行時(shí)間嚴(yán)重不平衡。由于下一層任務(wù)釋放的必須等待上一層所有任務(wù)運(yùn)行完成，即在60 s后下一層的任務(wù)才可以釋放。

圖2 水平聚類

負(fù)載不平衡衡量指標(biāo)：本文采用水平運(yùn)行時(shí)間方差（Horizontal Runtime Variance，HRV）來(lái)描述運(yùn)行時(shí)間不平衡問(wèn)題。HRV描述了一組任務(wù)或作業(yè)運(yùn)行時(shí)間的差異大小，HRV定義如下：

HRV 表示在同一水平層中所有任務(wù)/聚類運(yùn)行時(shí)間的方差。公式中分子σ(tv)為所有任務(wù)/聚類運(yùn)行時(shí)間的標(biāo)準(zhǔn)差，μ(tv)為該層中任務(wù)/聚類運(yùn)行時(shí)間的平均值。在μ(tv)相同的情況下，σ(tv)的值越大，HRV 的值也越大。

初始任務(wù)集圖1中，μ(tv)=20 則：

由于科學(xué)工作流任務(wù)間存在依賴關(guān)系，下一層作業(yè)的釋放時(shí)間取決于上一層任務(wù)中最長(zhǎng)運(yùn)行時(shí)間。如圖2，HC算法運(yùn)行后，μ(tv)=40 得：

水平運(yùn)行時(shí)間平衡衡聚類（HRB）算法根據(jù)任務(wù)運(yùn)行時(shí)間的差異進(jìn)行聚類操作，如圖3 所示，運(yùn)行時(shí)間較長(zhǎng)的任務(wù)t3 和運(yùn)行時(shí)間較短的任務(wù)t1 合并至一個(gè)聚類中，任務(wù)t4 和任務(wù)t2 合并至一個(gè)聚類中。聚類J1 和J2的運(yùn)行時(shí)間都為40 s，下一層任務(wù)的釋放將在40 s后，計(jì)算可得：μ(tv)=40，

圖3 水平運(yùn)行時(shí)間平衡聚類

對(duì)比HC 算法在60 s 后釋放下一層任務(wù)，水平運(yùn)行時(shí)間平衡聚類算法（HRB）將在30 s后釋放下一層任務(wù)，HRB 算法明顯優(yōu)于HC 算法。較高的HRV 值意味著下一層任務(wù)的釋放較遲。因此，為了提高運(yùn)行性能，減少作業(yè)運(yùn)行時(shí)間方差很有意義。

2.2 容錯(cuò)機(jī)制

在科學(xué)工作流執(zhí)行過(guò)程中，故障頻繁發(fā)生，嚴(yán)重影響科學(xué)研究工作。工作流管理系統(tǒng)為工作流執(zhí)行提供軟件環(huán)境，主要負(fù)責(zé)工作流的定義和管理?？茖W(xué)工作流管理系統(tǒng)中的容錯(cuò)機(jī)制主要用于解決科學(xué)工作流流程組合結(jié)構(gòu)設(shè)計(jì)異常等問(wèn)題，主要有以下幾種：（1）基于其他任務(wù)技術(shù)。其他任務(wù)是指當(dāng)前任務(wù)的另外一種實(shí)現(xiàn)方式，如果流程中正在運(yùn)行的任務(wù)出現(xiàn)錯(cuò)誤，則啟動(dòng)另外一種實(shí)現(xiàn)方式。（2）備份技術(shù)。為全部工作流任務(wù)創(chuàng)建多個(gè)備份，并將備份任務(wù)分配至在不同數(shù)據(jù)節(jié)點(diǎn)上運(yùn)行，類似于Hadoop 中的文件存儲(chǔ)系統(tǒng)。多個(gè)備份任務(wù)將同步執(zhí)行，一旦故障發(fā)生，直接調(diào)用備份任務(wù)代替原任務(wù)繼續(xù)運(yùn)行。（3）修復(fù)工作流方式。在工作流第一次運(yùn)行時(shí)，科學(xué)工作流管理系統(tǒng)記錄下執(zhí)行過(guò)程中間所產(chǎn)生的錯(cuò)誤信息，然后根據(jù)記錄數(shù)據(jù)，修正工作流組件組合方式和運(yùn)行參數(shù)，經(jīng)過(guò)多次運(yùn)行和修改，故障率可以大幅度降低。（4）用戶自定義異常處理。用戶擁有一定權(quán)限，可以根據(jù)自己的需求根據(jù)經(jīng)驗(yàn)，按照自己的意愿設(shè)計(jì)錯(cuò)誤處理方案。

流程級(jí)的容錯(cuò)機(jī)制，大多以流程為單位進(jìn)行容錯(cuò)，其他任務(wù)技術(shù)、副本技術(shù)都對(duì)資源和成本浪費(fèi)較為嚴(yán)重，而修復(fù)工作流對(duì)于執(zhí)行次數(shù)少或者初次執(zhí)行的科學(xué)工作流，執(zhí)行效率太低。所以研究人員開(kāi)發(fā)了一系列任務(wù)級(jí)容錯(cuò)技術(shù)，用于科學(xué)工作流調(diào)度和執(zhí)行階段的故障恢復(fù)，細(xì)化了故障恢復(fù)單元，降低故障恢復(fù)成本。任務(wù)級(jí)容錯(cuò)主要包括：重試技術(shù)、副本技術(shù)以及檢查點(diǎn)技術(shù)。其中，Chen等人[10-11]對(duì)科學(xué)工作流中故障問(wèn)題進(jìn)行了深入的研究，所提出的重聚類算法，重新運(yùn)行發(fā)生故障的任務(wù)，改變了傳統(tǒng)的重試技術(shù)重新運(yùn)行所有任務(wù)的模式。重聚類算法在有效避免重試技術(shù)和備份技術(shù)所造成的資源浪費(fèi)的同時(shí)，考慮聚類數(shù)量等方面的優(yōu)化，很大程度地提高了科學(xué)工作流系統(tǒng)的運(yùn)行效率。

科學(xué)工作流通常需要大量復(fù)雜的分析和計(jì)算，相對(duì)其他類型工作流故障概率更高。并且科學(xué)工作流任務(wù)之間存在很強(qiáng)的約束關(guān)系，如果其中一個(gè)任務(wù)發(fā)生故障，則與其有依賴關(guān)系的所有后續(xù)任務(wù)都需要重新執(zhí)行。這表明故障發(fā)生后，故障恢復(fù)規(guī)模較大。為了能夠提高重聚類算法性能，減少任務(wù)故障所帶來(lái)的損失。本文從負(fù)載不平衡角度，研究對(duì)重聚類算法進(jìn)行改進(jìn)，提出了平衡重聚類算法（BR），在任務(wù)調(diào)度和執(zhí)行階段進(jìn)行故障恢復(fù)。

2.3 故障模型

故障的產(chǎn)生具有隨機(jī)性和不確定性，因此需要根據(jù)歷史數(shù)據(jù)對(duì)故障的產(chǎn)生進(jìn)行建模，通過(guò)故障模型評(píng)估容錯(cuò)算法。在文獻(xiàn)[1]中已經(jīng)證明系統(tǒng)開(kāi)銷可以用Gamma分布或者Weibull 分布來(lái)描述。Schroeder 和Gibson 已經(jīng)證實(shí)[20]，任務(wù)失敗的到達(dá)間隔時(shí)間更符合Weibull 分布（由形狀參數(shù)0.78定義）。文獻(xiàn)[21]中指出，Weibull分布、Gamma分布和Lognormal分布是估計(jì)一組工作流任務(wù)運(yùn)行時(shí)間的最佳選擇。在本文中，采用Gamma 分布模擬任務(wù)運(yùn)行時(shí)間(t)和系統(tǒng)開(kāi)銷(S)，采用Weibull 分布模擬故障間隔到達(dá)時(shí)間(u)。

Gamma如公式（1）所示，Gamma分布通常使用兩個(gè)參數(shù)描述：形狀參數(shù)(α)和比例參數(shù)(β)。形狀參數(shù)決定分布的形狀，比例參數(shù)決定分布的拉伸或收縮。Weibull分布是可靠性分析和壽命檢驗(yàn)的理論基礎(chǔ)，Weibull 分布形式與Gamma分布相似，α表示形狀參數(shù)，β表示比例參數(shù)。

已知a、b為先驗(yàn)知識(shí)，D為觀測(cè)數(shù)據(jù)，β為目標(biāo)估計(jì)參數(shù)。由貝葉斯概率論可知，當(dāng)觀測(cè)數(shù)據(jù)集已知時(shí)β的后驗(yàn)分布定義如下：

公式中的D可以代表失誤間隔時(shí)間(u)、任務(wù)運(yùn)行時(shí)間(t)或者系統(tǒng)開(kāi)銷(S)的觀測(cè)值。P(β|a,b)是已知的先驗(yàn)知識(shí)，P(β|D,a,b)是需要計(jì)算的后驗(yàn)概率。定義失誤到達(dá)間隔時(shí)間u的觀測(cè)值為X={x1,x2,…,xn} ；任務(wù)運(yùn)行時(shí)間t的觀測(cè)值表示為RT={t1,t2,…,tn} ，采用S={s1,s2,…,sn} 表示系統(tǒng)開(kāi)銷S的觀測(cè)值。通過(guò)已有的觀測(cè)參數(shù)，可以得到β的估計(jì)值。

使用Weibull 分布來(lái)建模失誤到達(dá)時(shí)間間隔u，其中參數(shù)α為已知形式參數(shù)（由經(jīng)驗(yàn)值給出），只需要計(jì)算規(guī)模參數(shù)β。具有已知形狀參數(shù)α的Weibull分布與逆Gamma 分布為共軛對(duì)，這表明如果先驗(yàn)分布遵循逆Gamma 分布，形狀參數(shù)為a，比例參數(shù)為b，則后驗(yàn)分布服從逆Gamma分布，形式如下：

對(duì)比例參數(shù)β進(jìn)行最大似然估計(jì)估計(jì)，β的估計(jì)定義如下：

通過(guò)相同的步驟，對(duì)總運(yùn)行時(shí)間T、系統(tǒng)開(kāi)銷S以及故障到達(dá)時(shí)間u等需要提前預(yù)知的參數(shù)進(jìn)行估計(jì)，從而建立任務(wù)故障模型。通過(guò)調(diào)整故障模型中故障到達(dá)間隔時(shí)間（故障出現(xiàn)頻率），對(duì)所提出的算法進(jìn)行測(cè)試。

3 容錯(cuò)聚類算法

3.1 選擇重聚類（SR）

選擇重聚類算法在作業(yè)運(yùn)行結(jié)束后，輸入標(biāo)記運(yùn)行失敗的聚類作業(yè)，篩選出作業(yè)中運(yùn)行失敗的任務(wù)，并將這些任務(wù)合并到新的群集中，提交至主機(jī)再次執(zhí)行。算法1為選擇重聚類算法的偽代碼。

算法1選擇重聚類

輸入：W，科學(xué)工作流；C，每個(gè)類中的任務(wù)數(shù)量

輸出：W，科學(xué)工作流

1.procedureRECLUSTERING（J）

2.TL←divideAtLeve（lJ）

3.Jnew←{ }

4.forTask∈TLdo

5. iftis failed then

6.Jnew.add(t)

7. end if

8.end for

9.W=W-Jnew

10.returnW

11.end procedure

3.2 動(dòng)態(tài)重聚類（DR）

動(dòng)態(tài)重聚算法對(duì)選擇重聚類算法進(jìn)行改進(jìn)，考慮聚類規(guī)模（聚類中任務(wù)數(shù)量）對(duì)故障的影響。根據(jù)故障到達(dá)時(shí)間間隔、任務(wù)規(guī)模動(dòng)態(tài)地估計(jì)出使得系統(tǒng)開(kāi)銷可以取到最小的聚類任務(wù)數(shù)量(K)，在每次重運(yùn)行時(shí)，動(dòng)態(tài)更新K值，根據(jù)K值進(jìn)行聚類劃分。動(dòng)態(tài)重聚類算法的偽代碼如算法2所示。

算法2動(dòng)態(tài)重聚類

輸入：W，科學(xué)工作流；C，每個(gè)類中任務(wù)的數(shù)量

輸出：W，科學(xué)工作流

1.procedureRECLUSTERING（J）

2.TL←DivideAtLeve（lJ）

3.Jnew←{ }

4. forTask∈TLdo

5. iftis failed then

6.Jnew.add(t)

7. end if

8. ifJnew.size()＞Kthen

9.W=W+Jnew

10.Jnew←{ }

11. end if

12.end for

13.W=W+Jnew

14.returnW

15.end procedure

3.3 平衡重聚類（BR）

本文旨在解決重聚類算法在聚類過(guò)程中所面臨的負(fù)載不平衡問(wèn)題。平衡重聚類算在SR 算法的基礎(chǔ)上，根據(jù)各層任務(wù)運(yùn)行時(shí)間的差異，來(lái)調(diào)節(jié)聚類總運(yùn)行時(shí)間，以達(dá)到負(fù)載平衡的目的。負(fù)載平衡過(guò)程類似于HRB 算法，首先根據(jù)任務(wù)運(yùn)行時(shí)間長(zhǎng)短對(duì)故障任務(wù)列表進(jìn)行排序。然后進(jìn)行聚類操作，每次分配運(yùn)行時(shí)間最長(zhǎng)的任務(wù)至總運(yùn)行時(shí)間最短的聚類。

篩選出運(yùn)行失敗的任務(wù)后，負(fù)載平衡的實(shí)現(xiàn)仍面臨一個(gè)關(guān)鍵問(wèn)題，即聚類規(guī)模的確定。聚類個(gè)數(shù)與總運(yùn)行時(shí)之間存在約束關(guān)系。如下所示：

R=min{MLE(T)}

根據(jù)需重運(yùn)行任務(wù)的規(guī)模、可用資源數(shù)量，估計(jì)出使得總運(yùn)行時(shí)間最小的聚類個(gè)數(shù)R。以R作為已知數(shù)據(jù)輸入，進(jìn)行平衡重聚類。算法3展示了平衡重聚類算法的偽代碼。

算法3運(yùn)行時(shí)間平衡容錯(cuò)聚類

輸入：W，科學(xué)工作流；R，每一層作業(yè)中的聚類數(shù)量

輸出：W，科學(xué)工作流

1.procedureRECLUSTERING（W，R）

2.TL←DivideAtLevel(W,level)

3.Jnew←{ }

4. fortask∈TLdo

5. iftis failed then

6.Jnew.add(t)

7. end if

8. ifJnew.size＞Rthen

9.C=C+Jnew

10.Jnew←{ }

11.end if

12.end for

13.W=W+Jnew

14.end procedure

15.procedureMERGE(TL,C,R)

16.ifi＜Rthen

17.Jnew←{ }

18.end if

19.CL←{ }

20.sort(TL)

21.fort∈TLdo

22.J.add(t)

23.end for

24.fori＜Rdo

25.CL.add(Ji)

26.end for returnCL

27.end procedure

選擇重聚類將聚類規(guī)模簡(jiǎn)單定義為運(yùn)行失敗任務(wù)的數(shù)量，并不考慮聚類大小對(duì)SR 算法的性能影響。但是，實(shí)際的最佳聚類規(guī)模會(huì)隨著故障任務(wù)的數(shù)量和可用資源數(shù)量的變化而改變。動(dòng)態(tài)重聚類算法彌補(bǔ)了選擇重聚類算法的不足，根據(jù)可用資源狀況和任務(wù)規(guī)模計(jì)算出最佳聚類規(guī)模，每次重新運(yùn)行時(shí)動(dòng)態(tài)地調(diào)整聚類規(guī)模。與SR 算法和DR 算法相比，BR 算法在解決重聚類算法中負(fù)載不平問(wèn)題的同時(shí)，根據(jù)資源數(shù)量和故障規(guī)模計(jì)算最佳聚類數(shù)，兼并HRB 算法和DR 算法的優(yōu)點(diǎn)，很大程度地提高了重聚類算法的性能。

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)在五個(gè)常用科學(xué)工作流應(yīng)用程序上進(jìn)行，評(píng)估了選擇重聚類算法、動(dòng)態(tài)重聚類算法和平衡重聚類算法的性能。五個(gè)科學(xué)工作流應(yīng)用程序分別為：天文學(xué)應(yīng)用程序（Montage）、激光干涉引力波天文臺(tái)（LIGO）、地震應(yīng)用程序（CyberShake）、表觀基因組學(xué)（Epigenomics）和細(xì)菌學(xué)應(yīng)用（SIPHT）。文獻(xiàn)[22]詳細(xì)分析和描述了五種工作流各自的結(jié)構(gòu)和特征。

實(shí)驗(yàn)環(huán)境由WorkflowSim[23]仿真器提供，Workflow-Sim作為常用的科學(xué)工作流實(shí)驗(yàn)仿真環(huán)境，提供了20個(gè)虛擬機(jī)（VM），每一個(gè)VM 都有512 MB 的內(nèi)存，用于模擬真實(shí)的分布式環(huán)境。平臺(tái)提供了五種科學(xué)工作流的仿真實(shí)現(xiàn)、基礎(chǔ)調(diào)度算法、資源分配計(jì)劃以及測(cè)試程序。測(cè)試數(shù)據(jù)集均由WorkflowGenerator[24]生成，文獻(xiàn)[24]中已經(jīng)證明WorkflowGenerator 的可用性及其合理性。本實(shí)驗(yàn)在平臺(tái)調(diào)度階段實(shí)現(xiàn)三種重聚類算法，調(diào)用測(cè)試程序?qū)λ惴ㄐ阅苓M(jìn)行評(píng)估。

實(shí)驗(yàn)首先設(shè)置了不同的u（失敗到達(dá)間隔時(shí)間）值，觀測(cè)不同故障率情況下，三種重聚類算法實(shí)現(xiàn)后系統(tǒng)總運(yùn)行時(shí)間變化。u的值越高故障產(chǎn)生的概率越小，u的值越低故障產(chǎn)生的概率越大。然后，固定u值，觀測(cè)采用BR算法運(yùn)行前后五種科學(xué)工作流負(fù)載平衡衡量指標(biāo)HRV的變化。根據(jù)變化情況來(lái)評(píng)價(jià)算法在負(fù)載平衡方面的成果。

4.2 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)中u在任務(wù)平均運(yùn)行時(shí)間（平均運(yùn)行時(shí)間由文獻(xiàn)[24]計(jì)算得出，如表1所示）的1～10倍范圍內(nèi)取值，這樣工作流運(yùn)行時(shí)間合理，并且算法的性能差異能夠很好地體現(xiàn)。下面為五個(gè)科學(xué)工作流中三種重聚類方法的性能對(duì)比。

表1 五種科學(xué)工作流的特征

Montage：圖4 顯示了Montage 工作流的測(cè)試結(jié)果，可以看出當(dāng)故障到達(dá)時(shí)間間隔u取值較小時(shí)，BR算法、DR 算法性能明顯優(yōu)于SR 算法。隨著u逐漸增大時(shí)，BR、DR、SR 算法的性能結(jié)果趨于相等。這表明當(dāng)故障出現(xiàn)的頻率越高，BR算法和DR算法對(duì)系統(tǒng)性能提升越大。當(dāng)u取最小值20 s 的時(shí)候，對(duì)比BR 算法與SR 算法，性能增益最高為42%。隨著u的增大，性能增益逐漸降低。在u=100 s 時(shí)，性能增益為?2.76%。BR 算法相對(duì)DR算法的性能增益最高為7.14%，隨著u的增大，性能增益逐漸降至0.61%。

圖4 Montage工作流中三種重聚類算法性能對(duì)比

CyberShake：如圖5 所示，三類容錯(cuò)算法在Cyber-Shake工作流中測(cè)試結(jié)果的整體變化趨勢(shì)與Montage工作流的變化趨勢(shì)相似。在u=100 s時(shí)，相對(duì)SR算法，BR算法的性能增益提高了61.5%，隨后逐漸降低。BR 算法相對(duì)DR 算法的性能增益最高為3.79%。當(dāng)u>500 s時(shí)，明顯看到BR、DR、SR之間的性能增益幅度非常小，性能增益均在0.45%以下。

LIGO：LIGO 工作流中三種重聚類算法的實(shí)驗(yàn)結(jié)果如圖6所示，BR算法相對(duì)SR算法性能增益最高提升了43.0%，最低提高4.2%。當(dāng)u從800 s增加到2 000 s，BR 相對(duì)DR 算法的性能增益逐漸降低，從0.93%降低到?0.19%。這表明BR 算法的性能提升與DR 算法相近。在u=1 000 s處，SR算法性能略高于DR、BR算法。

圖5 CyberShake工作流中三種重聚類算法性能對(duì)比

SIPHT：圖7 為三種重聚類算法在SIPHT 工作流中的實(shí)驗(yàn)結(jié)果。不同于上述三種工作流中，BR相對(duì)SR的性能增益隨著u的增加而降低。當(dāng)u取2 500 s 時(shí)，BR算法相對(duì)SR的性能增益為61.54%。當(dāng)u分別取3 500、4 500、5 500時(shí)，BR算法相對(duì)SR的性能增益分別為9.1%、?0.35%、6.35%。同時(shí)，相對(duì)DR算法，BR算法的性能增益隨u的增加逐漸降低，從7.89%降到了?0.39%。

Epigenomics：如圖8 所示，為三種重聚類方法在Epigenomics工作流中的實(shí)驗(yàn)結(jié)果。與其他四種工作流相比，BR 算法的性能增益明顯高于其他四類工作流。BR 算法相比SR 算法性能增益最高為84.0%，最低為50%。同時(shí)，相對(duì)于DR 算法，BR 算法性能增益高達(dá)18.75%，最低為4.55%，這是一個(gè)比較可觀的提升。

圖8 Epigenomics工作流中三種重聚類算法性能對(duì)比

對(duì)比三種重聚類算法在五類工作流中的性能表現(xiàn)，可以看出隨著u的變化，性能增益所變現(xiàn)出來(lái)的規(guī)律有很大差別。為了更好地解釋這一結(jié)果，只能根據(jù)工作流的機(jī)構(gòu)以及任務(wù)運(yùn)行時(shí)間特點(diǎn)進(jìn)行分析。表1 列舉了五類個(gè)科學(xué)工作流任務(wù)的平均大小和平均任務(wù)運(yùn)行時(shí)間，但是缺少了任務(wù)運(yùn)行的細(xì)節(jié)。因此，設(shè)計(jì)了第二組實(shí)驗(yàn)，在取定u值的情況下分析BR算法對(duì)負(fù)載（運(yùn)行時(shí)間）的影響。

根據(jù)前面的實(shí)驗(yàn)結(jié)果選取平均任務(wù)運(yùn)行時(shí)間的一倍作為u值，因?yàn)閡取該值時(shí)，三種重聚類算法性能間的差異更加明顯。取定u值后，分析對(duì)比五個(gè)科學(xué)工作流中執(zhí)行BR 算法前的HRV 和執(zhí)行BR 算法后HRV 值的變化，其結(jié)果如圖9所示。

Montage：如圖9（a）所示，由于大多從層均為單任務(wù)，因此HRV都為0值。而第2、5層HRV值降低非常明顯，下降率分別為85.3%、98.1%。

CyberShake：如圖9（ b）所示，HRV 值在 B R 算法運(yùn)行前后的下降率最大為55.9%，最小為30.4%。

LIGO：如圖9（c）所示，在第1層中HRV的下降率最高為82.8%，而其他層都低于50%。

SIPHT：如圖9（d）所示，在第3 層HRV 下降率最高為41%，其他層HRV下降率均小于30%。

Epigenomics：如圖9（e）所示，相對(duì)其他工作流BR算法運(yùn)行前后HRV 的下降率，該工作流HRV 下降率較低，最大下降率僅為38.9%。

分析圖9 中五個(gè)實(shí)驗(yàn)結(jié)果，可以發(fā)現(xiàn)較Montage、LIGO中BR算法運(yùn)行前后HRV的值都非常小，而SIPHT中HRV的值遠(yuǎn)高于其他四個(gè)的值。結(jié)合表1可知，LIGO工作流程的平均任務(wù)運(yùn)行時(shí)間相對(duì)較短，即使BR 算法運(yùn)行后平均每層HRV 的值降低了將近50%，而最終的系統(tǒng)開(kāi)銷相對(duì)DR 算法只提升了0.93%，而Montage 中HRV 值的變化最大，在第二層中，HRV 值減小了68%，即使Montage 的平均運(yùn)行時(shí)間相對(duì)較小，但BR 算法對(duì)于DR算法的性能增益為7.14%。SIPHT工作流的結(jié)構(gòu)非常不對(duì)稱，HRV 值相對(duì)較高。BR 算法可以通過(guò)平衡運(yùn)行時(shí)間進(jìn)行優(yōu)化，DR 算法可以通過(guò)動(dòng)態(tài)調(diào)整聚類大小進(jìn)行優(yōu)化，而SR 算法的隨機(jī)性較大。這就可以解釋BR 相對(duì)SR 算法的性能增益不規(guī)律問(wèn)題。Epigenomics工作流的HRV 值的下降率平均為25%，在level=4 時(shí)，HRV值仍為0.64，相對(duì)較高。根據(jù)表1可知，Epigenomics的平均任務(wù)運(yùn)行時(shí)間是Montage 的300 倍，所以將近20%的運(yùn)行時(shí)間平衡導(dǎo)致了系統(tǒng)開(kāi)銷18.75%的提升。

圖9 五種科學(xué)工作流中執(zhí)行BR算法前后HRV的對(duì)比結(jié)果

結(jié)合兩組實(shí)驗(yàn)結(jié)果分析，可知當(dāng)故障出現(xiàn)頻率較高時(shí)，平衡重聚類算法性能提升明顯高于動(dòng)態(tài)重聚類算法、選擇重聚類算法。當(dāng)工作流任務(wù)結(jié)構(gòu)不對(duì)稱（HRV值較高的SIPHT 工作流）或運(yùn)行時(shí)間嚴(yán)重不平衡時(shí)（例如，Epigenomics 工作流），即使故障率較低下，BR 算法對(duì)工作流系統(tǒng)的運(yùn)行效率仍有較大的提高。

5 總結(jié)

為解決容錯(cuò)聚類算法面臨的負(fù)載不平衡問(wèn)題，本文提出了一種考慮任務(wù)運(yùn)行時(shí)間平衡的容錯(cuò)聚類算法BR，通過(guò)調(diào)整模型中故障出現(xiàn)頻率測(cè)試算法性能。實(shí)驗(yàn)結(jié)果表明，在故障率較高的情況下，與現(xiàn)有的任務(wù)容錯(cuò)聚類方法相比，BR 算法顯著降低了科學(xué)工作流的完工時(shí)間，在故障率較低的情況下，平衡容錯(cuò)聚類方法在Epigenomics 工作流中表現(xiàn)最佳。BR 算法采用水平運(yùn)行時(shí)間平衡方法來(lái)解決負(fù)載平衡問(wèn)題，未來(lái)的工作可以考慮任務(wù)間距離平衡或依賴關(guān)系平衡方法與容錯(cuò)聚類方法的結(jié)合。根據(jù)不同工作流呈現(xiàn)出的不平衡問(wèn)題，推薦相應(yīng)的平衡重聚類算法。