最后期限動態(tài)分配的三步云工作流調(diào)度算法

王子健，盧政昊，2，潘紀(jì)奎，2，孫福權(quán)

1(東北大學(xué)秦皇島分校 數(shù)學(xué)與統(tǒng)計學(xué)院，河北 秦皇島 066000)2(東北大學(xué) 信息科學(xué)與工程學(xué)院，沈陽 110000)

1 引 言

工作流經(jīng)常被用于生物信息學(xué)、天文學(xué)和物理學(xué)等大規(guī)模建?？茖W(xué)問題[1].一個工作流中通常包含成百上千個具有依賴關(guān)系的計算任務(wù)，一般被描述成有向無環(huán)圖(DAG).工作流調(diào)度的目的是找到最合適的資源來執(zhí)行工作流中的每一個任務(wù)，同時滿足服務(wù)質(zhì)量(QoS)約束[2].隨著云計算的興起，云環(huán)境成為了執(zhí)行工作流的新平臺.云工作流調(diào)度變得越來越流行，越來越有前景[3].云環(huán)境可以被當(dāng)成一個“無限的”資源池，其中包含各種類型的資源.為了執(zhí)行工作流，用戶通?；诎创胃顿M的模式租用云資源[4].一般來說，資源性能越高，執(zhí)行任務(wù)的速度越快，同時價格也越昂貴.因此云工作流調(diào)度需要同時考慮執(zhí)行成本和完工時間.一種常見的形式是在滿足最后期限約束的前提下最小化執(zhí)行成本，這是一個已知的NP難問題[5].這一問題多年來一直是分布式計算社區(qū)的熱點[6].

列表調(diào)度算法被廣泛用來解決工作流調(diào)度問題.它通常包含兩個步驟:根據(jù)預(yù)先定義的啟發(fā)式信息設(shè)置任務(wù)的優(yōu)先級并依據(jù)優(yōu)先級構(gòu)建一個調(diào)度列表；依次為調(diào)度列表中的任務(wù)分配合適的資源.為解決云工作流調(diào)度問題，有些研究[7]在兩步列表調(diào)度之前先進(jìn)行了最后期限的分配，從而形成三步列表調(diào)度.整個工作流的最后期限被分配到每個子任務(wù)上，形成每個任務(wù)的子期限.之后按照兩步列表調(diào)度算法的方式進(jìn)行資源的分配，確保每個任務(wù)在不超過其子期限的前提下配置上最廉價的資源.實驗數(shù)據(jù)表明，這種三步列表調(diào)度算法的效果要優(yōu)于兩步列表調(diào)度算法.

然而現(xiàn)有的最后期限分配策略均只能形成靜態(tài)的子期限，因此還可以進(jìn)行進(jìn)一步的優(yōu)化.本文采用三步列表調(diào)度算法進(jìn)行云工作流調(diào)度，并提出一種基于粒子群的動態(tài)最后期限分配方法(DY-DD).實驗結(jié)果表明，相比于其它經(jīng)典調(diào)度算法，本文提出的算法在成功率和執(zhí)行成本上均具有優(yōu)勢.

2 相關(guān)研究

工作流調(diào)度問題最初聚焦于多處理器系統(tǒng)[8]和陣列系統(tǒng)[9].由于這類系統(tǒng)通常提供數(shù)量有限且容量確定的資源，同時資源可免費使用，因此傳統(tǒng)工作流調(diào)度的主要目標(biāo)是最小化工作流執(zhí)行時間，從而以盡力而為的方式為用戶提供服務(wù).列表調(diào)度算法被廣泛用于解決此類問題，例如EFT[10]、HEFT[11]、CPOP[11]、PEFT[12].它們通常為每個任務(wù)計算啟發(fā)式信息，并根據(jù)啟發(fā)式信息構(gòu)建一個調(diào)度列表.之后為列表中的每一個任務(wù)分配合適資源使得任務(wù)可以盡早開始執(zhí)行.

