異構(gòu)分布式環(huán)境下協(xié)作任務(wù)的調(diào)度算法

1、基金項目：國家自然科學(xué)基金資助項目“基于排隊網(wǎng)絡(luò)的Web服務(wù)組合性能分析”(No.61262014)。作者簡介：龍浩（1970），男，博士，副教授，研究領(lǐng)域：工作流、服務(wù)計算。汪浩（1962），男，博士，教授，研究領(lǐng)域：網(wǎng)絡(luò)性能分析，服務(wù)計算異構(gòu)環(huán)境下科學(xué)工作流的啟發(fā)式調(diào)度算法異構(gòu)環(huán)境下科學(xué)工作流的啟發(fā)式調(diào)度算法龍浩汪浩（江西師范大學(xué)軟件學(xué)院江西南昌330029）Email：hhlong2010@摘要：要：針對資源個體與網(wǎng)絡(luò)鏈路差異較大

2、、廣域互連的分布式系統(tǒng)下科學(xué)工作流的時間費用優(yōu)化問題，提出改進的相對效比調(diào)度算法。利用任務(wù)配置圖描述關(guān)聯(lián)科學(xué)工作流過程模型的資源模型，利用任務(wù)資源分配圖作為科學(xué)工作流調(diào)度模型，采用相對效費比迭代調(diào)整任務(wù)資源分配圖，最終得到優(yōu)化的工作流調(diào)度方案。算法能夠避免共享資源訪問沖突，合理地篩選候選資源、優(yōu)化費用，能夠很好地適用科學(xué)工作流的資源差異較大及任務(wù)間存在大量數(shù)據(jù)傳輸?shù)奶卣?，模擬實驗表明算法性能有較大的提高。關(guān)鍵詞關(guān)鍵詞:科學(xué)工作流；任務(wù)配

3、置圖；任務(wù)資源分配圖；相對效費比中圖法分類號：中圖法分類號：TP393文獻標識碼：文獻標識碼：AASchedulingHeuristicofScientificWkflowunderDistributedComputingEnvironmentLONGHaoWANGHao(SchoolofSoftwareJiangxiNmalUniversityNanchang330022China)Abstract:Dataintensivescie

4、ntificwkflowsarequitecommonindistributedcomputingenvironmentsconsideringtheinterconnectedisomericphysicalresourcestheintensivedatatransferbetweensubtasksanimprovedheuristicbasedonrelativetimecostrate(RTCR)isproposed.Firs

5、tlyataskdeploymentdiagram(TDD)isusedtodepictthewkflow’smodelthedeploymentenvironmentaTaskResourceAssignmentGraph(TRAG)isusedtodescribepossiblesolutiontheoptimizationschedulingcanbeachievedbyadjustediterativelyaccdingtoth

6、eRTCRvalue.Theheuristics’efficiencyisrevealedbycomparingwithILHAalgithm.Keywds:scientificwkflowtaskdeploymentdiagramtaskresourceassignmentgraphrelativetimecostrate1概述概述隨著信息技術(shù)的發(fā)展和科學(xué)研究方法的日益豐富，使用大規(guī)模計算資源和大容量存儲設(shè)備的計算型科學(xué)實驗成為科學(xué)探

7、索、工程設(shè)計驗證的重要手段。科學(xué)工作流(ScientificWkflow)[1]借鑒傳統(tǒng)工作流技術(shù)，可以自動化科學(xué)任務(wù)的編排、執(zhí)行、監(jiān)控以及追蹤，支持科學(xué)工作分布協(xié)同和資源共享?？茖W(xué)工作流是數(shù)據(jù)驅(qū)動的，前后序子任務(wù)之間存在大量的數(shù)據(jù)傳輸，具有計算密集、數(shù)據(jù)密集等區(qū)別于傳統(tǒng)工作流的特點[2]?？茖W(xué)工作流調(diào)度問題研究如何利用計算資源最優(yōu)地完成一個由一組彼此之間存在數(shù)據(jù)關(guān)聯(lián)的子任務(wù)，不同約束條件和用戶需求構(gòu)成不同的組合優(yōu)化問題，其中完工時間和

