基于局部關(guān)鍵路徑與截止期限分配的云工作流調(diào)度算法

蔡艷婧 王 強 程 實

1(南通大學電子信息學院 江蘇 南通 226019)2(江蘇商貿(mào)職業(yè)學院電子與信息學院 江蘇 南通 226001)3(南通大學計算機科學與技術(shù)學院 江蘇 南通 226019)

0 引 言

工作流結(jié)構(gòu)廣泛應用于復雜計算問題建模，云計算特有的按需提供和付即用的定制資源使用方式使其成為調(diào)度工作流的有效方法[1]。與傳統(tǒng)批任務(wù)調(diào)度不同，工作流結(jié)構(gòu)的任務(wù)具有嚴格的邏輯執(zhí)行次序，需要在滿足給定QoS約束的同時，實現(xiàn)與資源間的映射。工作流調(diào)度通常由選擇被調(diào)度任務(wù)和選擇提供實例兩個階段構(gòu)成，兩階段決策對于是否能夠滿足給定約束和全局調(diào)度代價均具有重要影響。傳統(tǒng)工作流調(diào)度方法僅注重執(zhí)行效率/時間，忽略了資源使用的費用，此時的調(diào)度問題在不同資源和不同調(diào)度方案下的執(zhí)行時間和代價均有所不同。因此，同步考慮用調(diào)度時間和代價更加符合云資源的使用環(huán)境。

為了解決期限約束時的工作流調(diào)度代價優(yōu)化問題，本文設(shè)計的調(diào)度方法是將全局期限在所有工作流任務(wù)上進行分割，以得到任務(wù)的子期限，然后在實例提供時僅滿足子期限即可。

1 相關(guān)研究

對于工作流調(diào)度過程的調(diào)度與提供兩個階段[2]，給定資源集，調(diào)度階段的目標是決定任務(wù)執(zhí)行的最優(yōu)序列和與用戶相應約束下的任務(wù)部署[3]；提供階段的目標是為工作流內(nèi)的任務(wù)選擇資源類型和相應資源數(shù)量，并為任務(wù)執(zhí)行預留資源[4-5]。相關(guān)研究中，底向下分層[6](Down-Buttom Level,DBL)和底向上分層[7](Down-top Level,DTL)算法是典型的基于期限分配的啟發(fā)式調(diào)度算法。前者以down-top方式對任務(wù)進行劃分，后者則以top-down方式對任務(wù)進行劃分。由于工作流可以有向無循環(huán)圖建模，故DBL將任務(wù)劃分為不同層次，每個層次包含的任務(wù)不具有依賴性。而DTL將任務(wù)劃分為不同路徑(作為同步任務(wù)或簡單任務(wù)，同步任務(wù)定義為擁有一個以上父任務(wù)或子任務(wù)的任務(wù))。為任務(wù)分配期限時，全局期限以正比于每個層次的最小執(zhí)行時間的方式在各層次間進行分割。然而，在DBL算法，首先需要計算最快實例資源，然后再將期限與估算值之差以均勻分布方式在所有層次間進行分配。文獻[8]提出了DET算法，算法將任務(wù)分為兩種類型：關(guān)鍵和非關(guān)鍵任務(wù)。關(guān)鍵任務(wù)利用動態(tài)規(guī)化進行調(diào)度，非關(guān)鍵任務(wù)則在關(guān)鍵任務(wù)間進行回填式調(diào)度，但該算法忽略了任務(wù)間的通信時間。

文獻[9]提出了云工作流調(diào)度算法PDC，算法將期限以正比于各層次中任務(wù)執(zhí)行時間的方式在層次間進行分割。文獻[6，10]提出了最遲完成時間LFT算法，該算法也是將期限在各任務(wù)間進行分割，并確保工作流在用戶定義期限條件下，執(zhí)行完任務(wù)的最早時間。文獻[10]提出了局部關(guān)鍵路徑算法，算法可以根據(jù)任務(wù)在工作流中所處的局部關(guān)鍵路徑對任務(wù)進行分類，同時，期限根據(jù)定義的路徑進行重分配。然而，算法在每個局部關(guān)鍵路徑PCP執(zhí)行后，需要重新計算最遲完成時間，開銷較大。文獻[6]提出了基于動態(tài)代價最小的聯(lián)合內(nèi)層技術(shù)(Joint Inner Technology，JIT)算法，該算法在期限約束下將聯(lián)合管道任務(wù)集建立為單個任務(wù)，以消除任務(wù)間的數(shù)據(jù)傳輸時間。然而，該算法在任務(wù)執(zhí)行實例的選擇上并非最優(yōu)，有待改進。

2 任務(wù)調(diào)度模型

