肖鵬，胡志剛，閻朝坤，屈喜龍

（1. 湖南工程學院 計算機與通信系，湖南 湘潭 411104；2. 中南大學 信息科學與工程學院，湖南 長沙 410083）

1 引言

網格環(huán)境[1]中的預留服務主要用于保證資源分配時刻的可獲得性，從而為資源協(xié)同分配提供QoS保證[2]。近期網格性能測評報告顯示，過度使用預留機制會對性能造成嚴重負面影響，例如資源有效利用率下降[2～4]、系統(tǒng)負載不均衡[5,6]、服務請求拒絕率升高[7,8]、調度性能低下[9]。解決預留機制的負面影響成為改進網格系統(tǒng)性能的一個重要的課題。由于資源異構性和負載動態(tài)性，任務難以準確估計其預留數(shù)量和時間，導致的結果是：①任務傾向于高估其預留時間，以此確保足夠的時間彈性[3,7,8]；②任務傾向重復提交預留請求，以此降低資源故障對任務執(zhí)行的影響[2,3,10]。Dun等人[11]對大量工作流的性能測評顯示，任務實際執(zhí)行效率往往因為不準確的預留估計而極不確定；Prodan等人[12]在分析導致工作流延遲的因素時發(fā)現(xiàn)，預留協(xié)商延遲是影響工作流執(zhí)行效率的關鍵因素。基于預留機制存在的問題，本文提出一種支持時空二維松弛的預留策略，允許系統(tǒng)在一定條件下接納存在疊交的預留請求，目標是降低傳統(tǒng)預留機制對系統(tǒng)性能的負面影響。

2 相關研究

Smith等人[2]從等待時間、預留延遲、拒絕率等方面分析了預留機制對任務調度的影響，其實驗數(shù)據顯示：預留機制能有效降低任務平均等待時間，但面對較高的預留請求率時，以上性能指標都會顯著惡化。為降低預留機制對資源利用率的負面影響，回填技術[6]被廣泛應用，例如文獻[3]中提出了基于回填技術的多資源協(xié)同預留算法，其實驗數(shù)據顯示，回填技術能有效減輕預留機制給系統(tǒng)性能帶來的負面影響；Sulistio等人[4]則針對用戶頻繁取消預留請求的問題提出一種超額預留機制，以此降低頻繁取消預留請求所導致的資源效率損失。

傳統(tǒng)預留機制的另一個主要缺陷是容易產生大量“資源能力碎片”。針對這一問題，胡春明等人[13]提出一種基于彈性時間的預留策略，通過引入時間彈性因子，以此提高資源調度的自主性和資源綜合利用率；Farooq等人[7]則提出一種“關鍵任務重調度”機制，用于降低關鍵路徑上的任務預留請求被拒絕的概率；Jawad等人[14]則提出了一種基于“動態(tài)關鍵路徑”的協(xié)同預留機制，其核心思想是將通信關聯(lián)度強的父子節(jié)點聚合，從而重構工作流的關鍵節(jié)點和路徑；與本文研究最為接近的是Sulistio等人在文獻[4]中提出“超額預留”機制，但該研究只給出“超額預留”的概念，而對其將導致的違約風險缺乏量化分析和解決策略。而本文則明確給出了量化分析松弛策略的預留違約風險的方法。

3 定義與問題描述

設網格系統(tǒng)由N個資源站點組成，表示為集合{R1,R2,…,RN}；工作流表示為有向無環(huán)圖 G = ＜T,E＞，其中，T = [t1, t2, …, tn]為工作流的子任務集合，E = {＜ ti, tj＞|if ＜ ti, tj＞∈T×T}為工作流的有向邊集合；子任務ti的預留請求表示為三元組＜si,ei,ri＞，si為預留起始時間，ei為預留截止時間，ri為資源預留量；資源時間槽 Sk表示為三元組＜λk, μk, πk＞，λk為時間槽起始時間，μk為結束時間，πk為空閑資源量

定義 1 若 Sk對 ti的預留請求＜si,ei,ri＞以概率Pk,i滿足(si≥λk)∩(ei≤μk) ∩ (fk≥ri)，則稱時間槽 Sk松弛滿足ti的預留請求。

定義 2 與子任務ti的預留起始時間和截止時間疊交的預留請求集合記分別記為S-(ti)和S+(ti)：

