基于均衡適應(yīng)度的云工作流調(diào)度算法

方 軍 張 璋 張雪峰 杜 聰 馬 濤 劉 鑫

1(國家質(zhì)量監(jiān)督檢驗檢疫總局信息中心 北京 100088)2(北京中質(zhì)信維科技有限公司 北京 100088)3(北京賽迪工業(yè)和信息化工程監(jiān)理中心有限公司 北京 100048)4(石家莊鐵道大學(xué)信息學(xué)院 河北 石家莊 050043)

0 引 言

云計算環(huán)境中，資源可根據(jù)應(yīng)用需求動態(tài)地分配至用戶任務(wù)，而用戶對資源的付費方式是即付即用的，這極大地區(qū)別于傳統(tǒng)的分布式計算環(huán)境[1]。這種特有的使用特征使得云計算提供了對科學(xué)工作流調(diào)度的最好支持[2]。每一種大規(guī)模的工作流應(yīng)用均可建模為有向無循環(huán)圖結(jié)構(gòu)，結(jié)構(gòu)中包含有大量相互依賴或相互獨立的任務(wù)，有些可同步調(diào)度執(zhí)行，而有些則需要按照嚴(yán)格的先后次序調(diào)度執(zhí)行。為了滿足用戶對于應(yīng)用任務(wù)執(zhí)行的不同QoS需求，云環(huán)境中的工作流調(diào)度需要尋找有效可行的調(diào)度方案，實現(xiàn)工作流任務(wù)與多資源間的映射與執(zhí)行。

云環(huán)境中任務(wù)調(diào)度的主要目標(biāo)是如何為每個任務(wù)選擇合適資源，并決定任務(wù)在資源上的執(zhí)行序列，同時滿足用戶給定的QoS需求[3]。已有工作流調(diào)度系統(tǒng)多優(yōu)化調(diào)度效率忽略了優(yōu)化代價。由于云服務(wù)使用的有償性，優(yōu)化調(diào)度代價將具有更加重要的意義。同時，云資源使用具有自身特點：資源在用戶間共享與競爭并存，資源可用性具有變化性，資源異構(gòu)且即付即用等?；谝陨峡紤]，必須研究新的工作流調(diào)度算法以適應(yīng)云資源使用的特性及滿足用戶方的多需求性。

1 相關(guān)研究

任務(wù)調(diào)度問題重點關(guān)注于任務(wù)與資源間的映射及執(zhí)行管理，通常，該問題是NP難問題。因此，在多項式時間內(nèi)尋找其最優(yōu)解理論上是不可能的。當(dāng)前有關(guān)任務(wù)調(diào)度算法的研究可總結(jié)出以下幾種類型：1) 代價最優(yōu)，截止期限約束。文獻(xiàn)[4]提出動態(tài)代價有效截止時間約束啟發(fā)式調(diào)度算法，實現(xiàn)公有云的單一工作流調(diào)度。文獻(xiàn)[5]提出一種代價最優(yōu)化算法，利用任務(wù)復(fù)制機(jī)制增加滿足應(yīng)用截止期限的概率。除了以上啟發(fā)式算法，文獻(xiàn)[6-7]則利用搜索算法和元啟發(fā)式算法優(yōu)化了相同目標(biāo)。2) 時間最優(yōu)，預(yù)算約束。工作流的預(yù)算定義為用戶執(zhí)行任務(wù)向資源方支付的最大費用。文獻(xiàn)[8-10]提出了啟發(fā)式算法最小化執(zhí)行時間，同時需要滿足預(yù)算約束。文獻(xiàn)[11]提出安全與預(yù)算感知工作流調(diào)度算法，可在滿足安全級別的同時降低總執(zhí)行時間。3) 時間最優(yōu)，代價最優(yōu)。部分工作嘗試在最小化時間和代價兩種QoS參數(shù)間取得均衡。文獻(xiàn)[12]提出關(guān)鍵路徑優(yōu)先算法CPF，利用工作流的擴(kuò)展與壓縮機(jī)制優(yōu)化時間和代價。文獻(xiàn)[13]提出滿足Pareto最優(yōu)的代價-時間最優(yōu)調(diào)度算法。同樣地，利用Pareto最優(yōu)的概念，文獻(xiàn)[14]通過設(shè)置反映用戶對于時間和代價偏好的代價有效因子，提出執(zhí)行時間和代價最小化調(diào)度算法。然而，以上研究是考慮一個QoS為約束而優(yōu)化另一個QoS，或者同時優(yōu)化代價和時間，不同于以上研究，本文將同時考慮時間和代價的約束，并同時對兩種QoS進(jìn)行優(yōu)化。