云工作流模型以有向無循環(huán)圖DAG建模，表示為G(T,E)，T為n個任務(wù){(diào)t1,t2,…,tn}的集合，E為邊集。每條邊ei,j=(ti,tj)表示任務(wù)間的執(zhí)行次序約束，代表ti必須在tj開始前完成執(zhí)行。對于給定的DAG，不存在任一父節(jié)點的任務(wù)稱為入口任務(wù)tentry，不存在任一子節(jié)點的任務(wù)稱為出口任務(wù)texit。由于本文的算法要求應用模型具有單一入口和出口任務(wù)，故可以分別在任務(wù)DAG的開始和結(jié)尾處增加一個傀儡任務(wù)tentry和texit?？苋蝿?wù)的執(zhí)行時間為0，且與其他任務(wù)的連接邊上的權(quán)值也為0。

云資源模型由多個云服務(wù)提供者組成，每一個均可向用戶提供資源。每一個任務(wù)ti可由擁有不同QoS屬性的不同服務(wù)提供者的mi種服務(wù)Si={si,1,si,2,…,si,mi}進行處理。本文關(guān)注的QoS屬性為執(zhí)行時間和代價，服務(wù)代價取決于執(zhí)行時間，即執(zhí)行時間越短，代價越高。令ET(ti,s)表示在服務(wù)s上處理ti的估計執(zhí)行時間，EC(ti,s)表示在服務(wù)s上處理ti的執(zhí)行代價。令TT(ei,j,r,s)和TC(ei,j,r,s)分別表示服務(wù)r(執(zhí)行任務(wù)ti)與服務(wù)s(執(zhí)行任務(wù)tj)間的邊ei,j上的估計數(shù)據(jù)傳輸時間和傳輸代價。

3 算法設(shè)計

3.1 算法實現(xiàn)思路

基于局部關(guān)鍵路徑和截止期限的云工作流調(diào)度算法(Workflow Scheduling Based on Partial Critical Path and Deadline Constraint，WS-PCPDC)包括兩個階段：期限分配與資源選擇。期限分配階段中，全局任務(wù)DAG的截止期限在個體任務(wù)間進行分配，若每個任務(wù)可在其子期限內(nèi)完成，則整個任務(wù)DAG可在截止期限內(nèi)完成。資源選擇階段中，在滿足任務(wù)子期限的同時，為每個任務(wù)選擇最優(yōu)資源完成任務(wù)調(diào)度，實現(xiàn)代價最優(yōu)。

3.2 基本定義

對于每個未調(diào)度任務(wù)ti，令EST(ti)表示任務(wù)ti的最早開始時間，該時間是未考慮實際執(zhí)行該任務(wù)的資源時得到的時間。顯然，無法計算準確的EST(ti)，由于云環(huán)境是異構(gòu)環(huán)境，任務(wù)執(zhí)行時間在不同資源間是變化的。進一步，數(shù)據(jù)傳輸時間也取決于所選資源及資源間的傳輸帶寬。任務(wù)ti的最小執(zhí)行時間MET(ti)和最小傳輸時間可分別定義為：

基于以上定義，最早開始時間可定義為：

式中，pred(ti)表示ti的父節(jié)點任務(wù)。

對于每個未調(diào)度任務(wù)ti，令LFT(ti)為整個任務(wù)DAG在截止時間D內(nèi)保證完成時,任務(wù)ti能夠完成執(zhí)行的最遲時間，則：

對于每個調(diào)度任務(wù)ti，令SS(ti)為執(zhí)行ti的所選資源，AST(ti)為任務(wù)ti在資源上的實際開始時間。

3.3 算法步驟

算法1是WS-PCPDC算法的偽代碼。步驟3添加兩個傀儡節(jié)點至任務(wù)DAG中，步驟4-步驟7計算所需參數(shù)值，步驟8為節(jié)點tentry和texit分配子期限，并在步驟9中將這兩個任務(wù)標記為已分配(assigned)節(jié)點。已分配節(jié)點表明該任務(wù)節(jié)點已經(jīng)分配子期限，未分配子期限的節(jié)點稱為未分配(unassigned)節(jié)點。可以看出，texit的子期限設(shè)置為截止期限D(zhuǎn)，說明出口任務(wù)必須在D內(nèi)完成。步驟10對出口任務(wù)調(diào)用AssignParent算法(分配節(jié)點算法)，該算法的目標是為輸入節(jié)點的所有未分配父節(jié)點分配子期限，從出口任務(wù)texit開始分配即可保證為DAG中的所有任務(wù)分配子期限。因此，AssignParent算法負責在所有任務(wù)間分配全局截止期限。最后，步驟11調(diào)用Planning算法，用于在滿足子期限的情況下為每個任務(wù)選擇執(zhí)行資源。

算法1WS-PCPDC

(1) Procedure ScheduleWorkflow(G(T,E),D)

(2) Request available resource for each task inG

//發(fā)出資源請求

(3) addtentry,texitand their correoponding edges toG

//添加進出口任務(wù)

(4) using Eq.(1) to computeMET(ti) for each task

//為每個任務(wù)計算MET(ti)

(5) using Eq.(2) to computeMTT(ti) for each edge

//為每條邊計算MTT(ti)

(6) using Eq.(3) to computeEST(ti) for each task inG

//為每個任務(wù)計算EST(ti)

(7) using Eq.(4) to computeLFT(ti) for each task inG

