基于期限約束與關(guān)鍵路徑的云工作流調(diào)度

劉雨瀟, , ,

(湖北文理學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,湖北 襄陽 441053)

0 概述

云計(jì)算可以融合大規(guī)模計(jì)算能力應(yīng)用于實(shí)際問題求解,如工業(yè)、醫(yī)療、商業(yè)和科學(xué)計(jì)算等領(lǐng)域。就調(diào)度而言,以上領(lǐng)域的應(yīng)用通常涉及復(fù)雜且多階段的操作處理過程,即工作流模式[1]。云計(jì)算正是通過其彈性的資源提供模式及即付即用的資源支付方式,使得各領(lǐng)域下的工作流任務(wù)可以高效完成,類似Globus Galaxies平臺[2]的云工作流應(yīng)用正使得云計(jì)算環(huán)境成為構(gòu)建科學(xué)工作流調(diào)度與分析的主流方法。

將工作流調(diào)度至可用資源,同時滿足任務(wù)依賴關(guān)系及用戶定義的相關(guān)服務(wù)質(zhì)量(Quality of Service,QoS)約束即為工作流調(diào)度問題,通常為NP-完全問題。云資源上的工作流調(diào)度包括2個階段:資源提供與任務(wù)調(diào)度[3]。資源提供階段旨在決定任務(wù)所需資源的類型和數(shù)量,并預(yù)留至工作流執(zhí)行。工作流任務(wù)調(diào)度階段旨在決定任務(wù)最優(yōu)執(zhí)行序列和滿足用戶與工作流約束的任務(wù)部署[4]。目前的研究工作多集中于第二階段,即對于預(yù)定義的資源池(通常為同質(zhì)資源),以最小化工作流執(zhí)行時間為目標(biāo),未考慮資源使用代價。

本文提出一種基于期限約束與關(guān)鍵路徑的云工作流調(diào)度算法,用于動態(tài)云資源提供環(huán)境中的調(diào)度優(yōu)化。作為一種線性啟發(fā)式調(diào)度方法,該算法包括2個階段:任務(wù)優(yōu)先級確定和任務(wù)分配。第1個階段為各個工作流任務(wù)分配升秩/降秩值,并基于秩值和對任務(wù)進(jìn)行調(diào)度排序;第2個階段則尋找最優(yōu)執(zhí)行資源。本文通過兩階段的工作流調(diào)度,實(shí)現(xiàn)期限約束下工作流執(zhí)行代價的最小化。

1 相關(guān)工作

在獨(dú)立型包任務(wù)與依賴型工作流任務(wù)調(diào)度領(lǐng)域中,常見算法有啟發(fā)式算法、搜索算法和元啟發(fā)式算法。任務(wù)至資源間的分配可劃分為調(diào)度階段和提供階段。傳統(tǒng)的GAIN算法[5]可歸類為純?nèi)蝿?wù)調(diào)度階段的算法,而DRIVE算法[6]更側(cè)重于資源提供階段。僅考慮某一階段的優(yōu)化通常較適用于傳統(tǒng)的分布式計(jì)算環(huán)境,而云調(diào)度系統(tǒng)則同時包含了調(diào)度與提供2個階段。

工作流調(diào)度算法有2個主要的分類:盡力服務(wù)調(diào)度與QoS約束調(diào)度[7]。盡力服務(wù)調(diào)度算法的目標(biāo)是最小化工作流執(zhí)行跨度makespan,如HEFT算法[8]、Suffrage算法[9]、Min-Min算法[9]和Max-Min算法[9]等,這類算法通常忽略執(zhí)行代價因素,并不符合云資源的使用特征。QoS約束調(diào)度算法主要是在滿足用戶定義的相關(guān)約束的條件下優(yōu)化QoS參數(shù),如考慮預(yù)算約束算法[10]和考慮期限約束算法[11]。相比盡力服務(wù)調(diào)度算法,QoS約束調(diào)度算法更適應(yīng)于現(xiàn)實(shí)世界中科學(xué)工作流的應(yīng)用特征。然而,該類算法在約束條件和優(yōu)化較多時,會因較高的時間復(fù)雜度而不具實(shí)用性。