云計算的興起使得云環(huán)境成為執(zhí)行工作流的新平臺，也使得云工作流調(diào)度成為新的研究課題.云工作流調(diào)度通常需要同時進(jìn)行多個目標(biāo)的優(yōu)化，例如同時優(yōu)化工作流的完工時間和執(zhí)行成本.通常的做法是將其中一個目標(biāo)作為主要優(yōu)化對象，同時滿足其它目標(biāo)的約束.例如在滿足最后期限約束的前提下最小化執(zhí)行成本.這一問題是已知的NP難問題且求解過程很容易陷入局部最優(yōu)，因此大量元啟發(fā)式算法被用來解決這一問題.文獻(xiàn)[13]利用了遺傳算法、文獻(xiàn)[14，15]基于粒子群算法、文獻(xiàn)[16]基于蟻群算法.文獻(xiàn)[17]則在傳統(tǒng)粒子群算法的基礎(chǔ)上進(jìn)行了改進(jìn)，提出了免疫粒子群算法.該算法改善了粒子群算法的收斂速度，從而提高了算法的質(zhì)量.文獻(xiàn)[18]在使用粒子群算法的同時考慮了同一個資源實例下順序執(zhí)行的任務(wù)間存在的空閑時隙，并加以利用.然而以上這些元啟發(fā)式算法都只著重解決任務(wù)與資源間的映射，忽視了工作流執(zhí)行時各任務(wù)需要滿足的子期限.

列表調(diào)度算法同樣用于解決云工作流調(diào)度問題.有些文獻(xiàn)在傳統(tǒng)列表調(diào)度算法的基礎(chǔ)上新增了最后期限分配這一步驟.最后期限首先被分配給工作流中的每個任務(wù)，從而形成子期限.之后利用列表調(diào)度算法為每個子任務(wù)分配合適的資源.分配資源時確保每個任務(wù)滿足子期限且執(zhí)行成本最優(yōu).例如文獻(xiàn)[7]提出的ProLis、文獻(xiàn)[19]提出的DCO/DUCO和文獻(xiàn)[20]的HAS都根據(jù)自定義的啟發(fā)式信息進(jìn)行最后期限的分配.文獻(xiàn)[21]提出的LBWS則根據(jù)任務(wù)節(jié)點在工作流圖中所處的層級進(jìn)行最后期限的分配.盡管上述文獻(xiàn)均可以獲得不錯的調(diào)度結(jié)果，但是這些算法都只針對每個任務(wù)生成了靜態(tài)子期限，因此還可以進(jìn)行進(jìn)一步的優(yōu)化.

除此之外還有一些文獻(xiàn)利用了分治的思想進(jìn)行工作流調(diào)度.他們的目的也同本文一致，即滿足最后期限約束最小化執(zhí)行成本.例如文獻(xiàn)[22]提出的PCP算法利用了關(guān)鍵路徑的概念.算法首先找到工作流圖中的關(guān)鍵路徑，并將最后期限分配給每一個關(guān)鍵任務(wù)(位于關(guān)鍵路徑上的任務(wù)).之后再以每個關(guān)鍵任務(wù)為終點繼續(xù)反向查找關(guān)鍵路徑并分配最后期限.文獻(xiàn)[23]在此基礎(chǔ)上提出了IC-PCP算法.該算法與PCP具有類似的關(guān)鍵路徑查找方案，但不進(jìn)行最后期限的分配，取而代之的是直接進(jìn)行服務(wù)資源的配置.文獻(xiàn)[24]則進(jìn)一步利用了這種分治的思想，文獻(xiàn)中提出的DQWS算法在找到關(guān)鍵路徑后會直接將其從工作流圖中刪除，從而將原工作流一分為二.之后遞歸執(zhí)行此過程，直至每個子圖均只包含一條單任務(wù)鏈.以上算法有些雖然也使用了最后期限分配策略，但也均只形成了靜態(tài)子期限，沒有對分配的子期限進(jìn)行局部調(diào)優(yōu).

3 問題描述

3.1 工作流模型