//為每個任務(wù)計算LFT(ti)

(8) sub-deadline(tentry)=0,sub-deadline(texit) =D

//為入口出口任務(wù)計算子期限

(9) marktentryandtexitas assigned

//標識入出口任務(wù)已調(diào)度

(10) call function AssignParent(texit)

//調(diào)用AssignParent(texit)

(11) call function Planning(G(T,E))

//調(diào)用Planning(G(T,E))

(12) end procedure

3.4 AssignParent算法

AssignParent算法偽代碼如算法2所示。算法輸入一個已分配節(jié)點，并嘗試分配子期限至其所有父節(jié)點上。AssignParent算法(分配節(jié)點算法)首先需要尋找終止于輸入的未分配節(jié)點的局部關(guān)鍵路徑。

算法2AssignParent

(1) Procedure AssignParents(t)

(2) while (thas an unassigned parent) do

//若t有未調(diào)度父節(jié)點

(3)PCP←null,ti←t

//局部關(guān)鍵路徑置空

(4) while (there exists an unassigned parent ofti) do

//若仍有未調(diào)度父節(jié)點

(5) add CriticalParent(ti) to the beginning ofPCP

//添加任務(wù)的關(guān)鍵父節(jié)點至PCP的隊首

(6)ti←CriticalParent(ti)

//提取當前任務(wù)

(7) call function AssginPath(PCP)

//調(diào)用函數(shù)AssginPath(PCP)

(8) for all (ti∈PCP) do

//每個局部關(guān)鍵路徑上的任務(wù)更新EST和LFT

(9) updateESTfor all unassigned successors ofti

//更新所有未調(diào)度子任務(wù)的EST

(10) updateLFTfor all unassigned predecessors ofti

//更新所有未調(diào)度父任務(wù)的LFT

(11) end procedure

以下定義關(guān)鍵父節(jié)點的概念：

定義1任務(wù)ti的關(guān)鍵父節(jié)點為數(shù)據(jù)到達時間最遲的未分配父節(jié)點，即：滿足下式的ti的父節(jié)點tp：

定義2任務(wù)節(jié)點ti的局部關(guān)鍵路徑為：

1) 若ti不存在任一未分配父節(jié)點，則為空；

2) 若ti存在任一未分配父節(jié)點，則由其關(guān)鍵父節(jié)點tp和tp的局部關(guān)鍵路徑組成。

算法2由輸入節(jié)點開始，沿關(guān)鍵父節(jié)點直到到達沒有未分配父節(jié)點的節(jié)點任務(wù)，以形成一條局部關(guān)鍵路徑。第一次調(diào)用該算法時，由texit開始，向回追溯其關(guān)鍵父節(jié)點，直到到達tentry。因此，算法可以找到穿越整個DAG的全局關(guān)鍵路徑。然后，算法調(diào)用AssignPath算法(分配路徑算法)，該算法接收一條路徑(任務(wù)節(jié)點序列)作為輸入，在任務(wù)的最遲完成時間內(nèi)分配子期限至路徑上的每個節(jié)點上。當子期限分配至任務(wù)后，其未分配后繼節(jié)點的EST和其未分配父節(jié)點的LFT可能發(fā)生改變(根據(jù)式(3)和式(4))。基于此原因，算法需要在下一次循環(huán)中更新路徑上所有任務(wù)的這兩個值。最后，算法通過遞歸調(diào)用AssignParent為局部關(guān)鍵路徑上的每個任務(wù)節(jié)點的父節(jié)點分配子期限。

3.5 AssignPath算法

AssignPath算法接受一條路徑作為輸入，分配子期限至其上的每個任務(wù)節(jié)點。本文設(shè)計三種分配策略，試圖為路徑創(chuàng)建預計調(diào)度方案，并使用算法為路徑上的任務(wù)分配子期限。由于僅是估計調(diào)度方案而非實際方案，故未考慮資源的可用時間。

1) 最優(yōu)策略。該策略試圖尋找在最遲完成時間內(nèi)執(zhí)行路徑上任務(wù)的代價最小調(diào)度，然后利用該最佳調(diào)度分配子期限至路徑上的任務(wù)。策略過程如算法3所示。該算法基于回溯法，從路徑上的第一個任務(wù)開始，向最后一個任務(wù)遍歷，在每一步中為當前任務(wù)選擇下一個更慢的資源，即步驟5。因此，對于每個任務(wù)的資源是從最快至最慢進行檢測。如果沒有可用未檢測資源剩余，或分配當前任務(wù)t至下一個更慢資源s是不可行分配，則算法回溯至路徑的前一任務(wù)，并為其選擇另一資源，即步驟6-步驟8。如果任務(wù)t能夠在其最遲完成時間內(nèi)在資源s上完成，即EST(t)+ET(t,s)≤LFT(t)，則定義為一次可行分配。