元啟發(fā)式算法是解決多約束調(diào)度的常用方法,如遺傳算法GA[12]、蟻群優(yōu)化算法ACO[13]和粒子群優(yōu)化算法PSO[14-15]等隨機(jī)搜索算法。該類算法可以通過種群初始化和大量解空間,以較高的時間代價求解云環(huán)境中的有效調(diào)度解。然而,該類算法尋找可行調(diào)度解時的開銷會隨著工作流規(guī)模的增加而增大,因此,在面對復(fù)雜大規(guī)模的實(shí)時工作流調(diào)度時效率不高。

在與本文類似的其他相關(guān)研究中,文獻(xiàn)[16]提出一種基于局部關(guān)鍵路徑的調(diào)度算法IC-PCP,算法目標(biāo)是滿足截止時間約束下最小化執(zhí)行代價。該算法將處于局部關(guān)鍵路徑的所有任務(wù)優(yōu)先調(diào)度至費(fèi)用最低的資源上,避免每個PCP上的通信代價,但算法忽略了資源的啟動和部署時間。文獻(xiàn)[17]在IC-PCP算法的基礎(chǔ)上,提出增強(qiáng)算法EIPR,利用資源預(yù)分配空閑時間和預(yù)算盈余進(jìn)行任務(wù)復(fù)制,以降低代價。然而,該算法會因?yàn)槿蝿?wù)復(fù)制增加用戶代價。文獻(xiàn)[18]提出一種分割平衡時間調(diào)度算法PBTS,在滿足期限約束的同時最小化執(zhí)行代價,算法主要通過估算所需資源的最小數(shù)量最小化執(zhí)行代價。文獻(xiàn)[19]提出一種滿足給定預(yù)算和截止時間約束的最大化工作流執(zhí)行數(shù)量的算法。然而,與本文算法相比,該算法僅考慮了一種資源類型,本文則考慮了多類型的資源使用實(shí)例。文獻(xiàn)[20]提出一種滿足期限約束的動態(tài)代價最小化算法JIT,將管道任務(wù)集合并為單個任務(wù)以降低協(xié)作任務(wù)間的數(shù)據(jù)通信代價,但該算法并未優(yōu)化目標(biāo)資源尋找過程。

2 問題模型與定義

本文以有向無循環(huán)圖(Directed Acyclic Graph,DAG)表示工作流,定義為G=(T,E)。其中:T表示圖的節(jié)點(diǎn),即任務(wù)集;E表示圖的有向邊,即任務(wù)間的依賴關(guān)系集;邊ei,j∈E表示任務(wù)ti與tj間的有向邊,即執(zhí)行順序約束,僅當(dāng)完成任務(wù)ti并接收ti的所有數(shù)據(jù)后,才開始執(zhí)行tj,此時,ti稱為tj的直接前驅(qū)或父任務(wù),tj稱為ti的直接后繼或子任務(wù)。在工作流DAG中,每個任務(wù)可擁有一個或多個父任務(wù)或子任務(wù),僅當(dāng)ti的所有父任務(wù)完成后,ti才可以開始執(zhí)行。若任務(wù)沒有任一父任務(wù),則稱該任務(wù)為DAG的入口任務(wù)(entry task);若任務(wù)沒有任一子任務(wù),則稱該任務(wù)為DAG的出口任務(wù)(exit task)。若工作流DAG擁有多個入口或出口任務(wù),為了確保DAG僅有單個輸入與輸出路徑,通常增加2個傀儡任務(wù)作為入口任務(wù)tentry和出口任務(wù)texit,且傀儡任務(wù)的執(zhí)行代價及與其他任務(wù)間的通信數(shù)據(jù)均為0。

在云環(huán)境中調(diào)度工作流時,用戶通常會提供相應(yīng)的QoS約束,本文考慮工作流執(zhí)行的期限約束Duser和執(zhí)行代價cost,優(yōu)化目標(biāo)是在滿足期限約束的同時,追求工作流執(zhí)行代價的最小化,形式化為:

其中,makespan表示整個工作流的執(zhí)行時間。

3 WS-DCCP算法設(shè)計(jì)

3.1 任務(wù)優(yōu)先級確定