定義3 設隨機事件Ei表示子任務ti沒有發(fā)生預留違約，隨機事件表示集合(ti)沒有導致 ti發(fā)生預留違約，隨機事件表示集合S+(ti)沒有導致ti發(fā)生預留違約。

圖1 資源預留時間槽示例

以圖1為例，當ti的預留請求ri到達時，時間槽上已經存在7個預留請求，按照傳統(tǒng)預留的定義，則不存在能滿足ri的空閑時間槽。(ti)={r2, r3, r4}且S+(ti)={r5, r7}，若其中的預留請求提前釋放資源，則ri實際并不會發(fā)生預留違約。由定義3可知， ti不發(fā)生預留違約的概率計算公式為

工作流G = ＜T, E＞的協(xié)同預留方案可以表示為從資源需求集合到資源站點集合的映射 M:{r1,r2,…, rn}× {R1,R2,…,RN}→{0,1}。顯然協(xié)同預留方案M為n×N矩陣，Mi,j=1表示在Cj上預留資源給子任務 ti。綜合上述定義和分析，面向工作流的松弛預留策略可以歸結為以下優(yōu)化問題：

其中，Pr{E|M}≥V*則表示協(xié)同預留方案M不發(fā)生預留違約的概率大于等于V*。V*為松弛預留閾值，其數(shù)值越大則表示松弛接納策略越保守，當 V*=1時松弛預留策略退化為傳統(tǒng)預留策略。由于預留方案 M 的解空間為 2n×N，上述優(yōu)化問題顯然屬于NP-Complete。對此，第 4節(jié)的預留接納策略將采用進化算法[15]來求取近似最優(yōu)解。

4 策略分析與求解

4.1 違約概率分析

由式(3)可知，工作流中子任務ti的預留違約概率由Pr{}和Pr{}合成。

其中，Tk為隨機變量表示子任務tk的實際完成時間，集合是(ti)子集中滿足如下條件的子集：

①若ti的資源預留量ri滿足

則 ti需要中所有預留請求都在 si之前完成，才能保證不發(fā)生預留違約，Pr{}的計算公式為

②若資源預留量ri滿足

綜合以上2種情況的分析可知，ti不出現(xiàn)預留違約的概率Pr{}具有嚴格的上界和下界，其計算式分別由式(8)和式(10)給出，證畢。

其中，rk的預留起始時間滿足以下條件

證明 若 ti的實際完成時間提前并釋放其資源，則S+(ti)中部分預留請求將不會產生預留違約。關鍵問題是：ti的實際完成時間提前到何種程度才能保證 S+(ti)的預留請求都不會產生預留違約。為此，可以將S+(ti)中的預留請求按起始時間升序排列為＜r1,r2,…,rm＞，并從中找到一個滿足式(13)所示條件的rk。顯然，如果ti的實際完成時間早于rk，S+(ti)中預留請求＜r1,r2,…,rk＞都不會和ti的預留請求發(fā)生任何交疊；另一方面，ti提前釋放的資源能夠保證S+(ti)中＜rk+1,rk+2,…,rm＞都不發(fā)生會由于空閑資源不夠而導致的預留違約。綜上所述，得證。

4.2 預留接納算法

本文主要考慮網格工作流，由于子任務之間存在相互依賴關系，因此必須首先計算出子任務之間的關聯(lián)強度。本文采用了PMCC[17]公式來計算工作流子任務之間的關聯(lián)強度。工作流中任意兩子任務ti和tj(i ≠ j)之間的關聯(lián)強度計算公式如下：

其中，Ti和Tj為隨機變量，分別表示任務ti和tj的實際完成時間。針對網格工作流的基于松弛預留策略的協(xié)同預留接納算法實現(xiàn)如下所示。

End.

算法采用進化策略來獲得調度長度最優(yōu)化的協(xié)同預留方案。step 4 ～ step 15是采用松弛策略的分析結論來計算工作流中每個子任務不發(fā)生預留違約的概率，step 16則求取整個協(xié)同預留方案不出現(xiàn)預留違約的概率。算法的整體復雜度為O(Wn2N)，W為進化迭代數(shù)目，n為工作流中的任務節(jié)點數(shù)，N為網格系統(tǒng)的資源站點數(shù)目。