步驟9-步驟10中，算法檢測當前任務(wù)是否為路徑上的最后一個任務(wù)，且當前分配是否擁有比最優(yōu)分配更低的代價，若滿足，在步驟11中設(shè)置當前調(diào)度為最優(yōu)best調(diào)度。While循環(huán)結(jié)束后，步驟18檢測是否找到最優(yōu)調(diào)度，由于路徑上某些任務(wù)可能在其LFT內(nèi)得到調(diào)度，所有可能存在最優(yōu)調(diào)度不存在的情形。如果不存在最優(yōu)調(diào)度，則在步驟19中將任務(wù)的EST+MET值作為路徑上的任務(wù)的子期限值分配，否則，根據(jù)最優(yōu)調(diào)度best為路徑path上的所有任務(wù)設(shè)置EST和分配子期限。

最后，可能存在額外時間，即最后一個任務(wù)的LFT與其分配的子期限之間存在差值，可將其添加至路徑上的任務(wù)的子期限上。當該額外時間值小于最小值時，可將其添加至最后一個任務(wù)的子期限上。若該值較大，可以正比于傳輸時間減去執(zhí)行時間的方式將其分配至路徑上的任務(wù)。

算法3Optimized PathAssigning Algorithm(最優(yōu)策略算法)

(1) Procedure AssignPath(Path)

(2) best←null

//最優(yōu)集合先置空

(3)t←first task on the path

//提取當前路徑的第一個任務(wù)

(4) while (t is not null) do

(5)s←next slower service ∈St

//提取下一個最慢的服務(wù)提供者

(6) if (s=assigningtto s is not admissible) then

//若無法分配完成

(7)t←previous task on the path and continue while loop

//繼續(xù)在該路徑上尋找

(8) end if

(9) if (tis the last on the path) then

//若該任務(wù)為路徑上的最后一個任務(wù)

(10) set this schedule as best

//設(shè)置該調(diào)度解為最優(yōu)

(11) end if

(12)t←next task on the path

//提取路徑上的下一任務(wù)

(13) end while

(14) if (best is null) then

//若最優(yōu)集為空

(15) set sub-deadline(t)=EST(t)+MET(t) for all taskston the path

//更新子期限

(16) else

(17) setESTand sub-deadline according to best for all tasks∈path

//以最優(yōu)解為基礎(chǔ)設(shè)置EST和子期限

(18) end if

(19) mark all tasks of the path as assgined

//標記任務(wù)是否調(diào)度

(20) end procedure

2) 代價降低策略。該策略是一種近似最優(yōu)的貪婪方法，即策略試圖以多項式時間尋找一個較優(yōu)解(不一定為最優(yōu)解)。策略首先將最快資源分配至路徑上的每個任務(wù)，顯然該分配是代價最高解。然后，試圖在不超過任一任務(wù)的LFT的情況下，通過分配代價更低(也更慢)的資源至任務(wù)來降低代價。為了決定哪些任務(wù)需要重分配至代價更低的資源，需要計算代價降低率CDR，定義為：

(5)

式中:cs為已分配至任務(wù)ti的當前資源，ns為比當前資源執(zhí)行ti更慢的資源。任務(wù)t在資源s上的總執(zhí)行時間TET(t,s)為在資源s上的執(zhí)行時間+任務(wù)t與其路徑上的父節(jié)點與子節(jié)點間的總傳輸時間(除不存在父/子節(jié)點的第一個和最后一個任務(wù)節(jié)點)。任務(wù)t在資源s上的總執(zhí)行代價TEC(t,s)的定義方式與上類似。

ti的CDR可以衡量一個單位時間的代價可以換來多少執(zhí)行代價的降低。若t*被選擇使得它有最大CDR值，則該任務(wù)是可替換的，即將其分配至下一個更慢資源是一個可行分配。最后，t*的當前資源可更改為下一個更慢資源。過程如算法4所示。

算法4低價降低策略算法

(1) Procedure AssignPath(path)

(2) cur←assign the fastest service to each task of the path

//將最慢服務(wù)分配給路徑上的每個任務(wù)得到一個初始解

(3) computeCDR(ti) for each task of the path by Eq.(5)

//計算任務(wù)CDR(ti)

(4) repeat

(5)t*←null

(6) for all (ti∈path) do

//判定路徑的CDR值的大小

(7) if (CDR(ti)>CDR(t*) andtiis replaceable) then

(8)t*←ti

(9) end if

(10) end for

(11) if (t*is not null) then

(12) update cur by assigningt*to the next slower service

//分配次最慢的服務(wù)器更新cur

(13) updateCDR(t*)

//更新CDR

(14) end if

(15) until (t*is null)

//循環(huán)至集合為空

(16) if (there is an inadmissible assignment in cur) then

//若在cur集合中存在一個不允許的調(diào)度解

(17) set sub-deadline(t)=EST(t)+MET(t) for all tasks t on the path

//更新子期限

(18) else

(19) setESTand sub-deadline according to cur for all tasks∈path

//以最優(yōu)解為基礎(chǔ)設(shè)置EST和子期限

(20) end if

(21) mark all tasks of the path as assgined

//標記調(diào)度任務(wù)