將所有工作流任務(wù)根據(jù)并行程度和同步需求劃分為不同的邏輯層次(level)。為了最大化任務(wù)的并行程度,在劃分任務(wù)分層時,考慮同一層次中的任務(wù)間不存在依賴性,從而使每一層次可考慮為包括獨(dú)立任務(wù)集的包任務(wù)。定義一種向下分層法對任務(wù)進(jìn)行分層,即定義任務(wù)ti的分層為任務(wù)ti至出口任務(wù)之間路徑的邊的最大數(shù)量,如圖1所示。

圖1 工作流DAG

在圖1中,邊上的值表明任務(wù)間的通信時間(代價),分層表明任務(wù)所處的任務(wù)包(Bag of Tasks,BoT)。對于出口任務(wù),其分層恒為1。對于其他任務(wù),分層計(jì)算方式為:

其中,succ(ti)表示任務(wù)ti的直接后繼集,levelnum(ti)表示任務(wù)ti所在層數(shù)。

根據(jù)任務(wù)分層,將所有擁有相同分層的任務(wù)組成任務(wù)分層集合TLS,即:

TLS(l)={ti|levelnum(ti)=l}

(3)

其中,l表示分級數(shù),且l∈[1,2,…,levelnum(tentry)]。

3.1.1 正比例期限重分配

任務(wù)分層后,需要將工作流期限D(zhuǎn)user以正比例方式在各個分層上進(jìn)行重分配。令levelsub-deadline表示單個分層的子期限。為滿足全局期限D(zhuǎn)user的約束,需要確保單個分層中每個任務(wù)在其分配的子期限內(nèi)完成。

首先,定義每個分層l的初始子期限估算值為:

在式(4)中,ECT(ti)為任務(wù)ti在所有資源上的最早完成時間,定義如下:

(5)

其中,pred(ti)表示任務(wù)ti的直接前驅(qū)集,exemin(ti)表示任務(wù)ti的最小執(zhí)行時間,ACTi,k表示任務(wù)ti與其父任務(wù)tk間的平均通信時間,ltk表示父任務(wù)ti的分層。由于入口任務(wù)tentry沒有父任務(wù),因此ECT(tentry)=0。

式(4)表明,一個分層中所有任務(wù)的最大ECT可視為該分層的全局完成時間估算值,該時間可作為所處分層中所有任務(wù)并行執(zhí)行時要求的絕對最小完成時間。

然后,基于每個分層的期限長度,將以上比例加至每個分層中:

(7)

顯然,擁有越長任務(wù)的分層將得到越長的期限分配。

3.1.2 約束關(guān)鍵路徑

定義1(關(guān)鍵路徑) 工作流DAG中入口任務(wù)至出口任務(wù)間的最長路徑稱為關(guān)鍵路徑(Critical Path,CP)。

定義2(關(guān)鍵路徑的長度) 表示工作流DAG的關(guān)鍵路徑上任務(wù)的計(jì)算時間與通信時間之和,即調(diào)度工作流的時間下限。

定義3(約束關(guān)鍵路徑) 僅包括就緒任務(wù)的任務(wù)集構(gòu)成的路徑稱為約束關(guān)鍵路徑(Constrainted Critical Path,CCP)。

定義4(就緒任務(wù)) 若某任務(wù)的所有父任務(wù)已經(jīng)執(zhí)行,且所有數(shù)據(jù)均已接收,則稱該任務(wù)為就緒任務(wù)。

傳統(tǒng)方法基于升秩和降秩的方式尋找工作流DAG的所有CCP。任務(wù)ti的升秩表示從任務(wù)ti至texit間的關(guān)鍵路徑的長度,定義為:

其中,AETi表示任務(wù)ti的平均執(zhí)行時間,ACTi,j表示任務(wù)ti的平均通信時間。從式(8)可以看出,任務(wù)的升秩需要從出口任務(wù)開始計(jì)算,然后遞歸計(jì)算至工作流DAG的入口任務(wù)。對于出口任務(wù)texit:

rankup(texit)=AETexit

(9)

任務(wù)的降秩需要從入口任務(wù)開始計(jì)算,然后遞歸計(jì)算至工作流DAG的出口任務(wù),定義為:

(10)

同時,有:

rankdown(tentry)=0

(11)