結(jié)合已有研究，提出一種工作流任務(wù)遺傳調(diào)度算法，利用遺傳操作實現(xiàn)執(zhí)行時間與代價同步優(yōu)化。

2 問題描述

2.1 問題定義

本文所討論的具有網(wǎng)絡(luò)拓?fù)涞娜蝿?wù)調(diào)度問題可定義為分配應(yīng)用中的任務(wù)至處理器集合的問題，同時以最小化總執(zhí)行時間為目標(biāo)。因此，任務(wù)調(diào)度輸入包括一個任務(wù)圖和處理器圖，輸出為一個調(diào)度方案，代表每個應(yīng)用任務(wù)節(jié)點與處理器間的映射關(guān)系。先給出本文中應(yīng)用的符號說明，如表1所示。

表1 符號說明

定義1以有向無循環(huán)圖DAG表示一個任務(wù)圖G=(V,E,w,c)，如圖1所示，頂點集V={v1,v2,…,vk}表示并行子任務(wù)集合，有向邊集eij=(vi,vj)∈E描述子任務(wù)vi與vj間的通信關(guān)系，w(vi)表示任務(wù)vi的計算時間，c(eij)表示對應(yīng)傳輸數(shù)據(jù)d(eij)所需要的任務(wù)vi與vj間的通信時間。若任務(wù)vi不存在任一前驅(qū)，則Pred(vi)=0，稱為一個入口任務(wù)ventry。若不存在任一后繼，則succ(vi)=0，稱為一個終止任務(wù)vend。任務(wù)由負(fù)載wli組成，定義了任務(wù)在計算資源上處理的工作量。任務(wù)也可由前驅(qū)子任務(wù)集prec(vi)和后繼子任務(wù)集succ(vi)構(gòu)成，ts(vi,Pj)表示任務(wù)vi在處理器資源Pj上的開始時間，w(vi,Pj)表示執(zhí)行時間。因此，任務(wù)的完成時間為tf(vi,Pj)=ts(vi,Pj)+w(vi,Pj)。

圖1 DAG任務(wù)圖示例

假設(shè)任務(wù)執(zhí)行環(huán)境滿足以下條件：

條件1：任務(wù)不能開始執(zhí)行，直到其所有輸入已經(jīng)匯聚為止。每個任務(wù)僅出現(xiàn)在一個調(diào)度中。

條件2：就緒時間tready(vi,Pj)表示處理器Pj完成其最后一個分配任務(wù)準(zhǔn)備執(zhí)行任務(wù)vi的時間。因此，

(1)

式中:exec(j)表示執(zhí)行于處理器Pj上的任務(wù)集，tf(ezi)=tf(vz)+c(ezi)，prec(vi)表示vi的前驅(qū)任務(wù)集。

條件3：令[tA,tB]∈[0,∞]表示處理器Pj上無任務(wù)執(zhí)行的空閑時間間隔。任務(wù)vi∈V可在[tA,tB]內(nèi)被調(diào)度至Pj，若滿足：

max{tA,tready(vi,Pj)}+w(vi,Pj)≤tB

(2)

定義2處理器圖TG=(N,D)表示描述處理器相互網(wǎng)絡(luò)關(guān)聯(lián)的結(jié)構(gòu)圖，如圖2所示。模型中，N為有限頂點集，有向邊dij∈D表示頂點Pi至頂點Pj間的有向邊，Pi,Pj∈N。每個處理器Pi可控制其與其他處理器間的處理速率pi和鏈路帶寬bwi。

圖2 處理器圖

2.2 基于遺傳的任務(wù)調(diào)度算法設(shè)計

給定任務(wù)圖G=(V,E,w,c)和具有網(wǎng)絡(luò)拓?fù)涞奶幚砥鲌DTG=(N,D)，算法目標(biāo)是選擇最佳調(diào)度方案執(zhí)行任務(wù)，本文選擇遺傳算法對任務(wù)調(diào)度進(jìn)行優(yōu)化，命名算法為CTAGA算法。