3) 公平策略。該策略以公平的方式為路徑上的任務(wù)節(jié)點分配子期限。首先，策略將路徑上的每個任務(wù)分配至最慢的資源上。然后，從第一個任務(wù)至最后一個任務(wù)，在不超過任務(wù)的LFT的情況下，策略以下一個更慢資源替換已分配資源。該過程迭代執(zhí)行至無法替換為止。策略過程如算法5所示，最差情況下，repeat-until循環(huán)將執(zhí)行m次，因此，算法時間復雜度為O(lm)。

算法5Fair PathAssigning Algorithm

(1) Procedure AssignPath(Path)

(2) cur←assign the fastest service to each task of the path

//將最慢服務(wù)分配給路徑上的每個任務(wù)得到一個初始解

(3) for all (ti∈path) do

//對于所有路徑上的任務(wù)

(4) if (assigningti→next service is admissible) then

//若將任務(wù)調(diào)度至下一個服務(wù)器可行

(5) update cur by assigningti→next slower service

//更新cur集合

(6) until (no change is done)

//直到無法進一步改進

(7) if (there is an inadmissible assignment in cur) then

//若存在不可行解

(8) set sub-deadline(t)=EST(t)+MET(t) for all tasks t on the path

//更新子期限

(9) else

(10) setESTand sub-deadline according to cur for all tasks∈path

//以最優(yōu)解為基礎(chǔ)設(shè)置EST和子期限

(11) mark all tasks of the path as assgined

//標記已調(diào)度任務(wù)

3.6 Planning算法

Planning算法(規(guī)劃算法)即為算法的第二個階段(資源選擇階段)，其目標是為每個任務(wù)選擇最優(yōu)資源，在確保滿足截止期限的同時，以最小化執(zhí)行代價調(diào)度任務(wù)。在期限分配階段，每個任務(wù)被分配一個子期限。如果可以調(diào)度每個任務(wù)，使得任務(wù)在其分配子期限內(nèi)完成，則整個DAG可在截止期限內(nèi)完成。該階段算法嘗試以貪婪策略通過制定局部最優(yōu)決策創(chuàng)建全局最優(yōu)調(diào)度解。在每個階段中，算法選擇一個就緒任務(wù)，即該任務(wù)的所有父任務(wù)已經(jīng)完成調(diào)度，然后調(diào)度至滿足其子期限的價格最低的資源上執(zhí)行。因此，對于就緒任務(wù)ti的所選資源SS(ti)滿足：

約束條件為：

AST(ti,s)+ET(ti,s)≤sub-deadline(ti)

(6)

式中:ti在s上的實際開始時間AST(ti,s)為ti的父節(jié)點數(shù)據(jù)到達資源s的最遲時間與資源s上可用時槽開始時間的相對大值。

當沒有資源可子期限內(nèi)完成任務(wù)ti時(由于子期限僅是估算調(diào)度，并未考慮資源上的實際可用空閑時間槽)，則選擇完成時間最小的資源SS(ti)，即滿足：

minAST(ti,s)+ET(ti,s)

(7)

Planning算法的偽代碼如算法6所示。

算法6Planning

(1) Procedure Planning(G(T,E))

(2) Queue←tentry

//將入口任務(wù)輸入隊列

(3) while (Queue is not empty) do

//若隊列不為空

(4) t←delete first task from Queue

//刪除隊列首任務(wù)

(5) query available time slots for each service fromCRP

//查詢資源的可用時隙

(6) computeSS(t) according to Eq.(6) and (7)

//計算SS(t)

(7)AST←the actual start time of t onSS(t)

//更新AST

(8) make advance reservation of t onSS(t)

//提前保留

(9) for all (tc∈children oft) do

//對于所有子任務(wù)

(10) if (all parent oftcare scheduled ) then

//若所有父節(jié)點已被調(diào)度

(11) addtcto Queue

//添加至隊列

3.7 算法時間復雜度分析

假設(shè)調(diào)度的任務(wù)DAGG(T,E)包含n個任務(wù)和e條邊，可用資源數(shù)量為m，入口任務(wù)與出口任務(wù)間的最長路徑的長度為l。由于G為有向無循環(huán)圖，則最大邊數(shù)量為(n-1)(n-2)/2，因此可假設(shè)e≈O(n2)。調(diào)度算法中，步驟4計算MET的時間復雜度為O(nm)=O(n3)，步驟5計算MTT的時間復雜度為O(em2)=O(n2m)，步驟6計算EST的時間復雜度為O(n+e)=O(n2)，步驟7計算LFT的時間復雜度為O(n+e)=O(n2)，步驟11的Planning算法的時間復雜度為O(nme)=O(n3m)。

對于Planning算法，需要為每個任務(wù)嘗試所有資源以尋找滿足子期限的代價最低的資源。每一次嘗試中，需要計算任務(wù)在資源上的實際開始時間，該過程需要考慮所有父任務(wù)及連接邊，故時間復雜度為O(nme)。