一個工作流可以用有向無環(huán)圖DAG=(V，E)來表示.V={t1，t2，…，tn}是有向無環(huán)圖中節(jié)點的集合，每一個節(jié)點都代表一個任務(wù)，一個任務(wù)也可以被理解成一段獨立的且不能被并行執(zhí)行程序.對于一個給定的任務(wù)ti，可以用wi代表該任務(wù)的計算量.E是有向無環(huán)圖中邊的集合.E中的一條邊eij={ti，tj}代表了任務(wù)ti和tj之間的一種依賴關(guān)系，即任務(wù)tj只能在任務(wù)ti執(zhí)行結(jié)束后才能開始執(zhí)行.此時ti和tj被分別被稱為父任務(wù)和子任務(wù).若一個任務(wù)沒有父任務(wù)，則稱之為起始任務(wù)，若一個任務(wù)沒有子任務(wù)則稱之為終止任務(wù).如果任務(wù)之間存在數(shù)據(jù)傳輸，則需要為eij添加一個屬性dataij來代表由ti到tj的數(shù)據(jù)傳輸量.此時任務(wù)tj只能在ti執(zhí)行結(jié)束且完成數(shù)據(jù)傳輸后才開始執(zhí)行.有些工作流可能同時擁有多個起始節(jié)點或終止節(jié)點，大多數(shù)調(diào)度算法并不適用于這種情況.為了一般化工作流模型，可以在工作流的開始處和結(jié)束處分別添加了兩個負(fù)載為零且不傳輸任何數(shù)據(jù)的虛擬任務(wù)tentry和texit.圖1展示了一個工作流示例.

圖1 工作流示例圖Fig.1 Example of workflow

3.2 云資源模型

云平臺中的各類資源被虛擬化為資源池以便進(jìn)行統(tǒng)一的管理并以租賃的方式為云使用者提供服務(wù).用R={r1，r2，…，rn} 代表云使用者可租用的資源類型的集合.不同類型的資源擁有不同的處理能力和租賃費用.通常處理能力越強的資源，其租賃費用也越昂貴.vmk代表云使用者租用的一個具體的資源實例或虛擬機.虛擬機是工作流中任務(wù)的執(zhí)行平臺.工作流中的一個任務(wù)只能被調(diào)度到唯一的一個虛擬機上執(zhí)行，而一個虛擬機可以順序的執(zhí)行一組任務(wù).Tp(vmk)代表vmk的資源類型，因此Tp(vmk)∈R.P(rl)代表l類資源的處理能力，因此vmk的處理能力為P(Tp(vmk)).本文采用的定價方式為即付即用模式，即根據(jù)虛擬機被租用的單元時間數(shù)量來進(jìn)行收費.當(dāng)租用的虛擬機沒有使用完一個完整的單元時間時，也會按照一個單元時長的費用對其進(jìn)行收費.如圖2所示，虛擬機的單元時長設(shè)置為T，虛擬機在0時刻被租賃，3.2T時刻被釋放，那么用戶需支付4個單元時間的開銷.UC(rl)代表l類資源單位時長所需要的租用費用，因此租用vmk一個單位時長所需要承擔(dān)的租賃費用為UC(Tp(vmk)).

圖2 付費時間段示例圖Fig.2 Example of a paid time period

假設(shè)任務(wù)ti被安排到虛擬機vmk上執(zhí)行，則ti在vmk上的執(zhí)行時長為:

(1)

本文假設(shè)所有虛擬機都位于相同的物理區(qū)域且虛擬機之間的平均帶寬(bw)大致相等，同時虛擬機間數(shù)據(jù)傳輸是免費的.用TTi，j代表ti到tj的數(shù)據(jù)傳輸時長，則:

(2)

其中vm(ti)代表執(zhí)行ti的虛擬機.當(dāng)兩個任務(wù)由同一個虛擬機執(zhí)行時，它們之間的數(shù)據(jù)傳輸時長為0.

用STi，k代表任務(wù)ti在虛擬機vmk上的開始執(zhí)行時刻，F(xiàn)Ti，k代表任務(wù)ti在虛擬機vmk上的完成時刻，則:

(3)

FTi，k=STi，k+ETi，k

