張 揚 馬 飛

1(廣西工業(yè)職業(yè)技術學院 廣西 南寧 530003) 2(廣西大學計算機與電子信息學院 廣西 南寧 530004)

0 引 言

通常，云計算環(huán)境中的工作流可表示為有向無循環(huán)圖DAG的形式[1]。DAG中，節(jié)點即為待執(zhí)行的任務，有向邊即為任務間的次序約束或任務間的通信關系。相互獨立的任務可分配至不同的虛擬機上同步執(zhí)行，而相互依賴關系的任務則可以分配至同一虛擬機上執(zhí)行以降低任務間的數(shù)據(jù)通信延時。調(diào)度問題即將DAG中的任務分配至一個虛擬機資源集合，并考慮改善系統(tǒng)的性能[2]。調(diào)度問題可以是靜態(tài)的，即任務執(zhí)行前發(fā)生調(diào)度；也可以是動態(tài)的，即任務執(zhí)行過程中發(fā)生調(diào)度。多數(shù)情況下，以實現(xiàn)調(diào)度時間或代價最優(yōu)為目標的工作流形式的任務調(diào)度問題是NP問題。而大多數(shù)算法也僅集中于考慮執(zhí)行時間最小化的任務調(diào)度問題，而忽略了云計算環(huán)境中的調(diào)度代價問題。

本文設計一種基于代價的工作流任務調(diào)度算法(簡稱ICTS)。算法由層次排序、確定任務優(yōu)先級、虛擬機選擇三個階段組成。通過三階段式的任務調(diào)度過程，較好地均衡了調(diào)度長度和任務執(zhí)行代價間的平衡問題，并且通過大規(guī)模隨機化生成的任務有向圖模型的仿真比較研究，證實了算法在調(diào)度長度和執(zhí)行代價同步優(yōu)化上的優(yōu)勢。

1 相關研究

為了解決工作流調(diào)度這一NP問題，很多文獻提出了啟發(fā)式調(diào)度算法。文獻[3]提出兩種算法LOSS和GAIN分別用來優(yōu)化預算約束下的時間和代價，但僅涉及單目標優(yōu)化。文獻[4]討論了IaaS云環(huán)境中的代價和截止時間約束工作流調(diào)度，但所考慮的資源僅為同質(zhì)資源模型。文獻[5]提出兩種云工作流調(diào)度算法：一階段算法IC-PCP和兩階段算法IC-PCPD2。兩種算法可以在多項式時間內(nèi)得到截止時間約束下的代價最小調(diào)度方案。文獻[6]提出了在混合云中截止時間約束的代價最小化調(diào)度算法HEFT，利用子截止時間的概念進行資源的重調(diào)度，并實現(xiàn)了代價最小化。文獻[7]則實現(xiàn)了包任務在截止時間約束下的代價最小化調(diào)度，但僅適用于獨立任務調(diào)度。文獻[8]利用粒子群搜索方法求解了用戶截止時間約束下費用最小化的工作流調(diào)度方案。文獻[9-11]提出了一種截止時間與預算約束時工作流調(diào)度遺傳算法，但也僅是實現(xiàn)執(zhí)行代價或執(zhí)行時間的單一優(yōu)化。文獻[12]提出一種工作流調(diào)度算法Hybrid，基于帕累托占優(yōu)技術將任務調(diào)度至代價最小的虛擬機上，有效降低非關鍵路徑上任務的調(diào)度代價。但算法沒有考慮關鍵路徑上任務執(zhí)行代價對于總體代價的關鍵影響，導致得到的最終代價并不一定是最優(yōu)的?？梢钥闯觯陨蠁l(fā)式或元啟式算法多數(shù)僅進行了壟斷和單一目標優(yōu)化。

鑒于此，本文設計了一種同步考慮執(zhí)行時間與代價的工作流調(diào)度算法，通過定義任務的調(diào)度優(yōu)先級以及最優(yōu)調(diào)度資源的選擇規(guī)則，實現(xiàn)工作流的均衡調(diào)度。

2 系統(tǒng)模型

表1給出與本文相關的所有符號含義說明。

表1 符號說明

表1 符號說明

2.1 工作流模型