5 實驗與性能分析

實驗構建了一個異構多集群計算網格，包括了12個高性能計算集群作為資源站點，各集群節(jié)點的性能指標參考 DAS-2[18]的配置。實驗首先以隨機DAG作為工作負載，然后采用 WIEN2K[19]工作流進行實驗分析。

5.1 隨機DAG實驗分析

REXR是本文提出的松弛預留策略；CONR[2]為傳統(tǒng)的嚴格預留策略，主要作為實驗分析的基線；CBFR[6]為保守回填預留策略；MALR[20]為可塑預留策略；OVBR[4]為超額預留策略。實驗分5組進行，預留請求率從 5%逐步增加到 25%。實驗設定OVBR的超額接納率為20%，REXR的接納閾值 V*為 0.8。圖 2為不同預留請求率的資源平均利用率。實驗數(shù)據顯示，當預留請求率較低時(5%和10%)，CBFR、MALR、OVBR和REXR 4種策略的資源利用率差別很小，且相對 CONR策略而言大約能提高 13%；當預留請求率超過15%時，這 4種策略的性能表現(xiàn)出現(xiàn)明顯分化，其中OVBR策略的性能下降最為顯著，而CBFR策略和 MALR的性能差異只在預留請求率到達20%以上時才比較明顯。為了分析各種策略之間的性能差異，統(tǒng)計了各個資源站點的平均資源率，如圖3所示。

圖2 不同預留請求率下的資源平均利用率

圖3 各個資源站點的平均利用率

CONR策略偏向于將預留請求均衡地分配到各個站點，由于資源站點的靜態(tài)性能和動態(tài)負載壓力差異很大，因此CONR策略在面對較高的預留請求率時其性能表現(xiàn)顯著惡化；CBFR和MALR則偏向于向靜態(tài)性能指標較高的站點預留資源，因而導致這些站點面臨更高負載；OVBR在實現(xiàn)層面上類似CONR，由于實驗設定了20%的超額接納率，在預留請求率不高時，20%的超額預留沒有對系統(tǒng)造成任何負面影響，因此OVBR策略的表現(xiàn)是5種策略中最優(yōu)的，但隨著預留請求率的上升，OVBR不僅不能提高資源利用率，反而頻繁導致預留違約，從而使得有效資源利用率顯著下降。REXR策略的主要特點是隨預留請求率的增大而相對保持平穩(wěn)，例如當預留請求率從5%增大到25%時，REXR只損失了約24%的資源利用率。

圖4為5種策略在拒絕率方面的性能比較。實驗數(shù)據顯示：當預留請求率較低時，5種策略的拒絕率差別不大，原因是為整個網格系統(tǒng)處于低負載狀態(tài)，此時預留機制的負面效果尚為突出；當預留請求率升高時，CBFR的拒絕率增加最快，其次是CONR策略和MALR策略，而OVBR策略的拒絕率幾乎和REXR相同。OVBR策略和REXR策略的拒絕率相似的原因是兩者都放寬了預留接納的標準。為進一步分析這2種策略在不同參數(shù)下的性能表現(xiàn)，用不同的參數(shù) V*和 O*重復本次實驗，其中V*為 REXR策略的松弛接納閾值，而 O*為 OVBR的超額接納率，實驗結果如圖5所示。

圖4 不同預留請求率下的預留請求拒絕率

圖5 不同參數(shù)下的預留違約率比較

實驗結果顯示，OVBR在較低的預留請求率時幾乎沒有任何預留違約，而當預留請求率達到并超過15%時，其預留違約率顯著增加。當OVBR策略采用40%的超額預留率時，其違約率高達74%。即使預留請求率為20%，OVBR的違約率也高達55%相對而言，REXR的V*參數(shù)也會對其違約率產生一定影響，具體表現(xiàn)為：V*的值越小，違約率隨之增加得越快，但總體幅度明顯小于OVBR，而且只要V*值不小于0.8，其預留違約率就能控制在7%以內。