(4)

其中RTk代表vmk的空閑時刻，即vmk上排列在ti之前的任務(wù)的完成時刻.也可以理解為vmk可執(zhí)行ti的最早時刻.若ti是vmk上的第一個任務(wù)，則為的啟動完成時刻.

分別用LSTk和LFTk代表虛擬機vmk的開始租用時刻和租用結(jié)束時刻.LSTk為虛擬機vmk上的第一個任務(wù)開始接收數(shù)據(jù)的時刻，LFTk為vmk上最后一個任務(wù)完成數(shù)據(jù)傳輸?shù)臅r刻.公式(5)給出了vmk的租用費用.

ECk=「(LFTk-LSTk/TI)?×UC(T(vmk))

(5)

3.3 調(diào)度模型

調(diào)度的目的是將工作流中的任務(wù)分配到具體的虛擬機中并按照既定的順序執(zhí)行.一次調(diào)度的結(jié)果可以被描述為.I={vm1，vm2，…，vm|I|}是租用的虛擬機的集合，M是任務(wù)到虛擬機的映射的集合.每一個映射可使用m=進(jìn)行描述，其含義為任務(wù)ti由vmk執(zhí)行，執(zhí)行開始時間為STik，執(zhí)行結(jié)束時間為FTik.分別用makespan(I，M)和cost(I，M)代表工作流調(diào)度結(jié)果的完工時間和執(zhí)行成本，公式(6)和公式(7)給出了它們的計算方式.

(6)

(7)

若一個已知工作流給出的最后期限為D，則工作流調(diào)度問題可描述為:

(8)

4 算法設(shè)計

本文所解決的調(diào)度問題中，一個關(guān)鍵點在于如何確定每個任務(wù)的子期限.這個問題的求解空間維度高、范圍廣且連續(xù).粒子群算法是一種隨機優(yōu)化技術(shù)，每個粒子的本質(zhì)是一個多維向量，整個算法通過漸進(jìn)式的計算進(jìn)行求解，從而得到最優(yōu)的粒子.這種算法自問世來一直被廣泛的研究和應(yīng)用.粒子群算法的特點非常適用于解決本文所面對的問題.這一部分提出了基于粒子群的動態(tài)最后期限分配方法及相應(yīng)的列表調(diào)度算法.

4.1 t-level，b-level，alap

在應(yīng)用列表調(diào)度算法時，一個任務(wù)的t-level、b-level、alap經(jīng)常被計算[8].使用tli、bli和alapi分別代表任務(wù)ti的t-level、b-level、alap值，計算方式如公式(9)～公式(11)所示:

(9)

(10)

(11)

一個任務(wù)ti的t-level值等于從入口節(jié)點tentry到ti的最長距離，它關(guān)系到任務(wù)ti最早何時可以開始執(zhí)行.b-level值等于從ti到tentry的最長距離.alap值代表了在不影響整個工作流關(guān)鍵路徑長度的前提下，任務(wù)ti的開始執(zhí)行時間可拖延到何時.在計算這些值時，每個任務(wù)的執(zhí)行時長ETi必須已知.然而在實際情況中，任務(wù)的執(zhí)行時長與分配得到的虛擬機類型有關(guān)，因此只能在調(diào)度結(jié)束后才能精確計算.本文采用了一種近似計算的方法來計算一個任務(wù)的執(zhí)行時長，如公式(12)所示:

(12)

其中，r*代表云平臺能夠提供的處理速度最快的虛擬機類型.通過此種方法可以在工作流開始調(diào)度之前計算出每個任務(wù)的t-level值，b-level值和alap值.

4.2 粒子群算法

(13)

(14)

(15)

(16)

參數(shù)w為慣性系數(shù)，取隨機數(shù).c1和c2為加速系數(shù).r1和r2為隨機數(shù).

4.3 基于粒子群算法的DY-DD

