異構分布式環(huán)境下協(xié)作任務的調度算法

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

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

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

4、ntificwkflowsarequitecommonindistributedcomputingenvironmentsconsideringtheinterconnectedisomericphysicalresourcestheintensivedatatransferbetweensubtasksanimprovedheuristicbasedonrelativetimecostrate(RTCR)isproposed.Firs

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

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

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

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

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

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

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

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

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

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

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

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

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

18、般性，考慮任意子任務的候選節(jié)點的時間成本1j（含數(shù)據(jù)傳輸），可以構成一個時間成本坐標圖（見圖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、然，結論成立。R3R1costtimeu7u1u3u6u2u5u4R2u8u9圖1子任務的時間成本坐標圖Fig1Time&costcodinatediagramofsubtasks引理引理1對于子任務的任意候選節(jié)點、，1j??ct111u??ct222u，節(jié)點集不可能優(yōu)cctt1212??????????uct|ttccuct|ttccc11212??????于或。1u2u證明：證明：根據(jù)定理1，優(yōu)于R1區(qū)域任意節(jié)點；優(yōu)于R3區(qū)1u2u