8、費用是用戶最為關(guān)心的兩個性能指標。分布式系統(tǒng)下工作流的時間費用優(yōu)化調(diào)度，實質(zhì)是一個NPhard問題[3]，對于這類大規(guī)模復(fù)雜問題，利用啟發(fā)式算法能夠獲得較好的性能。文獻[4]利用列生成技術(shù)給出一種工作流上下界求解方法，并用最大收益規(guī)則對列生成算法得到的初始解做改進，文獻[56]使用不同優(yōu)先級規(guī)則對調(diào)度方案進行迭代改進，個體資源的性能差異較大時，調(diào)度結(jié)果受優(yōu)先級規(guī)則選擇的影響很大；截止期分解方法[711]按工作流模型結(jié)構(gòu)對子任務(wù)分層，將截

9、止期按比例分解到各層，通過優(yōu)化各層的局部費用最終得到全局較優(yōu)解。文獻[12]證明工作流劃分策略并不優(yōu)于fullgraph調(diào)度，尤其對不平衡工作流。文獻[13]用相對效費比算法解決截止期約束下的網(wǎng)格工作流費用優(yōu)化問題，對初始調(diào)度方案不斷調(diào)整，當方案完工時間小于截止期時，用時間換成本，當方案完工時間超過截止期時，用成本換時間，能夠得到更精確的結(jié)果。這些研究沒有考慮子任務(wù)存在的通信時間與花費，文獻[14]假設(shè)子任務(wù)間的數(shù)據(jù)傳輸時間固定、傳輸費

10、用為0，采用部分關(guān)鍵路徑法對截至期進行分解并選擇滿足截至期約束的最便宜資源以優(yōu)化費用；CostGradient算法[15]假定子任務(wù)間的數(shù)據(jù)傳輸成本固定，子任務(wù)選擇不同節(jié)點時計算成本、時間（含計算時間和數(shù)據(jù)傳輸時間）嚴格負相關(guān)，用成本梯度因子來描述關(guān)鍵任務(wù)資源的時間成本差異，可快速地找到最優(yōu)或次優(yōu)服務(wù)，該算法缺陷在于每當資源選擇時導(dǎo)致關(guān)鍵路徑變化，都必須對新入關(guān)鍵任務(wù)的候選資源進行排序，適用范圍受到嚴格限制。針對異構(gòu)分布式環(huán)境下科學(xué)工作

11、流的時間費用優(yōu)化問題，本文提出任務(wù)配置圖描述工作流資源模型，采用文獻[16]的任務(wù)資源分配圖思想作為工作流調(diào)度模型；基于文獻[13]的相對效費比（RelativeTimeCostRateRTCR）思想，兼顧考慮計算和數(shù)據(jù)傳輸?shù)臅r間成本，提出一種啟發(fā)式調(diào)度算法。任務(wù)配置圖能夠統(tǒng)一建模資源節(jié)點、資源節(jié)點之間的關(guān)聯(lián)以及子任務(wù)、子任務(wù)之間的數(shù)據(jù)關(guān)聯(lián)，避免共享資源訪問沖突；基于相對效費比的啟發(fā)式算法能夠合理地篩選候選資源、優(yōu)化費用。模擬結(jié)果驗證了

12、算法的層網(wǎng)絡(luò)節(jié)點與第層上的，均有直接網(wǎng)絡(luò)連接，第iipj1u2u層上的，與第層的也均有網(wǎng)絡(luò)連接。將子任務(wù)j1u2ukkq1j從節(jié)點遷移到節(jié)點時任務(wù)資源分配圖變?yōu)門RAG’，則相1u2u對效費比是任務(wù)資源分配圖變化后總體成本變化與(())112rjuu完工時間變化之比，即：((111111111211212111121111(11111111121121211111(())112ccccccCPCPjuiijujukkjuiijujukk

13、pqpqjujuikikccccccCPjuiijujukkjuiijujukkpqpqjikikrjuu?????????????????????????且TRAG)=TRAG)且TRAG(1112011111111121121211111(111111111211212111CPujuccccccjuiijujukkjuiijujukkpqpqikikccccccjuiijujukkjuiijujukpqpiki??????????

14、?????????)=TRAG)(11))11otherwise((1211kqkCPCPjuju??????????????????TRAG)TRAG)其中表示子任務(wù)分配到伙伴時TRAG的關(guān)鍵路徑長(CPju?TRAG)ju度。相對效費比體現(xiàn)了整個工作流在其他子任務(wù)調(diào)(())112rjuu度不變時，子任務(wù)從第層上的網(wǎng)絡(luò)節(jié)點變換到節(jié)點1jj1u2u時調(diào)度方案的成本時間變化。，計算節(jié)點的變化(())0112rjuu?導(dǎo)致的總體時間變化和總

