基于局部關鍵路徑與截止期限分配的云工作流調度算法

蔡艷婧 王 強 程 實

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

0 引 言

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

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

1 相關研究

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

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

2 任務調度模型

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

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

3 算法設計

3.1 算法實現思路

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

3.2 基本定義

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

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

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

對于每個未調度任務ti，令LFT(ti)為整個任務DAG在截止時間D內保證完成時,任務ti能夠完成執行的最遲時間，則：

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

3.3 算法步驟

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

算法1WS-PCPDC

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

(2) Request available resource for each task inG

//發出資源請求

(3) addtentry,texitand their correoponding edges toG

//添加進出口任務

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

//為每個任務計算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

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

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

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

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

//為入口出口任務計算子期限

(9) marktentryandtexitas assigned

//標識入出口任務已調度

(10) call function AssignParent(texit)

//調用AssignParent(texit)

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

//調用Planning(G(T,E))

(12) end procedure

3.4 AssignParent算法

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

算法2AssignParent

(1) Procedure AssignParents(t)

(2) while (thas an unassigned parent) do

//若t有未調度父節點

(3)PCP←null,ti←t

//局部關鍵路徑置空

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

//若仍有未調度父節點

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

//添加任務的關鍵父節點至PCP的隊首

(6)ti←CriticalParent(ti)

//提取當前任務

(7) call function AssginPath(PCP)

//調用函數AssginPath(PCP)

(8) for all (ti∈PCP) do

//每個局部關鍵路徑上的任務更新EST和LFT

(9) updateESTfor all unassigned successors ofti

//更新所有未調度子任務的EST

(10) updateLFTfor all unassigned predecessors ofti

//更新所有未調度父任務的LFT

(11) end procedure

以下定義關鍵父節點的概念：

定義1任務ti的關鍵父節點為數據到達時間最遲的未分配父節點，即：滿足下式的ti的父節點tp：

定義2任務節點ti的局部關鍵路徑為：

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

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

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

3.5 AssignPath算法

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

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

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

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

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

(1) Procedure AssignPath(Path)

(2) best←null

//最優集合先置空

(3)t←first task on the path

//提取當前路徑的第一個任務

(4) while (t is not null) do

(5)s←next slower service ∈St

//提取下一個最慢的服務提供者

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

//若無法分配完成

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

//繼續在該路徑上尋找

(8) end if

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

//若該任務為路徑上的最后一個任務

(10) set this schedule as best

//設置該調度解為最優

(11) end if

(12)t←next task on the path

//提取路徑上的下一任務

(13) end while

(14) if (best is null) then

//若最優集為空

(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

//以最優解為基礎設置EST和子期限

(18) end if

(19) mark all tasks of the path as assgined

//標記任務是否調度

(20) end procedure

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

(5)

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

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

算法4低價降低策略算法

(1) Procedure AssignPath(path)

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

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

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

//計算任務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

//分配次最慢的服務器更新cur

(13) updateCDR(t*)

//更新CDR

(14) end if

(15) until (t*is null)

//循環至集合為空

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

//若在cur集合中存在一個不允許的調度解

(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

//以最優解為基礎設置EST和子期限

(20) end if

(21) mark all tasks of the path as assgined

//標記調度任務

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

算法5Fair PathAssigning Algorithm

(1) Procedure AssignPath(Path)

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

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

(3) for all (ti∈path) do

//對于所有路徑上的任務

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

//若將任務調度至下一個服務器可行

(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

//以最優解為基礎設置EST和子期限

(11) mark all tasks of the path as assgined

//標記已調度任務

3.6 Planning算法

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

約束條件為：

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

(6)

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

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

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

(7)

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

算法6Planning

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

(2) Queue←tentry

//將入口任務輸入隊列

(3) while (Queue is not empty) do

//若隊列不為空

(4) t←delete first task from Queue

//刪除隊列首任務

(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

//對于所有子任務

(10) if (all parent oftcare scheduled ) then

//若所有父節點已被調度

(11) addtcto Queue

//添加至隊列

3.7 算法時間復雜度分析

假設調度的任務DAGG(T,E)包含n個任務和e條邊，可用資源數量為m，入口任務與出口任務間的最長路徑的長度為l。由于G為有向無循環圖，則最大邊數量為(n-1)(n-2)/2，因此可假設e≈O(n2)。調度算法中，步驟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算法，需要為每個任務嘗試所有資源以尋找滿足子期限的代價最低的資源。每一次嘗試中，需要計算任務在資源上的實際開始時間，該過程需要考慮所有父任務及連接邊，故時間復雜度為O(nme)。

AssignParent算法(分配節點算法)為遞歸過程。第一次在出口任務上調用并在所有DAG任務上進行自調用。算法擁有一個while循環(步驟2-步驟14)處理每個節點的入邊，故算法將處理所有DAG的邊。在while循環內部，首先需要計算局部關鍵路徑，其時間復雜度為O(l)。然后，算法調用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需要更新任務的所有未分配子節點的EST和所有未分配父節點的LFT。最差情況下，一個節點擁有n-1個未分配子節點和父節點，因此更新所有任務的EST和LFT的時間復雜度為O(n2)。

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

4 算例分析

以圖1所示DAG對算法工作原理進行闡述。算例包括9個任務t1至t9和兩個傀儡任務tentry和texit。三種資源Si,1、Si,2和Si,3，能以不同的QoS能力執行任務。表1給出任務在不同資源上的執行時間和執行代價。可以看到，對于任務而言，資源越快，代價越高。圖1中，每條邊上的數值既表示數據傳輸時間，也表示對應傳輸代價。例如：t2與t5間的數據傳輸時間為2，則用戶的傳輸代價也為2，與兩個任務所選資源無關。設置DAG的全局截止期限為35。

表1 執行時間和執行代價

圖1 任務DAG

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

4.1 調用AssignParent算法

首先，在texit上調度AssignParent算法，由于該任務有3個父節點，步驟2的while循環將執行三次，將之稱為Step1至Step3，后文進行討論。進一步，需要選擇路徑分配策略，以最優策略Optimized為例，每一步得到的任務的EST、LFT和子期限DL如表2所示。標記*表示該值相比前一步驟已發生改變。

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

Step1.1當在t6上調用AssignParent時，首先尋找該任務的局部關鍵路徑，即t3。然后，調用AssignPath尋找t3的最優分配，即S3,3。由于t3沒有未分配子節點或父節點，Step1完成。

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

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

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

4.2 調用Planing算法

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

表2 算法每一步的詳細計算結果

5 仿真分析

5.1 實驗配置

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

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

圖2 工作流結構圖

5.2 實驗結果

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

式中:MHEFT表示利用質構最早完成時間算法HEFT[13]得到的調度長度，CC為將所有任務調度至代價最低資源上的調度代價。

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

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

表3 標準化調度長度小于期限因子的平均比例

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

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

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

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

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

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

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

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

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

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

表4 WS-PCPDC算法比較MDP算法的性能優勢

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

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

6 結 語

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