AssignParent算法(分配節(jié)點算法)為遞歸過程。第一次在出口任務(wù)上調(diào)用并在所有DAG任務(wù)上進行自調(diào)用。算法擁有一個while循環(huán)(步驟2-步驟14)處理每個節(jié)點的入邊，故算法將處理所有DAG的邊。在while循環(huán)內(nèi)部，首先需要計算局部關(guān)鍵路徑，其時間復雜度為O(l)。然后，算法調(diào)用AssignPath，其時間復雜度取決于所選策略。由于AssignPath的時間復雜度取決于l和m，將其考慮為g(l,m)，故AssignParent的時間復雜度為O(el+eg(l,m))。對于AssignPath算法(分配路徑算法)，最快的為Fair策略，時間復雜度為O(lm)，因此可忽略時間復雜度的el部分，時間消耗為eg(l,m)。如果替換e，則時間復雜度為O(n2g(l,m))。在分配子期限后，AssignParent需要更新任務(wù)的所有未分配子節(jié)點的EST和所有未分配父節(jié)點的LFT。最差情況下，一個節(jié)點擁有n-1個未分配子節(jié)點和父節(jié)點，因此更新所有任務(wù)的EST和LFT的時間復雜度為O(n2)。

在三種不同的AssignPath策略下，AssignParent的時間復雜度分別為O(n2lm)、O(n2l2m)和O(n2lm)。由于l是入口任務(wù)至出口任務(wù)間最長路徑的長度，故其最大值為n(此時為線性DAG)。此時，AssignParent的時間復雜度分別為O(nm)、O(n4m)和O(n3m)，這也是整個算法的時間復雜度。

4 算例分析

以圖1所示DAG對算法工作原理進行闡述。算例包括9個任務(wù)t1至t9和兩個傀儡任務(wù)tentry和texit。三種資源Si,1、Si,2和Si,3，能以不同的QoS能力執(zhí)行任務(wù)。表1給出任務(wù)在不同資源上的執(zhí)行時間和執(zhí)行代價?？梢钥吹剑瑢τ谌蝿?wù)而言，資源越快，代價越高。圖1中，每條邊上的數(shù)值既表示數(shù)據(jù)傳輸時間，也表示對應傳輸代價。例如：t2與t5間的數(shù)據(jù)傳輸時間為2，則用戶的傳輸代價也為2，與兩個任務(wù)所選資源無關(guān)。設(shè)置DAG的全局截止期限為35。

表1 執(zhí)行時間和執(zhí)行代價

圖1 任務(wù)DAG

利用WS-PCPDC算法調(diào)度圖1的DAG，首先需要將所有任務(wù)分配至最快資源上計算EST和LFT。然后，算法設(shè)置tentry和texit的子期限分別為0和35，并標記兩個任務(wù)為已分配。接下來算法需要調(diào)用AssignParent和Planning，以下作出討論。

4.1 調(diào)用AssignParent算法

首先，在texit上調(diào)度AssignParent算法，由于該任務(wù)有3個父節(jié)點，步驟2的while循環(huán)將執(zhí)行三次，將之稱為Step1至Step3，后文進行討論。進一步，需要選擇路徑分配策略，以最優(yōu)策略O(shè)ptimized為例，每一步得到的任務(wù)的EST、LFT和子期限D(zhuǎn)L如表2所示。標記*表示該值相比前一步驟已發(fā)生改變。

Step1首先，AssignParent追蹤texit的局部關(guān)鍵父節(jié)點尋找其局部關(guān)鍵路徑，為t2-t6-t9。然后，調(diào)用AssignPath算法(分配路徑算法)分配子期限至這些任務(wù)。對于以上三個任務(wù)共有27種可能的資源分配，其中，S2,3-t2、S6,2-t6和S9,1-t9為擁有最小代價的最優(yōu)可行分配，該分配用于決定每個任務(wù)的子期限值。下一步即是更新這些任務(wù)的所有未分配子節(jié)點的EST，即t5和t8，及未分配父節(jié)點的LFT，即t3。變化后的值如表2的Step1。最后一步是在路徑上的所有任務(wù)上遞歸調(diào)用AssignParent。由于t2和t9沒有未分配父節(jié)點，在Step1.1中僅需在t6上調(diào)用AssignParent。

Step1.1當在t6上調(diào)用AssignParent時，首先尋找該任務(wù)的局部關(guān)鍵路徑，即t3。然后，調(diào)用AssignPath尋找t3的最優(yōu)分配，即S3,3。由于t3沒有未分配子節(jié)點或父節(jié)點，Step1完成。

Step2現(xiàn)在，回到任務(wù)texit，AssignParent試圖尋找下一條該任務(wù)的局部關(guān)鍵路徑，即t5-t8。然后，調(diào)用AssignPath，考慮這兩個任務(wù)的所有9種可能分配，并選擇最優(yōu)可行分配，即S5,1-t5，S8,3-t8。這兩個任務(wù)沒有未分配子節(jié)點，但算法需要更新其未分配父節(jié)點的LFT，即t1和t4。最后，算法在路徑上的所有任務(wù)上調(diào)用AssignParent，t5沒有未分配父節(jié)點，因此在Step2.1中僅考慮t8。