REXR算法的時間開銷由進化策略的迭代參數(shù)W和任務規(guī)模決定，本次實驗統(tǒng)計了REXR算法不同參數(shù)取值下的算法的平均執(zhí)行時間，實驗結果如表1所示。任務規(guī)模對算法執(zhí)行效率的影響明顯大于參數(shù)W的影響。當任務規(guī)模較小時，REXR算法收斂速度很快，此時的W參數(shù)幾乎不影響算法執(zhí)行效率；當任務規(guī)模達到200以上時，進化迭代參數(shù)至少要達到500以上，算法才能獲得有效收斂。

表1 不同參數(shù)下的算法執(zhí)行時間/s

綜合以上實驗數(shù)據和分析，本次實驗的主要結論是：①當預留請求率低于10%時，CBFR策略和OVBR策略能有效提高資源利用率；②當預留請求率大于10%時，REXR策略能顯著降低過渡預留導致的資源效率損失；面對較低的預留請求率，松弛接納閾值V*可以設置得較低，但面對較高的預留請求率時，V*取值不應過小。

5.2 實際工作流分析

WIEN2K工作流[19]包括2個并行分支，其問題規(guī)模由這2個并行分支決定，實驗設定問題規(guī)模從100逐步增加到 600。實驗過程中向網格系統(tǒng)注入了一定的背景工作負載，從而與WIEN2K共同競爭系統(tǒng)資源。為分析任務高估預留時間對其執(zhí)行效率的影響，本次實驗將WIEN2K中各個任務節(jié)點的預留時間高估了β倍，實驗分4組進行，β值分別為10%、20%、30%和40%，實驗結果如圖6所示。

實驗結果顯示，當任務預留時間高估率為10%且任務規(guī)模為100～400時，CONR、MALR和REXR 3種策略對應的WIEN2K執(zhí)行時間差別很小，但當任務規(guī)模達到500以上時，REXR策略的性能優(yōu)勢就比較明顯了，其對應的工作流執(zhí)行時間大約只有前2種策略的51%；隨著任務高估率β值的增加，所有策略所對應的執(zhí)行時間都顯著增加，不過相對增幅出現(xiàn)了明顯差異，其中MALR策略的相對增幅最明顯，而REXR策略的執(zhí)行時間隨β值而增加的幅度則遠遠小于其他4種策略。

背景負載對 WIEN2K執(zhí)行效率的影響十分明顯。當任務規(guī)模小于400時，OVBR策略在本次實驗中的性能表現(xiàn)是最差的，OVBR策略表現(xiàn)不佳的主要原因是，背景負載在實驗開始階段的到達速度較快，系統(tǒng)在面對較高額外負載時，其資源可用量顯著降低，而超額預留策略則更加減少了系統(tǒng)未來的可預留資源量，因此WIEN2K第2個并行分支中的許多子任務出現(xiàn)了執(zhí)行延遲，從而影響任務整體的執(zhí)行效率。但這種情況在β值較高時得到了一定程度的緩解，原因剛好是因為較高的β值意味著并行分支中的預留時間被高估，很多預留請求實際被提前釋放，其效果等價于取消預留請求，從而令OVBR策略的性能表現(xiàn)得到一定程度的提升。

MALR策略在任務規(guī)模超過400后，其性能表現(xiàn)明顯低于其他策略，產生這種現(xiàn)象的原因與WIEN2K工作流的結構特征有關。因為WIEN2K的主要執(zhí)行時間集中在2個大的并行分支部分，其并行子任務類似一組獨立子任務。因此WIEN2K的最終執(zhí)行時間是由這些子任務集合的最遲完成時間決定。而MALR策略的優(yōu)越性主要體現(xiàn)在子任務差異度很大的情況下，此時MALR策略能依據子任務的計算量和資源需求量之間的線性關系來規(guī)劃一個總體完成時間較優(yōu)的預留方案，而本實驗所分析的WIEN2K則不具備這種特許。因此MALR策略的平均執(zhí)行時間大約是REXR策略的一倍左右。

圖6 不同β值下WIEN2K執(zhí)行時間對比

本次實驗的主要結論是：①高估預留時間將對工作流執(zhí)行效率產生較大負面影響，REXR策略能夠有效降低這種負面影響；②OVBR和CBFR難以適應突發(fā)負載增高的情況，當系統(tǒng)整體負載較重時，2種策略對任務執(zhí)行效率的負面影響顯著增大；③MALR的性能表現(xiàn)受工作流結構特征影響較大。

6 結束語