科學工作流的常規(guī)建模方式即為有向無環(huán)圖模型DAG，將工作流表示為G=(V,E)，V表示任務v的集合，E表示邊e的集合也代表兩個任務間的通信代價。節(jié)點vi∈V表示任務的計算時間，該值取決于任務所分配的虛擬機的計算能力。邊(i,j)∈E的權重表示任務vi與任務vj間的通信時間，即任務間發(fā)送數(shù)據(jù)所需要的時間。若DAG中的一個任務不存在父節(jié)點(前驅(qū)節(jié)點)，則稱之為入口任務ventry，若一個任務不存在子節(jié)點(后繼節(jié)點)，則稱之為出口任務vexit。若DAG中擁有多個入口或出口任務節(jié)點，可分配一個總的入口或出口任務節(jié)點，并將其所有先前入口或出口任務相連，且該總?cè)肟诨虺隹诠?jié)點的權重取0，邊權重也取0。DAG的任務模型表明，一個任務只有在其所有父節(jié)點完成后，該任務才能開始執(zhí)行。有向無環(huán)圖模型下的工作流模型優(yōu)勢在于可以明確工作流各個子任務間的依賴關系，以及整個工作流的進出口位置，進而方便任務調(diào)度次序的選擇和任務完成時間的計算。

圖1為一個DAG模型示例。該DAG包括10個任務節(jié)點，節(jié)點v0為第一個執(zhí)行任務，節(jié)點v1-v8僅能在任務v0完成關發(fā)送結果數(shù)據(jù)后才能開始執(zhí)行，而節(jié)點v2-v4直到v1完成前也無法開始執(zhí)行，節(jié)點v9是最后一個任務，該任務只有在其他所有任務均執(zhí)行完成后才能開始執(zhí)行。當兩個任務被分配至同一虛擬機資源時，邊上的通信代價值也可以忽略不計。

圖1 DAG示例

2.2 云資源模型

假設云計算環(huán)境擁有m個異構虛擬機資源組成的集合M，由于每個任務可在不同虛擬機上執(zhí)行，令t(vi,mj)表示任務vi在虛擬機vj上的執(zhí)行時間，并假設每個任務是DAG的一個個體而不再分割。DAG中的所有任務調(diào)度至虛擬機上執(zhí)行后，DAG的調(diào)度長度makespan即為出口任務vexit的實際完成時間。令TES(vi,mj)、TEF(vi,mj)、TLF(vi,mj)分別表示任務vi在虛擬機mj上的最早開始時間、最早完成時間、最遲完成時間。TES(vi,mj)可表示為：

TES(vi,mj)=

(1)

若前驅(qū)任務vp調(diào)度至虛擬機mj，則ctvp,vi等于0。TEF(vi,mj)可表示為：

TEF(vi,mj)=TES(vi,mj)+t(vi,mj)

(2)

TLF(vi,mj)可表示為：

(3)

DAG的調(diào)度長度makespan定義為DAG的完成時間，等于出口任務vexit的實際完成時間，表示為：

MS=TAF(vexit)

(4)

云計算中，多個虛擬機均可以執(zhí)行每個任務。則任務vi在虛擬機mj上的執(zhí)行時間可表示為：

(5)

若現(xiàn)有n個虛擬同可執(zhí)行任務vi，則vi的平均執(zhí)行時間可表示為：

(6)

該資源模型利用異構的虛擬機集群建立了執(zhí)行工作流任務的通用模型，使得不同處理能力和不同價格的虛擬機均是工作流任務的可選目標，這樣可以在調(diào)度算法設計上僅關注于任務與資源間滿足目標函數(shù)的匹配與映射求解問題。

2.3 價格模型

云計算擁有不同的價格模型，如Amazon EC2按照虛擬機的數(shù)量和類型收費，而Google App Engine則按照所請求的CPU周期數(shù)收費。本文利用后一種虛擬機的代價模型，其優(yōu)勢在于在單個已付費周期的CPU租用過程中，若付費任務已經(jīng)在單個CPU周期內(nèi)完成，則后續(xù)繼續(xù)利用CPU的任務可以不支付費用，從而降低工作流整體的執(zhí)行代價。價格越高，則表明虛擬機計算能力越強，反之亦然。令mc(vi,mj)表示任務vi在虛擬機mj上執(zhí)行的代價：

(7)

3 算法設計

本文設計一種基于代價的工作流任務調(diào)度算法，目標是將DAG中的任務調(diào)度至虛擬機上執(zhí)行，并確保得到最小化的調(diào)度長度和執(zhí)行代價。算法基本流程如算法1所示。

算法1ICTS算法

輸入：DAG G(V,E)，虛擬機集合。

輸出：任務調(diào)度解，即任務與虛擬機間的映射關系。

1. partition G into levles according to tasks dependency

2. sort levels based on dependency order

3. for each level do

4. for each taskvido

5. computeRank(vi)

6. end for

7. end for

8. create new tasks list