15、體成本變化是相同的，選擇其中時間減少的候選伙伴，可以同步降低總體成本。時，(())112rjuu???計算節(jié)點的變換能使總體成本增加而關(guān)鍵路徑長度不變；，計算節(jié)點的變化導(dǎo)致的關(guān)鍵路徑時間變化和總(())0112rjuu?體成本變化是相異的，選擇使關(guān)鍵路徑長度增加的計算節(jié)點，可以降低成本，選擇成本增加的計算節(jié)點，可以減少時間，且相對效費比值越大，效果越顯著。時，計算節(jié)點(())112rjuu??的變換會導(dǎo)致總體成本減少而總體時間不變。工作

16、流調(diào)度就是圍繞給定的截止期，在任務(wù)配置圖上不斷構(gòu)建最優(yōu)任務(wù)資源分配圖的過程。在任何時候，都應(yīng)當無條件選擇相對效費比為負值且關(guān)鍵路徑長度減少或相對效費比為的子任務(wù)的計算節(jié)點進行調(diào)整；當完工時間低于截止期?時，選擇且有最大正值相對費效比且關(guān)鍵路徑長度增加的子任務(wù)進行調(diào)整；當完工時間超過截止期時，選擇最小正值相對費效比且關(guān)鍵路徑長度減少的子任務(wù)進行調(diào)整。定理定理1對于子任務(wù)的任意候選節(jié)點、，如果1j1u2u且(())0112rjuu?；或者1

17、1111111121121211111ccccccjuiijujukkjuiijujukkpqpqikik?????????且；或者且(())0112rjuu?((1112CPCPjuju??TRAG)TRAG)(())112rjuu??，則最11111111121121211111ccccccjuiijujukkjuiijujukkpqpqikik?????????優(yōu)調(diào)度方案中子任務(wù)的中選節(jié)點必然是而不是節(jié)點。1j2u1u證明：不失一

18、般性，考慮任意子任務(wù)的候選節(jié)點的時間成本1j（含數(shù)據(jù)傳輸），可以構(gòu)成一個時間成本坐標圖（見圖1）。（1）且(())0115rjuu?，的15115151111111111111ccccccjuiijujukkjuiijujukkpqpqikik?????????1u時間成本均低于，優(yōu)于；同理優(yōu)于；、優(yōu)5u1u5u2u8u1u2u于；9u（2）且，、的成本相等，(())0113rjuu?((1311CPCPjuju??TRAG)TRAG)

19、1u3u的時間低于，優(yōu)于；1u3u1u3u（3）且(())142rjuu??，、14114141121121211111ccccccjuiijujukkjuiijujukkpqpqikik?????????2u的時間相等，但成本低于，優(yōu)于；4u2u4u2u4u（4），，，(())0116rjuu?(())0117rjuu?(())0126rjuu?，（）和（）都滿足時間越(())0127rjuu?1u6u2u1u7u2u長，成本越低。顯

20、然，結(jié)論成立。R3R1costtimeu7u1u3u6u2u5u4R2u8u9圖1子任務(wù)的時間成本坐標圖Fig1Time&costcodinatediagramofsubtasks引理引理1對于子任務(wù)的任意候選節(jié)點、，1j??ct111u??ct222u，節(jié)點集不可能優(yōu)cctt1212??????????uct|ttccuct|ttccc11212??????于或。1u2u證明：證明：根據(jù)定理1，優(yōu)于R1區(qū)域任意節(jié)點；優(yōu)于R3區(qū)1u2u