提出一種支持時空二維松弛的預留策略，用于解決預留機制對系統(tǒng)性能的負面影響，并采用進化算法與松弛預留策略相結合的方法設計了一個協(xié)同資源預留接納算法。實驗結果顯示，松弛預留策略不僅能有效降低預留服務對系統(tǒng)性能的負面影響，而且在能顯著降低由高估預留時間而導致電工作流執(zhí)行效率損失。今后的主要工作是在松弛預留模型中引入資源失效情況下的分析和處理技術。

[1] FOSTER I, KESSELMAN C. The Grid 2 [M]. San Francisco: Morgan Kaufmann, 2004.

[2] SMITH W, FOSTER I, TAYLOR V. Scheduling with advanced reservations[A]. IPDPS’00[C]. Cancun, Mexico, 2000.127-132.

[3] CAO J W, ZIMMERMANN F. Queue scheduling and advance reservations with COSY[A]. IPDPS’04[C]. Santa Fe, New Mexico, USA,2004.63-70.

[4] SULISTIO A, KIM K H, BUYYA R. Managing cancellations and no-shows of reservations with overbooking to increase resource revenue[A]. CCGRID’08[C]. Lyon, France, 2008.267-276.

[5] AIDA K, CASANOVA H. Scheduling mixed-parallel applications with advance reservations[J]. Cluster Computing, 2009,12(2):205-220.

[6] CASTILLO C, ROUSKAS G N, HARFOUSH K. Efficient resource management using advance reservations for heterogeneous grids[A].IPDPS’08[C]. Miami, Florida, USA, 2008.1-12.

[7] FAROOQ U, MAJUMDAR S, PARSONS E W. Impact of laxity on scheduling with advance reservations in Grids[A]. MASCOTS’05[C].Atlanta, Georgia, USA, 2005.319-322.

[8] LI B, SHEN B. Slack-based advance reservation for grid jobs[A].ICACTE’10[C]. Chengdu, China, 2010.418-423.

[9] SODAN A C, DOSHI C, BARSANTI L, et al. Gang scheduling and adaptive resource allocation to mitigate advance reservation impact[A].CCGRID’06[C]. Singapore, 2006.649-653.

[10] BURCHARD L O. Analysis of data structures for admission control of advance reservation requests[J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(3):413-424.

[11] DUN N, TAURA K, YONEZAWA A. Fine-grained profiling for data-intensive workflows[A]. CCGRID’10[C]. Melbourne, Australia,2010.571-572.

[12] PRODAN R, FAHRINGER T. Overhead analysis of scientific workflows in grid environments[J]. IEEE Transactions on Parallel and Distributed Systems, 2008, 19(3):378-393.

[13] 胡春明, 懷進鵬, 沃天宇. 一種基于松弛時間的服務網格資源能力預留機制[J]. 計算機研究與發(fā)展, 2007,44(1): 20-28.HU C M, HUAI J P, WO T Y. Flexible resource capacity reservation mechanism for service grid using slack time[J]. Journal of Computer Research and Development, 2007,44(1):20-28.

[14] JAWAD A, THOMAS E. A new resource mapping technique for grid workflows in advance reservation environments[A]. HPCS’10[C].Normandy, France, 2010.63-70.

[15] 公茂果, 焦李成, 楊咚咚等. 進化多目標優(yōu)化算法研究[J]. 軟件學報, 2009, 20(2):271-289.GONG M G, JIAO L C, YANG D D, et al. Evolutionary multi- objective optimization algorithms[J]. Journal of Software, 2009, 20(2):271-289.

[16] MENG X H, ZHU Y A, WU X M. Improved dynamic programming algorithms for the 0-1 knapsack problem[A]. ICCSIT’11[C]. Chendu,China, 2011.19-22.

[17] SNEDECOR G W, COCHRAN W G. Statistical Methods[M]. Ames:Iowa State Press, 1980.

[18] BAL H, BHOEDJANG R R, HOFMAN R, et al. The distributed ASCI supercomputer project[J]. ACM Operating Systems Review, 2000,34(4):76-96.

[19] TOPCUOGLU H, HARIRI S, WU M Y. Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(2):260-274.

[20] WU L, WU C, CUI J, et al. An adaptive advance reservation mechanism for grid computing[A]. PDCAT’05[C]. Dalian, China,2005.400-403.