9. sort all tasks in the new list in decreasing order of Rank(vi)

10. for each taskviin the task list do

11. for each VMmjin the VMs set do

12. compute MKCR(vi,mj)

13. end for

14. end for

15. assign taskvito the VMmjthat has the maximum value of MKCR(vi,mj)

16. end

ICTS算法由三個階段組成：層次排序階段(工作流任務分級)、確定任務優(yōu)先級階段、虛擬機選擇階段。第一階段的目標是盡可能提高任務并行執(zhí)行度，具體方式是以自頂向下的方式遍歷工作流結構的有向無環(huán)圖，以拓撲排序的形式將處于同一層次的相互獨立的任務劃分為群組。分組后的任務將形成任務包的形式，在同一任務包中的任務不具備相關性，從而提高任務的并行執(zhí)行程度。第二階段中，算法根據(jù)每個任務的秩值，對每個層次中的任務進行排序，任務vi的秩值計算方式為：

(8)

(9)

Rank(vexit)=MCP(vexit)

(10)

由此可見，第二階段計算任務的秩值決定了任務被調(diào)度的優(yōu)先級次序，且任務秩值需要以遞歸方式從出口任務往入口任務進行計算。

最后，在虛擬機選擇階段，任務vi在虛擬機mj上的調(diào)度長度/代價比率MKCR(vi,mj)計算為：

MKCR(vi,mj)=[(1-β)×Min_Cost(vi)/

Cost(vi,mj)]+[β×Min_TEF(vi)/TEF(vi,mj)]

(11)

式中：β表示代價因子，用于描述用戶對于調(diào)度長度與執(zhí)行代價間的偏好；Cost(vi)表示任務vi在虛擬機mj上的執(zhí)行代價。

第三階段使得每個任務將被調(diào)度至擁有最大MKCR(vi,mj)值的虛擬機上，該策略可以充分利用在每個虛擬機上相鄰兩個調(diào)度任務間的空閑時間槽，不僅最小化整個DAG的完成時間，并且可以通過目標虛擬機的選擇時參考調(diào)度長度/代價比率MKCR的方式均衡任務執(zhí)行的時間和代價。

算法時間復雜度分析。ICTS算法的時間復雜度與傳統(tǒng)的HEFT算法是相似的，同為O(e×m)，其中：e表示DAG中有向邊的數(shù)量，m表示虛擬機數(shù)量。若有向邊的數(shù)量正比于v2(v為任務數(shù)量)，則算法時間復雜度可達到O(v2×m)。

圖2展示了以圖1為例的任務DAG利用混合算法Hybrid[12]和本文算法ICTS得到的調(diào)度結果。算例的場景中擁有3個虛擬機資源，任務在虛擬機上的執(zhí)行時間和執(zhí)行代價如表2和表3所示。圖2(a)顯示混合算法的調(diào)度長度為1 000.94 s，調(diào)度代價為822＄。圖2(b)顯示ICTS算法的調(diào)度長度為874.19 s，調(diào)度代價為793＄。本文提出的算法降低了約12.66%的調(diào)度長度，調(diào)度代價約節(jié)省了3.52%。

圖2 調(diào)度結果對比

任務VM0VM1VM2v0191.98132.6499.31v1220.01152.01113.81v2177.37122.5591.75v3270.97187.22140.18v4204.71141.44105.90

續(xù)表2 s

表3 任務在不同虛擬機上的執(zhí)行代價 ＄

4 仿真實驗

利用WorkFlowSim平臺[13]進行云環(huán)境中工作流調(diào)度的仿真實驗，并利用一種特定的工作流結構類型Montage作為云工作流的拓撲結構進行測試，Montage工作流是一種應用于天文學領域的科學工作流結構，其任務組成以I/O密集型為主，對CPU處理能力要求相對較低，串行任務較少，其結構如圖3所示。表4是實驗中的相關參數(shù)配置情況。

圖3 Montage工作流結構

表4 參數(shù)配置

4.1 性能指標

1) 調(diào)度長度比率和代價比率。系統(tǒng)調(diào)度效率可以通過標準化的調(diào)度長度和代價進行衡量，即調(diào)度長度比率SLR和代價比率MCR，分別定義為：

(12)

(13)

式(12)的分母部分表示處于關鍵路徑CP上的任務的最小執(zhí)行時間之和，式(13)的分母部分表示處于關鍵路徑CP上的任務的最小執(zhí)行代價之和。