遺傳算法的一般步驟如圖3所示，它是受自然物種進(jìn)化啟發(fā)的一種強(qiáng)大的解空間搜索方法。相比其他算法僅能找到局部最優(yōu)解，遺傳算法GA可以利用過去搜索到的最優(yōu)解去擴(kuò)展新的解空間搜索區(qū)域。算法中，一個可行解即為一個個體，即染色體，本文中所考慮的將任務(wù)分配至可用的處理器集中即為染色體中的一個基因。算法可以維持一個隨機(jī)產(chǎn)生個體的種群進(jìn)化多代，種群中個體的質(zhì)量由適應(yīng)度函數(shù)進(jìn)行評估，具有較高適應(yīng)度值的個體代表質(zhì)量較好的調(diào)度解?；谶m應(yīng)度，父代被選擇產(chǎn)生子代，即通過交叉、變異操作，產(chǎn)生新的染色體種群，這樣可以改進(jìn)染色體質(zhì)量。最終，新的種群將逐漸收斂至最優(yōu)解。以下具體描述算法的實現(xiàn)細(xì)節(jié)。

圖3 遺傳步驟

1) 個體表示 選擇種群的一個個體(見圖4)描述調(diào)度問題的一個可行解，個體包含任務(wù)分配的排列。每個分配由一個任務(wù)和相應(yīng)的分配處理器組成。每個個體中任務(wù)的最早開始時間和最早完成時間，可以改變其后繼任務(wù)的相關(guān)時間。而這種改變可能導(dǎo)致遺傳算法更加復(fù)雜的狀態(tài)。

圖4 一維排列表示的個體

可見，一維排列不適合于表示工作流任務(wù)，由于它僅定義了哪個處理器被分配至每個任務(wù)，而無法顯示任務(wù)分配至每個處理器的順序。然而，執(zhí)行順序?qū)τ诠ぷ髁鲬?yīng)用是必需考慮的。本文使用一種二維排列表示一個調(diào)度方案，如圖5所示。在二維排列中可以顯示每個處理器上的任務(wù)序列。在遺傳操作過程中，二維排列可轉(zhuǎn)化為一維排列。

圖5 二維排列

2) 種群初始化 初始化種群通過隨機(jī)啟發(fā)式方法產(chǎn)生的個體集合組成。每個個體由任務(wù)與分配的處理器的配對構(gòu)成。

3) 適應(yīng)度函數(shù) 適應(yīng)度函數(shù)用于量化種群中每個個體的優(yōu)劣。根據(jù)適應(yīng)度值，父個體被選擇產(chǎn)生子代。由于算法目標(biāo)是最小化調(diào)度長度，同時考慮網(wǎng)絡(luò)連接與用戶代價，適應(yīng)度函數(shù)則需要取決于EFT和用戶支付代價。以下闡述EFT和任務(wù)在處理器上的執(zhí)行代價問題。

任務(wù)的開始時間定義為其最后一個前驅(qū)任務(wù)的完成時間。因此，為了決定開始時間，需要搜索滿足條件2和條件3時處理器Pj上的最早空閑時間間隔[tA,tB]。任務(wù)vi在處理器Pj上的開始時間ts設(shè)置為：

(3)

因此，任務(wù)vi在處理器Pj上的最早開始時間計算為：

(4)

(5)

EFT(vi,Pj)=w(vi,Pj)+EST(vi,Pj)

(6)

另外，算法同時考慮用戶執(zhí)行任務(wù)時的需要支付的代價。任務(wù)vi在處理器Pj上的執(zhí)行代價定義為：

(7)

式(7)中的代價定義如下：

處理代價為：

(8)

式中：c1為處理器Pj以處理速率pj執(zhí)行工作流時單位時間的代價。

令tmin為并行任務(wù)中第一個完成任務(wù)的完成時間，c2為單位時間任務(wù)的等待代價，ti為任務(wù)vi的完成時間，則等待時間代價為：

(9)

令c3為從處理器Pj傳輸數(shù)據(jù)時單位時間的代價，則通信時間代價為：

(10)

令c4為單位數(shù)據(jù)的存儲代價，sti為任務(wù)vi在處理器Pj上的存儲數(shù)據(jù)量，則存儲代價為：

(11)

進(jìn)一步，可計算任務(wù)vi使用處理器Pj的內(nèi)存代價為：

(12)

式中：smem為利用的內(nèi)存大?。籧5為單位數(shù)據(jù)的內(nèi)存代價。

基于以上代價，可以建立同步考慮計算代價與EFT間的均衡適應(yīng)度函數(shù)U(vi,Pj)：

(13)