三步列表調(diào)度是非常有效的云工作流的調(diào)度算法.這種調(diào)度算法通常先進(jìn)行最后期限的分配，即將整個工作流的最后期限D(zhuǎn)分配給每一個任務(wù).通過分配，任務(wù)ti會得到一個子期限sdi.之后需要對所有任務(wù)進(jìn)行拓?fù)渑判?，從而得到一個任務(wù)隊列L.最后依次為隊列中的每一個任務(wù)配置虛擬機.配置的虛擬機盡量保證任務(wù)在子期限前執(zhí)行完成且執(zhí)行成本最小.本文提出的動態(tài)最后期限分配方法(DY-DD)將粒子群算法應(yīng)用于最后期限分配階段.為了能夠使用粒子群算法，本文所提出的算法對三步列表調(diào)度的執(zhí)行步驟進(jìn)行了改變.首先對任務(wù)進(jìn)行拓?fù)渑判蛏申犃蠰，之后利用粒子群算法找到近似最優(yōu)的最后期限分配結(jié)果，最后進(jìn)行虛擬機的配置.

(17)

其中fi代表對粒子xi進(jìn)行虛擬機配置后的最終調(diào)度結(jié)果，fj代表對粒子xj進(jìn)行虛擬機配置后的最終調(diào)度結(jié)果.若兩種調(diào)度方案的完工時間均滿足最后期限則執(zhí)行費用小的方案較優(yōu)，否則完工時間小的方案較優(yōu).

為了將粒子的移動控制在合理的空間范圍內(nèi)，需要對粒子各分量的最大值和最小值進(jìn)行設(shè)置.一個簡單的思路是將所有分量的最大值設(shè)置為D，最小值設(shè)置為0.這是因為所有任務(wù)的子期限最晚也不會超過整個工作流的最后期限，最早也不會早于0.然而由于搜索空間過大，這種設(shè)置方式會影響粒子群算法的性能.根據(jù)4.1節(jié)的介紹可知，任務(wù)ti開始執(zhí)行的時間不會早于tli，最晚開始時間也不應(yīng)當(dāng)晚于alapi，因此將粒子的最大值和最小值設(shè)置為:

(18)

(19)

(20)

(21)

為了加速粒子群收斂，本文設(shè)置了t=0時刻的全局最優(yōu)解，設(shè)置方式如公式(22)所示:

(22)

算法1給出了動態(tài)最后期限分配方法的詳細(xì)描述.算法的輸入是一個代表工作流的DAG，輸出是調(diào)度的結(jié)果.算法首先按照b_level降序順序?qū)λ腥蝿?wù)進(jìn)行拓?fù)渑判?第1行).之后初始化粒子群算法的相關(guān)參數(shù)和粒子并設(shè)置局部最優(yōu)位置及全局最優(yōu)位置(第2-3行).接下來啟動粒子群算法(第4-12行).每一個粒子都需要利用虛擬機選擇算法(算法2)進(jìn)行解碼，生成最終解決方案(第8行).利用公式(17)可以對生成的解決方案進(jìn)行比較，從而更新局部最優(yōu)位置和全局最位置(第9和11行).粒子群迭代結(jié)束后，算法返回由全局最優(yōu)位置解碼得到的解決方案，這也是整個算法計算出的最終調(diào)度方案(第13-14行).

算法 1.動態(tài)最后期限分配方法(DY-DD)

輸入:TheDAGofaworkflowG=

輸出:TheschedulingsolutionS=

1.L←listedtasksofworkflowindescendingorderbyb_level

2.Setparametersofpsoand set global best position gb

3.Initialize the population and set local best position lb of each particle

4.Whileitdoesn′tmeetiterationconditiondo

5.Foreach particlexk，k∈{1，2，…，size}do

8.DecodexktoasolutionSkbyAlgorithm 2accordingtotheorderofL

9.Updatethelocalbestpositionlbkofxk

10.Endfor

11.Updatetheglobalbestpositiongb

12.Endwhile

13.DecodegbtoasolutionSbyAlgorithm2accordingtotheorderofL

14.ReturnthesolutionS

