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

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

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

3、置圖；任務(wù)資源分配圖；相對(duì)效費(fèi)比中圖法分類號(hào)：中圖法分類號(hào)：TP393文獻(xiàn)標(biāo)識(shí)碼：文獻(xiàn)標(biāo)識(shí)碼：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ī)模計(jì)算資源和大容量存儲(chǔ)設(shè)備的計(jì)算型科學(xué)實(shí)驗(yàn)成為科學(xué)探

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

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

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

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

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

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

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

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

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

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

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

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

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

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