2) 代價因子β。為了度量SLR和MCR，需要使用不同的代價因子β取值。圖4為針對不同的代價因子取值在不同的DAG規(guī)模下得到SLR和MCR取值情況。圖中，x軸代表代價因子，y軸同時代表SLR和MCR，即標準化的調(diào)度長度和代價。DAG中的任務數(shù)量隨機生成于80～400個任務之間。圖4表明，代價因子與MCR成正比，而與SLR成反比。對于較小的代價因子β，如β=0.1、0.2、0.3，MCR和SLR的變化比例略小于β>0.3的變化。總體來看，在β<0.4的情況下，算法在兩個指標上能夠擁有較好的性能表現(xiàn)。而β>0.4后，SLR的變化比例較慢，而MCR變化較快。因此，在后續(xù)仿真測試中代價因子β可取值為0.1、0.2和0.3。

圖4 不同規(guī)模不同代價因子對性能的影響

4.2 結果分析

本節(jié)對ICTS算法和對比算法Hybrid進行實驗對比分析，利用前文引入的標準化調(diào)度長度比率和標準化代價比率作為性能指標。在相同的虛擬機資源配置下，利用不同的DAG規(guī)模(不同的任務數(shù)量)進行實驗仿真。圖4為在不同的任務數(shù)量和CCR取值情況下兩個指標的性能比較情況，其中，柱狀圖的取值對應于左側(cè)縱坐標值，折線圖的取值對應于右側(cè)坐標值。算法的SLR指標均會隨著任務數(shù)量和CCR取值的增加而增加，而ICTS算法在不同DAG規(guī)模下也可以得到更優(yōu)的SLR性能。表5給出本文算法ICTS對比Hybrid算法在任務調(diào)度長度和代價上得到的增益比例(即在調(diào)度長度和代價上的節(jié)省程度)，在確定的任務規(guī)模下，ICTS算法在選擇目標虛擬機時有效參考了調(diào)度效率與代價的均衡，使得兩個指標均得到改善。

表5 ICTS算法比較對比算法Hybrid得到的增益

圖5和圖6顯示了在不同的DAG任務規(guī)模下算法得到的SLR和MCR指標性能情況?？梢钥吹?，ICTS算法在兩項指標上是優(yōu)于Hybrid算法的，這是因為ICTS算法考慮了任務父節(jié)點與自身的通信時間以及任務子節(jié)點與自身的通信時間(如式(8)所示)。因此，在DAG中最復雜任務將處于分級隊列的隊首而被優(yōu)先進行調(diào)度。而Hybrid算法在計算每個任務的分級時僅僅考慮了任務與其后繼之間的通信時間。

圖5 不同任務組成(CCR度量)及不同任務數(shù)量對SLR的影響

圖6 不同任務組成(CCR度量)及不同任務數(shù)量對MCR的影響

利用式(11)選擇任務調(diào)度的虛擬機，ICTS算法同時考慮了Min_Cost(vi)和Min_TEF(vi)。此外，還可以看到，改變工作流中任務的通信/計算比率(改變計算密集型和通信密集型任務的比例)的情況下，ICTS算法在SLR指標上依然具有較好的適應性，仿真結果并沒有出現(xiàn)反轉(zhuǎn)式的結果，而僅僅是指標值出現(xiàn)比較緩和的增加。

對于算法而言，MCR指標會隨著任務數(shù)量和CCR取值的增加而增加。圖6結果表明ICTS算法在不同的任務規(guī)模下提供了比Hybrid算法更好的MCR性能。另一方面，Hybrid算法過多依賴于時間與代價的比例，這些比例在選取調(diào)度任務時僅考慮了執(zhí)行代價與執(zhí)行時間的最小值和最大值，而本文算法對相關參數(shù)的依賴性則遠弱于Hybrid算法，使其在不同規(guī)模和不同任務組成的情況下依然可能得到比較穩(wěn)定的性能表現(xiàn)。

5 結 語

為了實現(xiàn)云計算環(huán)境中的工作流任務調(diào)度，本文以最小化調(diào)度長度和執(zhí)行代價為目標，提出一種基于代價的工作流調(diào)度算法。通過任務分級排序、確定任務優(yōu)先級以及虛擬機資源選擇三個階段的優(yōu)化，實現(xiàn)了不同規(guī)模任務下對工作流調(diào)度長度和執(zhí)行代價的同步優(yōu)化。仿真實驗結果表明，對于選取的SLR和MCR兩個性能指標，本文算法均表現(xiàn)出比對比算法更好的性能。下一步可選擇將云資源提供方的能耗問題考慮到優(yōu)化目標中，即在執(zhí)行效率與執(zhí)行能效之間取得更好的平衡，以此為目標設計工作流調(diào)度算法。