粒子通過虛擬機選擇算法進(jìn)行解碼.算法的詳細(xì)描述如算法2所示，此算法參考了ProLis的服務(wù)選擇算法.算法2的輸入包括一個任務(wù)列表L和一個具體的粒子x，輸出是由x解碼得到的一個調(diào)度方案.L是拓?fù)渑判蚝蟮娜蝿?wù)列表，x代表L中每個任務(wù)的子期限.算法需要為L中的每一個任務(wù)選擇虛擬機，原則是滿足任務(wù)的子期限且執(zhí)行成本的增量最小(第3行).候選的虛擬就包括所有已選擇的虛擬機(集合I)以及尚未被選擇但是可以隨時被添加到I中的虛擬機.如果所有虛擬機均不能滿足一個任務(wù)的子期限，則將該任務(wù)配置到能使其最早完成的虛擬機中，并將此虛擬機升級為執(zhí)行速度最快的類型(第4-10行).至此虛擬機選擇完畢，計算任務(wù)的開始執(zhí)行時刻和執(zhí)行完成時刻并生成分配方案(11-15行).直到所有的任務(wù)均配置好虛擬機后返回最終的調(diào)度結(jié)果(第17行).

算法 2.虛擬機選擇算法

輸入:AtasklistL

Aparticlex

輸出:TheschedulingsolutionS=

1.I←φ，M←φ

2.ForeachtasktiinLdo

3.vmk←selectavmthatmeetsxiandminimizesthecostincrementofaddingti

4.Ifvmkisnullthen

5.vmk←selectavmwhichallowsearliestfinishtime

6.Whilexiisnotmet&&vmkisnotofthefastesttypedo

7.upgradethetypeofvmktoafasterlevel

8.updatefinishtimeoftasksonvmk

9.Endwhile

10.Endif

11.CalculateSTi，k，F(xiàn)Ti，kby(3)and(4)，respectively

12.M←M∪ {}

13.Ifvmk?Ithen

14.I←I∪{vmk}

15.Endif

16.Endfor

17.Return

5 仿真實驗

5.1 實驗設(shè)置

這一部分將對實驗的設(shè)置進(jìn)行介紹.本文通過仿真的方式對提出的算法進(jìn)行了驗證.仿真程序利用了文獻(xiàn)[7]所提供的開源程序，并在此基礎(chǔ)上嵌入了本文所提出的算法的源代碼.

本文選取了4種不同特點的工作流模型，它們分別是:CyberShake、Epigenomics、LIGO、Montage.這些工作流各具特色，圖3展示了這些工作流的結(jié)構(gòu)特點，更具體的描述可以參看文獻(xiàn)[25].一般來說CyberShake用于刻畫地震災(zāi)害，屬于數(shù)據(jù)密集型工作流，且需要大量的CPU資源； Epigenomics被應(yīng)用于信息生物學(xué)，本質(zhì)上是一個數(shù)據(jù)處理管道，用來自動執(zhí)行各種各樣的基因組排序操作；LIGO主要應(yīng)用于引力物理學(xué)，屬于CPU密集型工作流；Montage被應(yīng)用于天文學(xué)，任務(wù)間存在大量的I/O，CPU資源需求不高.工作流由Bharathi等人提供的工作流生成器生成.每個工作流模型下分別選擇了50個任務(wù)、100個任務(wù)、200個任務(wù)、…、900個任務(wù)、1000個任務(wù)等不同規(guī)模的工作流進(jìn)行實驗.為了減小隨機性對實驗結(jié)果造成的影響，每類模型相同規(guī)模的工作流使用了20中不同的實例.

圖3 4種工作流的結(jié)構(gòu)特征Fig.3 Structural characteristics of the four workflows

在實驗中，假設(shè)云平臺中包含9種不同類型的虛擬機，它們都擁有各自的處理能力和租用費用，詳見表1.由于工作流數(shù)據(jù)集中任務(wù)工作量被刻畫成了在標(biāo)準(zhǔn)計算資源上的運行時間而不是工作負(fù)載，因此這些虛擬機的處理能力被刻畫為標(biāo)準(zhǔn)計算資源處理速度的倍數(shù).虛擬機之間的帶寬被設(shè)置為20MBps，虛擬機租用付費的單元時長設(shè)置為1小時，這些設(shè)置都參考了Amazon EC2.

