基于均衡適應度的云工作流調度算法

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

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

0 引 言

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

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

1 相關研究

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

結合已有研究，提出一種工作流任務遺傳調度算法，利用遺傳操作實現執行時間與代價同步優化。

2 問題描述

2.1 問題定義

本文所討論的具有網絡拓撲的任務調度問題可定義為分配應用中的任務至處理器集合的問題，同時以最小化總執行時間為目標。因此，任務調度輸入包括一個任務圖和處理器圖，輸出為一個調度方案，代表每個應用任務節點與處理器間的映射關系。先給出本文中應用的符號說明，如表1所示。

表1 符號說明

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

圖1 DAG任務圖示例

假設任務執行環境滿足以下條件：

條件1：任務不能開始執行，直到其所有輸入已經匯聚為止。每個任務僅出現在一個調度中。

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

(1)

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

條件3：令[tA,tB]∈[0,∞]表示處理器Pj上無任務執行的空閑時間間隔。任務vi∈V可在[tA,tB]內被調度至Pj，若滿足：

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

(2)

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

圖2 處理器圖

2.2 基于遺傳的任務調度算法設計

給定任務圖G=(V,E,w,c)和具有網絡拓撲的處理器圖TG=(N,D)，算法目標是選擇最佳調度方案執行任務，本文選擇遺傳算法對任務調度進行優化，命名算法為CTAGA算法。

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

圖3 遺傳步驟

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

圖4 一維排列表示的個體

可見，一維排列不適合于表示工作流任務，由于它僅定義了哪個處理器被分配至每個任務，而無法顯示任務分配至每個處理器的順序。然而，執行順序對于工作流應用是必需考慮的。本文使用一種二維排列表示一個調度方案，如圖5所示。在二維排列中可以顯示每個處理器上的任務序列。在遺傳操作過程中，二維排列可轉化為一維排列。

圖5 二維排列

2) 種群初始化 初始化種群通過隨機啟發式方法產生的個體集合組成。每個個體由任務與分配的處理器的配對構成。

3) 適應度函數 適應度函數用于量化種群中每個個體的優劣。根據適應度值，父個體被選擇產生子代。由于算法目標是最小化調度長度，同時考慮網絡連接與用戶代價，適應度函數則需要取決于EFT和用戶支付代價。以下闡述EFT和任務在處理器上的執行代價問題。

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

(3)

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

(4)

(5)

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

(6)

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

(7)

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

處理代價為：

(8)

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

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

(9)

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

(10)

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

(11)

進一步，可計算任務vi使用處理器Pj的內存代價為：

(12)

式中：smem為利用的內存大??；c5為單位數據的內存代價。

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

(13)

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

4) 遺傳操作

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

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

圖6 單點交叉

圖7 兩點交叉

圖8 均勻交叉

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

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

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

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

④ 通過聯立父個體的兩個部分得到新的子代個體。

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

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

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

圖9 變異操作

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

算法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 實驗配置

本節通過數值仿真評估算法性能，實驗參數如表2所示。利用CloudSim及JDK-7u7-i586 JAVA環境進行實驗，通過CloudSim可以構建模擬云基礎設施和服務模型。仿真中利用Million Instructions per Second MIPS描述處理器的處理能力。

表2 參數配置

3.2 實驗結果

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

圖10 調度長度比較

圖11 代價比較

算法任務數量20406080100GCA0.250.290.340.390.44CASA0.230.250.310.350.40CTAGA0.160.180.220.250.28

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

圖12 處理器數量對調度長度和代價的影響

圖13 迭代次數對調度長度和代價的影響

最后，實驗還觀察了CTAGA算法在不同個體數量下的性能情況。如圖14所示，當個體數量從30變為90時，可以看到種群規模的增加并沒有極大影響執行代價，而找到最快解的概率則在變高。另一方面，調度時間在78 min后的50 min里展現出下降趨勢。

圖14 個體數量對調度長度和代價的影響

4 結 語

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