rankdown(ti)表示任務(wù)tentry至任務(wù)ti的最長距離,但不包括任務(wù)本身的計(jì)算時間,而rankup(ti)則表示任務(wù)ti至texit間關(guān)鍵路徑的長度,包括任務(wù)本身的計(jì)算時間。

WS-DCCP算法對任務(wù)升秩與降秩計(jì)算方式進(jìn)行改進(jìn),如式(12)和式(13)所示。

(12)

rankdown(tk))

(13)

與傳統(tǒng)方法不同,改進(jìn)升秩與降秩計(jì)算任務(wù)的前驅(qū)或后繼任務(wù)的通信時間總量而不是選擇其中的最大值。通過這種方式,可以使得擁有更高出度或入度的任務(wù)擁有更高的優(yōu)先級,從而使得該類任務(wù)優(yōu)先被執(zhí)行,且在下一條約束關(guān)鍵路徑CCP上的更多任務(wù)可被置為就緒任務(wù)。

同時,WS-DCCP算法通過任務(wù)的升秩與降秩之和尋找所有工作流DAG的關(guān)鍵路徑:

ranksum=rankup+rankdown

(14)

首先,基于任務(wù)的ranksum值對所有任務(wù)進(jìn)行排序;然后,將擁有最高ranksum值的任務(wù)選擇為第一條關(guān)鍵路徑。第一條關(guān)鍵路徑上的所有任務(wù)標(biāo)識為已訪問任務(wù),以同樣的方式,可以找到工作流的所有關(guān)鍵路徑。該過程的執(zhí)行步驟如算法1所示。

算法1關(guān)鍵路徑查找算法

輸入工作流G=(T,E)

輸出關(guān)鍵路徑

1.procedureFindCP(DAG G)

2.for all task ti∈G do//遍歷工作流的所有任務(wù)

3.calculate rankup,rankdownand ranksum//計(jì)算各任務(wù)秩值

4.end for

5.CPlist←?//初始化關(guān)鍵路徑列表為空

6.while there is an univisited task in G do//尋找未訪問任務(wù)

7.ti←biggest ranksum//尋找最大秩值和

8.CP←?//置關(guān)鍵路徑為空

9.while tiis not null do

10.add tito CP//添加任務(wù)ti至關(guān)鍵路徑

12.end while

13.add CP to CPlist//添加關(guān)鍵路徑至關(guān)鍵路徑列表

14.end while

15.end procedure

3.1.3 算例說明

本節(jié)以一個實(shí)例,分別說明傳統(tǒng)升秩與降秩方法和WS-DCCP算法的改進(jìn)秩值方法尋找約束關(guān)鍵路徑CCP的不同?？紤]圖1所示的工作流結(jié)構(gòu),邊上數(shù)值代表任務(wù)間的數(shù)據(jù)通信時間,每個任務(wù)的平均計(jì)算時間AETi、升秩值rankup、降秩值rankdown以及升降秩值之和ranksum如表1所示。

表1 各任務(wù)計(jì)算時間、標(biāo)準(zhǔn)升降秩及其和

首先,根據(jù)選取任務(wù)ranksum最高的原則,可以得到第一條關(guān)鍵路徑為t1→t2→t5→t10→t12;然后,剔除已訪問的第一條關(guān)鍵路徑中的任務(wù),以同樣的ranksum最高原則,可依次得到其他關(guān)鍵路徑;最后,需要通過遍歷關(guān)鍵路徑CP,以循環(huán)方式尋找約束關(guān)鍵路徑CCP。在第1條CP中,僅有任務(wù)t1、t2可就緒,其他任務(wù)均無法就緒,則第1條CCP為t1→t2。例如:考慮第1條關(guān)鍵路徑中的任務(wù)t5,該任務(wù)未添加至該CCP,由于其父任務(wù)之一t3仍未添加至任意CCP中。當(dāng)無法在第1條CP中找到更多的就緒任務(wù)時,即可考慮通過第2條CP建立新的CCP。在第2條CP中,由于任務(wù)t3的唯一父任務(wù)t1已經(jīng)添加至第1條CCP中,則任務(wù)t3為就緒任務(wù)。依此類推,可知第2條CCP包括3個任務(wù):t3→t6→t9。從第2條CP中排除任務(wù)t11的原因在于它的一個父任務(wù)t7仍未添加至任一CCP中。同理,其他的CCP可利用剩余的CP進(jìn)行構(gòu)造。通過上述過程得到的CP與CCP如表2所示。