表1 可用服務(wù)類型的處理速度和成本Table 1 Processing speed and cost of available service types

為了對本文所提出的算法做出評估，選擇了IC-PCP[26]和ProLis[7]作為了對比算法.IC-PCP是經(jīng)典的滿足最后期限約束的工作流調(diào)度算法.ProLis是典型的三步列表調(diào)度算法，此算法在列表調(diào)度的基礎(chǔ)上應(yīng)用了最后期限的分配.

本文使用調(diào)度成功率和執(zhí)行成本兩個指標(biāo)對算法進(jìn)行評價.成功率越高且執(zhí)行成本越低的算法效果越好.調(diào)度算法的結(jié)果經(jīng)常受到最后期限設(shè)置的影響.過于緊張的最后期限會使得調(diào)度成功率降低且執(zhí)行成本增高，寬松的最后期限則與之相反.為了對算法做出更為全面的評價，需要在不同的最后期限設(shè)置下對算法進(jìn)行驗證，為此引入了兩個基準(zhǔn):

1)廉價調(diào)度:僅在一臺最廉價的虛擬機上使用HEFT[11]算法進(jìn)行工作流調(diào)度.Mc和Cc分別代表廉價調(diào)度的完工時間和執(zhí)行成本.

2)快速調(diào)度:僅選擇最昂貴的虛擬機進(jìn)行工作流調(diào)度，調(diào)度算法為HEFT[11].Mf和Cf分別代表快速調(diào)度的完工時間和執(zhí)行成本.

另外引入λ(λ∈ [0，1])作為最后期限的寬松程度，并將最后期限表示為:

D=MF+(MC-MF)×λ

(23)

由于最后期限由λ確定，因此可以通過設(shè)置不同的λ值來觀察不同寬松程度下各工作流調(diào)度算法的表現(xiàn).

參與實驗的工作流均具有不同的屬性，如任務(wù)數(shù)、任務(wù)負(fù)載值、數(shù)據(jù)傳輸量等，這必然導(dǎo)致調(diào)度結(jié)果的執(zhí)行成本值千差萬別.對于一個工作流，使用執(zhí)行成本除以Cc的方式對結(jié)果進(jìn)行標(biāo)準(zhǔn)化處理.

由于計算量很大，整個實驗過程使用了56臺PC機共同完成.不同的PC機負(fù)責(zé)計算不同工作流模型和最后期限設(shè)置.最后匯總各PC機的計算結(jié)果并生成相應(yīng)的圖表.表2給出了算法相關(guān)參數(shù)的設(shè)置方式.

表2 參數(shù)設(shè)置Table 2 Parameter settings

5.2 實驗結(jié)果

在進(jìn)行實驗時先另λ從0.005變化至0.05，步長為0.005；又另λ從0.1變化至0.5，步長為0.05.前者用以觀察在相對緊張的最后期限設(shè)置下各算法表現(xiàn)，后者則用以觀察在相對寬松的最后期限設(shè)置下各算法表現(xiàn).圖4給出了λ從0.005變化至0.05時各算法平均成功率.

圖4 不同λ時每種方法的成功率Fig.4 Success rate of each method at different λ

由實驗結(jié)果可知，算法的平均成功率均會隨著λ的增大而增加.設(shè)置相對較寬松的最后期限顯然可以使算法更容易找到滿足約束條件的解決方案.ProLis和DY-DD幾乎在所有情況下都能成功的找到解決方案.IC-PCP在Epigenomics和LIGO兩個模型下表現(xiàn)的十分出色；在Montage模型下，當(dāng)λ為0.005時其成功率約為91%；在CyberShake下表現(xiàn)的最差，當(dāng)λ為0.005時其成功率僅有68%.不過隨著λ的增加，IC-PCP的成功率會逐漸提升，直到λ等于0.045時，其成功率會趨近100%.