通過聯(lián)立考慮cost(vi,Pj)和EFT(vi,Pj)的適應(yīng)度函數(shù)，可以決定種群中哪個個體是最適合滿足適應(yīng)度的個體，即應(yīng)計算其最小值。

4) 遺傳操作

(1) 選擇。根據(jù)種群個體適應(yīng)度選擇新的個體。個體選擇為父代的概率正比于適應(yīng)度值。均衡值越小的個體越優(yōu)秀。

(2) 交叉。個體的交叉操目標(biāo)是從當(dāng)前種群中隨機(jī)選擇兩個個體(父個體)進(jìn)行遺傳交叉以產(chǎn)生新的個體，從而在子代中獲得更好的個體。算法引入三種交叉方法：單點交叉、兩點交叉(或多點交叉)和均勻交叉。交叉概率設(shè)置為在區(qū)間[0.6,1]。具體示例分別如圖6、圖7和圖8所示。

圖6 單點交叉

圖7 兩點交叉

圖8 均勻交叉

交叉操作將由以下步驟決定：

① 從父個體中隨機(jī)選擇一個、兩個(或多個)交叉點；

② 以上隨機(jī)點將每個個體劃分為左右兩部分；

③ 交叉互換兩個個體的左右兩個部分；

④ 通過聯(lián)立父個體的兩個部分得到新的子代個體。

單點交叉中(圖6)，在個體中隨機(jī)選擇一個位置。第一個子個體即為聯(lián)立第一個父個體的左邊部分和第二個父個體的右邊部分得到的，第二個子個體即為聯(lián)立第二個父個體的左邊部分和第一個父個體的右邊部分得到的。兩點交叉中，需要隨機(jī)選擇個體中的兩個位置，如圖7所示。兩點交叉的好處在于可以避免單點交叉的固有問題，即確定染色體的頭部基因和尾部基因總是分裂的。均勻交叉中，先隨機(jī)產(chǎn)生一個二進(jìn)制序列(圖8)，該序列決定哪些比特從父個體中進(jìn)行復(fù)制。比特值表示每個個體中元素的位置，比特密度決定個體如何交叉。遺傳算法在實現(xiàn)過程中將根據(jù)種群大小各取三分之一的種群分別進(jìn)行三種交叉操作。

(3) 變異。遺傳算法中，變異操作可以從當(dāng)前種群中的單個個體上產(chǎn)生新的子代，變異可以通過搜索新的更佳的基因維持個體的多樣性，以避免問題解陷入局部最優(yōu)。算法引入兩種變異操作：交換變異和替換變異。遺傳算法在實現(xiàn)過程中將根據(jù)種群大小各取交叉后的一半種群分別進(jìn)行兩種變異操作。

交換變異的目標(biāo)是在個體上重新分配處理器至一個隨機(jī)任務(wù)。所選處理器為隨機(jī)選擇，且具有執(zhí)行該任務(wù)的能力。圖9(a)描述了一種交換變異情形，其中，分配至任務(wù)v4的處理器P2交換為處理器P4。相比而言，互換變異則是在相同時槽內(nèi)改變一個個體中相同處理器上獨立任務(wù)的執(zhí)行次序。圖9(b)是一種互換變異情形，任務(wù)v0和v5進(jìn)行了互換變異。

圖9 變異操作

本文設(shè)計了幾種任務(wù)調(diào)度算法進(jìn)行性能比較，這些算法均是最小化工作流調(diào)度長度或調(diào)度代價為目標(biāo)的。算法1為貪婪優(yōu)化算法GCA，算法將每個工作流任務(wù)分配至執(zhí)行代價最小的處理器上。算法2為內(nèi)容感知調(diào)度算法CASA，算法通過網(wǎng)絡(luò)連接狀況建立了一個基于最早完成時間的調(diào)度表，并依該表進(jìn)行任務(wù)調(diào)度。算法3即為本文所設(shè)計的同步考慮網(wǎng)絡(luò)連接內(nèi)容與代價的調(diào)度算法CTAGA，算法可以實現(xiàn)在執(zhí)行時間與代價間均衡的調(diào)度，并得到全局最優(yōu)解。三種算法的偽代碼如下所示：

算法1GCA偽代碼

1Input:G=(V,E,w,c),TG=(N,D)

2Output: A new task scheduling

3FunctionGCA(G,TG)

4 Sort taskvn∈Vinto list L according to priority

5Forvn∈V

6 Find the best processorPjwhich minimize the execution cost of taskvn