表2 通過標(biāo)準(zhǔn)升降秩得到的CP與CCP

基于同樣的CP和CCP構(gòu)造方法,改進(jìn)的任務(wù)升秩與降秩值及得到的CP和CCP如表3和表4所示,其中,AETi表示每個任務(wù)的平均計(jì)算時間,rankup表示改進(jìn)升秩值,rankdown表示改進(jìn)降秩值,ranksum表示升降秩值之和。

表3 各任務(wù)計(jì)算時間、改進(jìn)升降秩及其和

表4 通過改進(jìn)升降秩得到的CP與CCP

3.2 任務(wù)分配

任務(wù)分配階段旨在尋找最佳資源執(zhí)行CCP上的任務(wù)集。同時,為了避免增加通信代價,WS-DCCP算法規(guī)定一條約束關(guān)鍵路徑上的所有任務(wù)均執(zhí)行于同一資源。任務(wù)分配的優(yōu)化目標(biāo)是在滿足約束關(guān)鍵路徑子期限的情況下最小化工作流執(zhí)行代價。

令ECT(CCPi,pj)為當(dāng)前約束關(guān)鍵路徑CCPi在資源pj上的最早完成時間,在單個任務(wù)的情況下,其值由式(5)決定。分層的子期限估算與當(dāng)前CCP在資源pj上的最早完成時間之差為:

其中,levelsub-deadline為分配至包含當(dāng)前CCP中最后任務(wù)ti的分層的子期限。如果當(dāng)前CCP的最早完成時間超過分層子期限,即:

則表明式(15)可能為負(fù)值。同時,令CostCCPi,pj表示在資源pj上執(zhí)行當(dāng)前CCP上所有任務(wù)時的代價。

算法2給出了尋找最佳目標(biāo)資源的執(zhí)行過程。該過程需要考慮以下3種情況:

情況1由于云資源使用是基于賬單數(shù)量的付費(fèi)模式,以Amazon EC2為例,使用時間未達(dá)到1 h均按1 h間隔付費(fèi),如果任務(wù)可執(zhí)行于還剩余使用賬單時間的資源上,其執(zhí)行代價為0。因此,在分配資源時,算法優(yōu)先選擇還剩余空閑付費(fèi)間隔的資源,即:算法的第1步是在確保CCP的最早完成時間不超過分層子期限的情況下,優(yōu)先考慮無代價的資源執(zhí)行CCP,然后,選擇最早完成時間最小的資源(即最快資源)。

情況2如果無法找到滿足情況1的資源,需要提供一個新資源,此時算法在資源集中搜索滿足分層子期限約束并且最低價的資源進(jìn)行分配。

情況3對于較嚴(yán)格的期限約束,可能存在無法找到滿足任務(wù)所在分層子期限的資源(即式(15)恒為負(fù)值)。如果存在某個CCP滿足該條件,并不一定表明無法滿足全局期限約束,而僅僅表明會違背子期限約束。此時,算法選擇最佳性能的可用資源。

算法2尋找最佳資源算法

輸入關(guān)鍵路徑與子期限

輸出代價最小化的最優(yōu)資源

1.procedureResourceSelection(CCPi)

2.F←find all resources that have zero cost for CCPi

3.M←find all resources that can meet sub-deadline for CCPi

4.if (F∩M)//情況1

5.SelectResource←minECT(F∩M)

6.else if(M) then//情況2

7.SelectResource←minCost(M)

8.else//情況3

9.SelectResource←minCost(all resources)

10.end if

11.end procedure

3.3 算法時間復(fù)雜度