Step2.1當在任務(wù)t8上調(diào)用AssignParent時，尋找其局部關(guān)鍵路徑，即t1-t4。然后，調(diào)用AssignPath，計算該路徑的最優(yōu)可行分配，即S1,3-t1、S4,2-t4。這兩個任務(wù)沒有未分配父節(jié)點，算法需要更新t4的子節(jié)點的EST，即t7。由于t1和t4沒有未分配父節(jié)點，Step2停止。

Step3在最后一步中，AssginParent尋找texit的最后一條局部關(guān)鍵路徑，即t7。AssignPath尋找最優(yōu)可行分配為S7,2-t7，由于沒有未分配父節(jié)點或子節(jié)點，算法停止。

4.2 調(diào)用Planing算法

在該算例中，Planning僅將每個任務(wù)調(diào)度至AssignParent算法計算得到的相同資源上。原因在于：數(shù)據(jù)傳輸時間是固定的，且資源是完全可用的。這兩個假設(shè)使得AssignPath得到的估計調(diào)度方案是實際的調(diào)度方案。所選資源如表2所示?？倳r間為35，總代價為64，包括執(zhí)行代價48和數(shù)據(jù)傳輸代價16。

表2 算法每一步的詳細計算結(jié)果

5 仿真分析

5.1 實驗配置

為了評估算法性能，本節(jié)設(shè)計仿真實驗對算法進行測試。利用工作流仿真工具包WorkflowSim對算法進行實驗分析。在Workflow平臺上配置10個異構(gòu)數(shù)據(jù)中心，每個數(shù)據(jù)中心隨機配置10～100個資源節(jié)點，資源處理能力與代價配置參考Amazon EC2，單個數(shù)據(jù)中心的資源擁有相同的處理器速率，數(shù)據(jù)中心內(nèi)的資源處理能力約定最快為最慢的10倍。數(shù)據(jù)中心內(nèi)部的資源間的帶寬隨機分布于[100 Mbit/s，512 Mbit/s]之間，數(shù)據(jù)傳輸代價正比于帶寬，即帶寬越高，代價越高。

同時，實驗為了測試任務(wù)規(guī)模對算法性能的影響，配置了三種規(guī)模的任務(wù)數(shù)量，小規(guī)模為30個任務(wù)，中規(guī)模為100個任務(wù)，大規(guī)模為1 000個任務(wù)。使用五種不同科學領(lǐng)域中的合成工作流結(jié)構(gòu)作為數(shù)據(jù)源，包括：(1) Montage工作流：天文學;(2) Epigenomics工作流：生物學;(3) SIPHT：生物信息學；(4) LIGO工作流：引力物理學；(5) CyberShake工作流：地震學。其結(jié)構(gòu)如圖2所示[12]。不同工作流形式在其任務(wù)關(guān)聯(lián)、數(shù)據(jù)聚合、數(shù)據(jù)分布及數(shù)據(jù)重分布等組成方面均有所不同。Montage工作流的任務(wù)以I/O密集型為主，對CPU處理能力的要求相對較低，且串行任務(wù)結(jié)構(gòu)極少。Epigenomics工作流的任務(wù)以計算密集型為主，且對內(nèi)存要求較多，串行任務(wù)也較多。SIPHT工作流與Epigenomics同為生物學工作流形式，任務(wù)類型相似，但SIPHT工作流結(jié)構(gòu)更為復雜，串行任務(wù)極少。LIGO工作流的任務(wù)多以CPU計算密集型為主，且擁有較多內(nèi)存需求，擁有大量較短的串行任務(wù)。CyberShake任務(wù)以數(shù)據(jù)密集型為主，同時擁有較大內(nèi)存需求和CPU計算能力請求。

圖2 工作流結(jié)構(gòu)圖

5.2 實驗結(jié)果

利用標準化調(diào)度長度makespan(NM)和標準化代價cost(NC)對算法性能進行衡量：

式中:MHEFT表示利用質(zhì)構(gòu)最早完成時間算法HEFT[13]得到的調(diào)度長度，CC為將所有任務(wù)調(diào)度至代價最低資源上的調(diào)度代價。

為了評估算法性能，需要將截止期限分配至整個工作流任務(wù)。顯然，該截止期限須大于或等于HEFT算法得到的調(diào)度長度。為了設(shè)置截止期限，定義一個截止期限因子α，并設(shè)置工作流的期限為其到達時間加上αMHEFT。實驗中α值的取值范圍為[1,5]。選取的基準算法為MDP算法[10]。

表3給出了算法的標準化調(diào)度長度小于期限因子的平均比例，可以看出，算法均可以在期限約束內(nèi)完成所有工作流調(diào)度，即使期限較緊的情況下(更小的期限因子取值)。對于LIGO和CyberShake工作流，兩種算法幾乎利用了所有可用的期限使得執(zhí)行代價達到最小，即平均差值比例小于1%。Montage工作流幾乎是同樣的情況，而對于Epigenomics和SIPHT工作流，MDP算法擁有更高的平均差值比例，分別是中規(guī)模Epigenomics工作流中的3.07%和小規(guī)模SPIHT工作流中的5.99%。而本文的三種算法在小規(guī)模SPIHT中也均有相對更高的差值比例。