7 AssignvnonPj

8Returna new task scheduling

算法2CASA偽代碼

1Input:G=(V,E,w,c),TG=(N,D)

2Output: A new task scheduling

3FunctionCASA(G,TG)

4 Sort taskvn∈Vinto listLaccording to priority

5Forvn∈V

6 Find the best processorPjwhich allow EFT ofvn,taking account of network bandwidth usage

7 AssignvnonPj

8Returna new task scheduling

算法3CTAGA偽代碼

1Input:G=(V,E,w,c),TG=(N,D)

2Output: A new task scheduling

3FunctionCTAGA(G,TG)

4 Generate initial population

5 Compute fitness of each individual according to Fitness Function

6Repeat//New generation

7Forpopulation_size

8 Select two parent from old generation

9 Recombine fitness for two offspring

10Insert offspring in new generation

11Untilpopulation has converged

3 實驗分析

3.1 實驗配置

本節(jié)通過數(shù)值仿真評估算法性能，實驗參數(shù)如表2所示。利用CloudSim及JDK-7u7-i586 JAVA環(huán)境進(jìn)行實驗，通過CloudSim可以構(gòu)建模擬云基礎(chǔ)設(shè)施和服務(wù)模型。仿真中利用Million Instructions per Second MIPS描述處理器的處理能力。

表2 參數(shù)配置

3.2 實驗結(jié)果

圖10-圖11是本文算法與對比算法的性能比較情況。圖10表明GCA算法得到了最差性能，CASA在調(diào)度長度上性能最優(yōu)，而本文算法處于中間，優(yōu)于GCA算法20%左右。然而，在圖11中的代價方面，盡管CASA擁有最佳的性能，但它卻擁有最高的代價。CTAGA在調(diào)度長度與代價方面起到了很好的均衡，通過與CASA比較，CTAGA能夠為用戶節(jié)省約20%的代價；與GCA比較，CTAGA則能節(jié)省約25%的調(diào)度時間。表3是三種算法在不同任務(wù)數(shù)量的情況下得到的均衡適應(yīng)度的值的情況。雖然本文算法CTAGA在三種算法中無法同步實現(xiàn)調(diào)度長度和調(diào)度代價的最優(yōu)，但其得到的均衡適應(yīng)度值是三種算法中最小的，這表明算法選擇的個體在調(diào)度時間和代價的綜合性能上是最優(yōu)的。

圖10 調(diào)度長度比較

圖11 代價比較

算法任務(wù)數(shù)量20406080100GCA0.250.290.340.390.44CASA0.230.250.310.350.40CTAGA0.160.180.220.250.28

實驗還觀察了處理器數(shù)量和迭代次數(shù)對CTAGA算法得到的代價和調(diào)度長度的影響，結(jié)果如圖12和圖13所示。結(jié)果表明，處理器數(shù)量越多，系統(tǒng)性能越好，但是代價也越高。當(dāng)遺傳代數(shù)逐步增加時，工作流調(diào)度長度會隨著代價的降低而降低，這是由于每個所選個體需要同步考慮代價和執(zhí)行時間因素導(dǎo)致的。

圖12 處理器數(shù)量對調(diào)度長度和代價的影響

圖13 迭代次數(shù)對調(diào)度長度和代價的影響

最后，實驗還觀察了CTAGA算法在不同個體數(shù)量下的性能情況。如圖14所示，當(dāng)個體數(shù)量從30變?yōu)?0時，可以看到種群規(guī)模的增加并沒有極大影響執(zhí)行代價，而找到最快解的概率則在變高。另一方面，調(diào)度時間在78 min后的50 min里展現(xiàn)出下降趨勢。

圖14 個體數(shù)量對調(diào)度長度和代價的影響

4 結(jié) 語

針對工作流任務(wù)調(diào)度優(yōu)化問題，提出了一種云工作流任務(wù)多目標(biāo)調(diào)度遺傳算法。在個體編碼方面，算法采用了一種二維排列編碼方法。另外，在適應(yīng)度設(shè)計方面，設(shè)計了一種考慮任務(wù)執(zhí)行代價與最早完成時間的均衡適應(yīng)度函數(shù)。同時，引入了三種遺傳交叉操作和兩種遺傳變異操作，增加了最優(yōu)解的求解概率。實驗結(jié)果表明，新算法在執(zhí)行代價與調(diào)度效率間可以實現(xiàn)更好的均衡優(yōu)化，是有效可行的。