考慮任務(wù)數(shù)量為n的工作流DAGG=(T,E),假設(shè)DAG為全連通,則有向邊的最大數(shù)量為n(n-1)/2,處理所有任務(wù)及其依賴關(guān)系的時間復(fù)雜度為O(n2)。對于WS-DCCP算法的第一階段,需要將所有n個就緒任務(wù)在p個可用資源上進(jìn)行遍歷,其時間復(fù)雜度為O(np),而選擇所有工作流任務(wù)的時間復(fù)雜度為O(n2p)。對于WS-DCCP算法的第二階段,由于前一階段的所選任務(wù)需要在所有可用資源上進(jìn)行計(jì)算,其時間復(fù)雜度為O(p)。因此為任務(wù)選擇資源的時間復(fù)雜度為O(np)。另外,在計(jì)算關(guān)鍵路徑時需要計(jì)算任務(wù)的升秩和降秩值,其時間復(fù)雜度為O(n2p)。綜上,WS-DCCP算法的時間復(fù)雜度為O(n2+n2p+np+n2p)=O(n2p)。

4 仿真實(shí)驗(yàn)

本節(jié)對算法性能進(jìn)行仿真評估,構(gòu)建2種形式的WS-DCCP算法:基于式(8)、式(10)的標(biāo)準(zhǔn)升秩與降秩算法WS-DCCP(SR),基于式(12)、式(13)的改進(jìn)升秩與降秩算法WS-DCCP(MR)。另外,源于優(yōu)化機(jī)制的相似性,選擇IC-PCP[16]和JIT[20]作為基準(zhǔn)算法。WS-DCCP(MR)同樣使用逐層方式尋找關(guān)鍵路徑,即:首先選擇第一分層所有任務(wù)中擁有最高秩值的任務(wù),然后在第二分層被選任務(wù)的子任務(wù)中,選擇擁有最高秩值的任務(wù)。重復(fù)該過程,直到達(dá)到最后分層,找到所有其他關(guān)鍵任務(wù),即可得到第1條關(guān)鍵路徑。第2條關(guān)鍵路徑重新回到剔除第1條關(guān)鍵路徑后的子DAG中重新尋找。

4.1 實(shí)驗(yàn)環(huán)境與參數(shù)

通過仿真平臺CloudSim[21]構(gòu)造一個云數(shù)據(jù)中心和6種資源類型,資源的詳細(xì)參數(shù)參考Amazon EC2設(shè)置,如表5所示。資源間的平均帶寬參數(shù)參考Amazon AWS設(shè)置為20 MB/s。EC2單元的計(jì)算能力以每秒百萬浮點(diǎn)操作次數(shù)MFLOPS進(jìn)行度量。在實(shí)際的云計(jì)算環(huán)境中進(jìn)行資源分配時,由于諸如時延、操作系統(tǒng)執(zhí)行、資源類型、數(shù)據(jù)中心地理位置和資源請求量等因素的存在,可能導(dǎo)致資源啟動時存在時延,因此,為了滿足實(shí)際情況需求,仿真實(shí)驗(yàn)中為資源設(shè)置97 s的啟動時間。

表5 資源參數(shù)

同時,為了評估算法處理真實(shí)負(fù)載的性能,實(shí)驗(yàn)中使用4種現(xiàn)實(shí)科學(xué)工作流進(jìn)行測試,包括CyberShake、Montage、LIGO和SIPHT,利用Pegasus工作流產(chǎn)生器創(chuàng)建這4種合成工作流結(jié)構(gòu),同時將工作流規(guī)模設(shè)置為200個任務(wù)。

另外,為了評估算法的敏感性,實(shí)驗(yàn)設(shè)置不同的期限約束,其約束范圍從較嚴(yán)格變化至較寬松。為了得到期限間隔,計(jì)算2種基準(zhǔn)調(diào)度的長度:最快調(diào)度與最慢調(diào)度。

1)如果工作流的關(guān)鍵路徑上的所有任務(wù)均執(zhí)行于最快資源類型上,即可得到最快調(diào)度長度:

2)如果工作流的關(guān)鍵路徑上的所有任務(wù)均執(zhí)行于最慢資源類型上,即可得到最慢調(diào)度長度:

基于FS和SS,將工作流的期限定義為:

Duser=FS+α×(SS-FS)

(19)

其中,α表示期限因子,α∈[0.1,1],α以步長0.1進(jìn)行遞增,其值越小,期限約束越嚴(yán)格,其值越大,期限約束越寬松。

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