表3 標準化調(diào)度長度小于期限因子的平均比例

圖3給出了調(diào)度算法得到的執(zhí)行代價情況。大致上，中小規(guī)模工作流擁有類似結(jié)果，兩類算法在較寬松期限下(期限因子為5)擁有基本相同的標準化代價值(約為2)，這表明當將期限從MHEFT增加到5倍時，對于中小規(guī)模工作流標準化代價降低幅度約小于兩倍CC，除了中規(guī)模Montage例外。對于大規(guī)模工作流則擁有完全不同的結(jié)果，僅有SIPHT工作流維持與中小規(guī)模工作流相同的結(jié)果，而Montage工作流擁有最差的性能表現(xiàn)。這表明擁有大數(shù)量任務(wù)的大規(guī)模工作流中，工作流任務(wù)間的結(jié)構(gòu)特征比中小規(guī)模工作流更加影響任務(wù)調(diào)度過程。圖3還表明，Optimized在三種策略中及所有工作流類型中擁有最佳的性能表現(xiàn)，即最小的代價，也優(yōu)于參考算法MDP。

(a) 小規(guī)模CyberShake (b) 中規(guī)模CyberShake

(c) 大規(guī)模CyberShake (d) 小規(guī)模Epigenomics

(e) 中規(guī)模Epigenomics (f) 大規(guī)模Epigenomics

(g) 小規(guī)模LIGO (h) 中規(guī)模LIGO

(i) 大規(guī)模LIGO (j) 小規(guī)模Montage

(k) 中規(guī)模Montage (l) 大規(guī)模Montage

(m) 小規(guī)模SPIHT (n) 中規(guī)模SPIHT

(o) 大規(guī)模SPIHT圖3 標準化代價情況

對于CyberShake、LIGO和SIPHT工作流，利用Optimized策略的WS-PCPDC算法擁有最佳性能，而Cost Decrease策略則擁有近似表現(xiàn)。Fair策略擁有最差的性能，但仍然比MDP算法表現(xiàn)更優(yōu)。表4給出WS-PCPDC算法比較MDP算法的性能優(yōu)勢。

表4 WS-PCPDC算法比較MDP算法的性能優(yōu)勢

對于Epigenomics工作流，MDP在某些情況下具有比WS-PCPDC更好的性能，在大中規(guī)模情況下可以得到更小的平均代價降低幅度，主要原因是Epigenomics工作流結(jié)構(gòu)中擁有多個并行線性任務(wù)。初始狀態(tài)下，WS-PCPDC尋找工作流的關(guān)鍵路徑時，工作流擁有多個入口任務(wù)，一個是并行管道任務(wù)，其他三個為工作流的終端任務(wù)。WS-PCPDC試圖為這條關(guān)鍵路徑尋找最優(yōu)調(diào)度時，未考慮第一個和第六個任務(wù)間的并行性。若考慮并行性，需分配最長的子期限到這四個任務(wù)上，由于此時可以留下更多的空閑時間，全局代價也可以得到降低。

大規(guī)模Montage在所有算法上均擁有最差性能，即截止期限的增加并未帶來代價降低幅度的增加。在大規(guī)模Montage中，當增加期限至5倍時，代價降低約為初始值的一半。進一步，利用Optimized的WS-PCPDC算法從小規(guī)模至大規(guī)模工作流中有所降低，尤其在大規(guī)模工作流中，其性能差于MDP。原因在于，對于Montage結(jié)構(gòu)，其全局關(guān)鍵路徑由9個任務(wù)組成，需優(yōu)先為該路徑分配子期限。對于小規(guī)模工作流，所分配的子期限在資源選擇階段得以保留。然而，對于大規(guī)模工作流，全局關(guān)鍵路徑上第三個任務(wù)前的很多任務(wù)會在資源選擇階段被調(diào)度到更慢的資源上，這會導致關(guān)鍵路徑上的第三個任務(wù)無法按時完成，并會將這推遲傳導至其子節(jié)點，從而降低最終的調(diào)度性能。Fair在大規(guī)模工作流中擁有較好性能，比較MDP的平均代價降低比例為12.07，該策略在中規(guī)模工作流中也有較好性能。

6 結(jié) 語

為了滿足期限約束，最小化執(zhí)行代價，提出一種基于局部關(guān)鍵路徑和截止期限分配的工作流調(diào)度算法。算法通過定義工作流的局部關(guān)鍵路徑，以遞歸方式在局部關(guān)鍵路徑上的任務(wù)間進行子期限分配，并在調(diào)度資源選擇上滿足任務(wù)子期限的同時，為每個任務(wù)選擇執(zhí)行代價最低的調(diào)度，實現(xiàn)調(diào)度代價優(yōu)化。