圖5給出了λ從0.005變化至0.05時各算法的標(biāo)準(zhǔn)化執(zhí)行成本.由于在不滿足截止時間約束的情況下比較成本是沒有意義的，因此圖5只給出了成功率近似100%的情形下個算法的執(zhí)行成本情況.

圖5 不同λ時每種方法的成本(0.005< λ< 0.05)Fig.5 Cost of each method when 0.005< λ< 0.05

由實驗結(jié)果可知，IC-PCP在LIGO模型下λ為0.005時表現(xiàn)的最為出色，除此之外的其它情形下表現(xiàn)最好的均為DY-DD.ProLis在大多數(shù)情況下都優(yōu)于IC-PCP，但是相比于DY-DD一直存在劣勢.

圖6給出了λ從0.1變化至0.5時各算法的標(biāo)準(zhǔn)化執(zhí)行成本.由實驗結(jié)果可知，在相對寬松的最后期限設(shè)置下，ProLis和DY-DD具有明顯的優(yōu)勢.在大多數(shù)情況下DY-DD均優(yōu)于ProLis，僅在Montage下且λ大于0.4時兩者的結(jié)果才相差無幾.

圖6 不同λ時每種方法的成本(0.1< λ< 0.5)Fig.6 Cost of each method when 0.1< λ< 0.5

5.3 算法時間復(fù)雜度分析

DY-DD算法首先需要生成調(diào)度列表(算法1第1行).其中為每個任務(wù)計算b-level的過程需要遍歷所有任務(wù)和任務(wù)間的依賴.對于一個包含n個任務(wù)的工作流，其依賴最多為n×(n+1)/2.因此整個計算過程的時間復(fù)雜度為O(n2).排序過程的時間復(fù)雜度為O(n×logn).之后需要初始化粒子群(算法1第2-3行)，這一過程需要設(shè)置初始的最優(yōu)粒子和設(shè)置粒子的速度上下限.設(shè)置速度上下限時需要利用t-level和alap，它們的計算方式與b-level類似，因此需要O(n2)的時間復(fù)雜度.設(shè)置最優(yōu)粒子需要遍歷粒子的每一個維度，即遍歷每一個任務(wù)，因此時間復(fù)雜度為O(n).初始化粒子也需要遍歷粒子的每一個維度，若粒子群的粒子數(shù)量為SIZE，則這一過程的時間復(fù)雜度為O(SIZE×n)，其中SIZE為常數(shù).對于某一次迭代，更新某一個粒子的速度、位置和局部最優(yōu)解(算法1第6-7行、算法1第9行)的時間復(fù)雜度為O(n).對粒子進(jìn)行解碼(算法1第8行)需要利用算法2，算法2需要遍歷每個粒子維度，即每一個任務(wù)，并為每一個任務(wù)選擇一個合適的虛擬機.若云平臺提供的虛擬機類型數(shù)量N，則每次選擇所需要遍歷的虛擬機數(shù)量為n+N，因此算法2的時間復(fù)雜度為O(n×(n+N))，其中N為常數(shù).若粒子群的迭代次數(shù)上限為T，則整個迭代階段(算法1第4-12行)的時間復(fù)雜度為O(T×SIZE×(n+n×(n+N)))，其時間復(fù)雜度約為O(n2).由此得出整個算法的時間復(fù)雜度為O(n2).

6 結(jié)束語

本文提出了DY-DD算法.該算法主要解決云工作流的調(diào)度問題.對于一個給定的工作流、最后期限約束和云模型，使用該算法可以找到滿足最后期限約束的調(diào)度方案且優(yōu)化了執(zhí)行成本.使用現(xiàn)實的數(shù)據(jù)進(jìn)行了實驗仿真，并與經(jīng)典的調(diào)度算法進(jìn)行了對比.實驗結(jié)果表明，DY-DD算法在成功率和執(zhí)行成本上很有競爭力.

接下來一方面試圖改進(jìn)本文提出的算法，降低算法的復(fù)雜度；另一方面也嘗試使用其它方式解決本文所研究的問題.除此之外，還將聚焦于多目標(biāo)的工作流調(diào)度.