為了比較算法的代價,引入滿足期限的失效代價,即考慮任務(wù)執(zhí)行失效對執(zhí)行代價的影響。當(dāng)執(zhí)行結(jié)果無法滿足期限約束時,視為一次失效。引入一個權(quán)重分配至算法返回的平均代價,令k表示滿足期限約束的成功調(diào)度集合,則該權(quán)重代價可定義為:

在式(20)中,Cost(k)表示滿足期限約束的代價(式(1)得到的最小值),SR表示算法的調(diào)度成功率,即滿足調(diào)度期限的仿真實(shí)驗(yàn)次數(shù)與總的仿真運(yùn)行次數(shù)的比率,定義為:

SR=n(k)/nTot

(21)

其中,nTot表示總仿真次數(shù),nTot=50,n(k)為集合k的基數(shù)。將最低價調(diào)度考慮為所有任務(wù)均調(diào)度至最低價資源上執(zhí)行,為了代價標(biāo)準(zhǔn)化處理,算法獲得的權(quán)重代價為代價除以最低價調(diào)度。

圖2顯示了標(biāo)準(zhǔn)化代價的比較結(jié)果?？梢钥闯?在多數(shù)情況下,WS-DCCP算法均擁有比IC-PCP更低的代價。在最嚴(yán)格期限約束下(α=0.1),IC-PCP算法在SIPHT和CyberShake 2種工作流中擁有較低的代價,但在Montage中代價較高,在LIGO中100%失效。同時,對于LIGO和Montage工作流,WS-DCCP算法在多數(shù)時間下能夠以接近IC-PCP一半的代價調(diào)度工作流。此外,在所有工作流中,WS-DCCP(MR)算法在性能上優(yōu)于WS-DCCP(SR)算法,除了CyberShake工作流的最嚴(yán)格期限約束的情況。總體而言,JIT算法降低通信代價的方式較IC-PCP可以降低一定代價,但由于其資源選擇并非最優(yōu),因此在4種工作流中的代價均高于WS-DCCP算法。

圖3顯示了算法調(diào)度成功率的比較結(jié)果?？梢钥闯?除了CyberShake工作流,WS-DCCP算法幾乎可以成功滿足所有期限約束。在最嚴(yán)格期限約束下(α=0.1),IC-PCP算法和JIT算法的調(diào)度成功率表現(xiàn)較差,其中,IC-PCP算法在LIGO工作流中幾乎100%失效,而JIT算法的調(diào)度成功率略高于IC-PCP算法。結(jié)果還表明,WS-DCCP算法對于期限約束遠(yuǎn)沒有IC-PCP算法和JIT算法表現(xiàn)得敏感,這反映WS-DCCP算法擁有比較穩(wěn)定的性能。IC-PCP算法的不穩(wěn)定性部分是由其較高的失效率導(dǎo)致的,源于該算法在選擇資源分配時并沒有做到最優(yōu)選擇。

圖2 算法代價比較

圖3 算法調(diào)度成功率比較

總體來看,WS-DCCP算法雖然無法保證在所有工作流類型和所有程度的期限約束下達(dá)到工作流執(zhí)行代價的最小,但可以在降低代價的情況下仍然擁有更高的調(diào)度成功率,其綜合性能更好,性能也更穩(wěn)定。

5 結(jié)束語

為實(shí)現(xiàn)期限約束下的執(zhí)行代價最小化,本文提出一種基于關(guān)鍵路徑的云工作流調(diào)度算法。通過求解工作流結(jié)構(gòu)的約束關(guān)鍵路徑,并將約束關(guān)鍵路徑上的任務(wù)執(zhí)行于同一資源上,降低資源間的通信代價。同時,設(shè)計(jì)基于改進(jìn)任務(wù)升秩與降秩之和的約束關(guān)鍵路徑求解方法,引入基于任務(wù)秩值與關(guān)鍵路徑的機(jī)制,以降低工作流執(zhí)行代價。實(shí)驗(yàn)結(jié)果表明,本文算法可以在滿足期限約束的同時,降低工作流執(zhí)行代價,提高調(diào)度成功率。下一步研究將集中于多約束條件下的關(guān)鍵路徑求解,如將預(yù)算約束或資源能耗因素考慮在內(nèi),求解多目標(biāo)的工作流調(diào)度優(yōu)化。