基于遺傳算法的批處理科學工作流任務調(diào)度算法的改進

熊聰聰，陳長博，趙 青，林 穎

(天津科技大學人工智能學院，天津 300457)

基于批處理的工作流廣泛應用于多個領(lǐng)域，尤其是在數(shù)據(jù)分析應用中，例如移動領(lǐng)域、電子商務和科學研究，其原理是通過一系列的連接操作來處理大量數(shù)據(jù)[1].科學領(lǐng)域的計算任務通常被建模為科學工作流形式，其任務根據(jù)數(shù)據(jù)流與計算相關(guān)性形成鏈式結(jié)構(gòu)，由于科學計算領(lǐng)域通常存在數(shù)據(jù)量巨大和計算復雜度高的問題，需要高性能計算環(huán)境支持運行[2].兩者最主要的區(qū)別為：科學工作流主要以數(shù)據(jù)為中心，而傳統(tǒng)工作流更注重業(yè)務過程的自動化.云計算作為近年來最火熱的網(wǎng)絡服務方式為科學工作流提供了高效、高性價比、可擴展的運行支撐環(huán)境[2-3].當前，基于云平臺的科學工作流的調(diào)度研究已成為一個研究熱點，國內(nèi)外已有很多成果面世.例如，2018 年Anwar 等[4]提出了一種基于工作流程(DSB)的任務包的動態(tài)調(diào)度策略，用于調(diào)度科學的工作流，目的是在用戶定義的期限約束下最小化租賃虛擬機的租用成本.Liu 等[5]提出了一種新的基于任務回填的科學工作流調(diào)度策略，使用task backfill 算法在虛擬機實例上聚合多個任務，使用合適的性能，并利用單個任務填充虛擬機的空閑時間槽，在不影響整體性能的情況下提高資源利用率.Zhao 等[6-7]針對異構(gòu)云環(huán)境，提出了一種基于數(shù)據(jù)依賴聚類和遞歸劃分的數(shù)據(jù)聚類算法，并將數(shù)據(jù)大小和固定位置的因素結(jié)合起來.然后，提出了一種啟發(fā)式的樹對樹數(shù)據(jù)布局策略，以使頻繁的數(shù)據(jù)移動發(fā)生在高帶寬的信道上.之后，又在此基礎(chǔ)上提出了面向科學工作流模型的任務調(diào)度算法[8]，可以在提高執(zhí)行效率的同時，提高計算資源利用率，減少能源消耗.

然而，隨著大數(shù)據(jù)時代的到來，一種新型的科學工作流模型——批處理科學工作流逐漸引起人們的注意.為了提高大數(shù)據(jù)時代數(shù)據(jù)密集型應用的計算效率，工作流中的很多任務需要通過數(shù)據(jù)劃分為可并行處理的任務組，從而在原始簡單的有向無環(huán)圖(directed acyclic graph，DAG)上形成了一個個包含批處理操作的寬節(jié)點結(jié)構(gòu).

當前，關(guān)于批處理科學工作流的云調(diào)度研究正處于起步階段，傳統(tǒng)科學工作流調(diào)度中的deadline 劃分、虛機映射等方法并不適合于批處理科學工作流模型.因此，本文將重點關(guān)注批處理科學工作流的特征，在研究批處理科學工作流任務調(diào)度過程中，盡可能滿足用戶所提供的deadline 的情況，尋找調(diào)度成本最低的虛擬機資源分配方式.云批處理科學工作流的任務調(diào)度包括兩個層次：一是任務包與VM 之間的映射，二是在單個VM 上的順序執(zhí)行[9].本文重點關(guān)注第一個層次，在滿足或相對滿足任務截止期的情況下，工作流調(diào)度的成本最優(yōu)化，尋找最優(yōu)調(diào)度方案.

相關(guān)研究中，Mao[10]開發(fā)了一個工作流計算系統(tǒng)GreePipe，該系統(tǒng)可以將工作流描述自動轉(zhuǎn)換成一系列基于Hadoop 的MapReduce 任務，實現(xiàn)生物研究領(lǐng)域復雜的數(shù)據(jù)分析邏輯.該工作流屬于不可拆分工作流.對于可拆分批處理工作流，大多數(shù)工作都直接采用更細的粒度進行建模，并直接采用一些非線性的DAG 圖進行表示，并作為多個單獨的MapReduce 任務處理，這樣的建模方式，丟失了批結(jié)構(gòu)信息.雖然很多針對一般工作流的調(diào)度算法可以用于批處理工作流，但是，由于沒有考慮批處理工作流的批結(jié)構(gòu)特點，容易導致較低的資源利用率.

Cai 等[11]提出了一種最少新租賃時間區(qū)間優(yōu)先規(guī)則、最便宜執(zhí)行成本優(yōu)先規(guī)則和剩余時間片長度和執(zhí)行時間匹配度優(yōu)先規(guī)則的混合式啟發(fā)算法.但是，該算法初始虛擬機資源分配方案的原則是選用最多的性能最差的虛擬機類型，并以最大并行度的方式執(zhí)行批處理任務調(diào)度.如果調(diào)度時間超出了用戶提出的deadline，就會升級關(guān)鍵路徑上任務節(jié)點使用的虛擬機類型.因此，最終所得解傾向于租用大量低成本的虛擬機類型，容易陷入局部最優(yōu).

與上述已有方法相比，本文改進了遺傳算法中的初始種群生成過程，使初始種群覆蓋面更廣；優(yōu)化適應度函數(shù)，使其更適合評估批處理科學工作流下的個體適應度值；引入非關(guān)鍵路徑虛擬機使用數(shù)量收縮操作，在不影響關(guān)鍵路徑的前提下進一步減少任務調(diào)度成本.

1 批處理科學工作流任務調(diào)度模型任務模型

為了方便描述，對批處理科學工作流進行如下建模：

(1)圖1 為一個標準的批處理科學工作流DAG，對于一個標準的DAG 圖來說，入口節(jié)點是其他所有任務的前驅(qū)節(jié)點，其優(yōu)先度是最高的，故在所有任務節(jié)點中入口節(jié)點應該最先獲得調(diào)度，出口節(jié)點與之同理.

(2)需要進行任務調(diào)度的任務批為 T = (t1, t2,…,tn)，其中 ti代表編號為i 的任務節(jié)點.在每一個任務節(jié)點上包含若干個子任務，即ti(k )代表ti任務節(jié)點上的第k 個任務包.

(3)定義批處理科學工作流為有向無環(huán)圖DAG，任務節(jié)點ti為有向無環(huán)圖DAG 上的一個節(jié)點.

(4)假設(shè)云平臺提供m 種不同類型的虛擬機，將任務節(jié)點ti上的q 個子任務調(diào)度到不同虛擬機上的期望運行時間(t)是一個q×m 的矩陣，其計算公式見式(1).矩陣的第i 行表示任務節(jié)點i 的所有子任務在每一種虛擬機上的預測執(zhí)行時間；而第j 列表示每個任務節(jié)點的所有任務在單個第j 類虛擬機上運行所需的預估時間.預估時間由兩部分組成，一部分為單個虛擬機執(zhí)行任務所必需的時間，第二部分為虛擬機啟動和安裝軟件的時間.

圖1 標準批處理科學工作流DAG圖Fig.1 DAG diagram of standard batch processing science workflow

2 批處理科學工作流任務調(diào)度

遺傳算法是受達爾文進化論啟發(fā)進而產(chǎn)生的一種全局搜索和優(yōu)化算法.它把每一個總?cè)簝?nèi)的個體看作一種解，通過模仿自然界中優(yōu)勝劣汰的法則，使優(yōu)秀的個體留下，并進行交叉變異繼續(xù)尋找更優(yōu)解，同時將劣質(zhì)的個體淘汰，最終通過不斷的算法迭代得到最優(yōu)解[12].

本文采用基于改進遺傳算法的智能啟發(fā)式算法，以盡可能搜索到在盡量滿足工作流整體deadline 要求前提下的任務調(diào)度總成本最優(yōu)的虛擬機資源分配方案，對可隨意分割的批處理科學工作流任務調(diào)度和不可隨意分割的批處理科學工作流任務調(diào)度進行論述.可隨意分割的批處理科學工作流是指：在該科學工作流上的每一個節(jié)點上的任務包可以根據(jù)虛擬機數(shù)量隨意分割進行并行處理，使得每個虛擬機上的負載是均衡的.不可隨意分割的批處理科學工作流是指：在該科學工作流上的每一個節(jié)點上有一定數(shù)量的任務包，任務包不可分割.在本文中假設(shè)每個任務包的處理時間是相同的.

2.1 可隨意分割批處理科學工作流調(diào)度

2.1.1 編碼方式

本文采用整數(shù)編碼的方式，編碼長度取決于任務節(jié)點數(shù).每一條染色體都對應一個任務解.假設(shè)任務節(jié)點數(shù)N＝5，可用虛擬機類型數(shù)量為M＝6，則染色體(1，3，2，4，3，3，4，1，5，2)代表在任務節(jié)點一上使用3 個1 號虛擬機并行執(zhí)行，在任務節(jié)點二上使用4個2 號虛擬機并行執(zhí)行，在任務節(jié)點三上使用3 個3號虛擬機并行執(zhí)行，在任務節(jié)點四上使用1 個4 號虛擬機串行執(zhí)行，在任務節(jié)點五上使用2 個5 號虛擬機并行執(zhí)行.

2.1.2 優(yōu)化初始種群生成

傳統(tǒng)遺傳算法的初始種群生成可能存在初始種群生成覆蓋度不夠廣、初始種群生成重復率高的缺點，從而導致算法無法收斂到全局最優(yōu)解.本文對遺傳算法的初始化種群處理如下：

為了保證初始解距離最優(yōu)解距離不至于太遠，在生成初始解的過程中引入時間成本比概念，即采用滿足任務執(zhí)行需求的最低端配置虛擬機類型，在增加虛擬機使用數(shù)量的同時與串行執(zhí)行相比，調(diào)度時間減少量與成本增加量之間的比值.

(1)在生成初始解時選取三分之一初始解為每個任務節(jié)點選取一個時間減少量與成本增加量之間的比值，并選取比該比值小的所有虛擬機使用類型方案，按照任務節(jié)點順序以全組合方式生成初始解.其主要目的是使這一部分生成的初始種群先天就相對較優(yōu)，提升算法的收斂速度和準確度.

(2)在批處理科學工作流任務調(diào)度每一個任務節(jié)點內(nèi)所包含的任務包對應需求的虛擬機類型可能不同，例如有些任務節(jié)點所包含的任務為數(shù)據(jù)密集型任務，有的則為計算密集型，因此在云提供商平臺中會提供各種側(cè)重點不同的虛擬機類型.為了進一步保證初始解相對較優(yōu)，三分之一初始解按照每個任務節(jié)點所對應需求類型的虛擬機類型進行隨機生成.

為了保證初始解的隨機性，三分之一初始解按照完全隨機的方式進行初始解生成.

2.1.3 適應度函數(shù)

在遺傳算法中，適應度函數(shù)是用來衡量一個解的好壞的，本文以調(diào)度成本最優(yōu)以及調(diào)度時間盡量滿足截止期為優(yōu)化目標，由于在該模型下，每個任務節(jié)點開始進行任務調(diào)度的時間依賴于前序節(jié)點的結(jié)束時間且任務節(jié)點與任務節(jié)點之間可以并行執(zhí)行，因此整個批處理科學工作流的任務調(diào)度完成時間取決于該批處理科學工作流關(guān)鍵路徑上的任務節(jié)點進行任務調(diào)度的總時間.而對于同一個批處理科學工作流來說，關(guān)鍵路徑的選擇取決于虛擬機的具體配置情況，比如：給定一個批處理科學工作流，在該科學工作流中至少存在一條或多條路徑可以從初始節(jié)點通往最終節(jié)點，而在某種虛擬機類型和數(shù)量的配置下對于該科學工作流，其從初始節(jié)點通往最終節(jié)點耗時最長的一條路徑為該科學工作流的關(guān)鍵路徑，耗時即為該科學工作流的調(diào)度總時長.

第y 個任務節(jié)點使用j 個i 類虛擬機的執(zhí)行任務所需時間(ty)的計算公式見式(2).

式中：tyi為單個i 類虛擬機執(zhí)行第y 個任務節(jié)點所需的預估時間；tbi為虛擬機的啟動以及執(zhí)行軟件的安裝時間.

任務調(diào)度總時間為該批處理科學工作流上關(guān)鍵路徑節(jié)點任務調(diào)度所需時間之和.

第y 個任務節(jié)點使用j 個i 類虛擬機的執(zhí)行任務所需的總費用(Cy)的計算公式見式(3).

式中：a 為虛擬機的租用周期；ci為第i 類虛擬機單個租用周期的單價.

總費用Ctotal為每個任務節(jié)點的費用的連續(xù)累加和，其計算式見式(4).

由上，定義適應度函數(shù)fitness 為

式中：w1與w2為兩個實數(shù)，兩數(shù)相加之和為1；Tdeadline為用戶所提供的調(diào)度該批任務所要求的deadline 與任務批開始進行調(diào)度的時間差值，單位為min；Ttotaltime為任務調(diào)度總時間，單位為min；Max 代表取括號內(nèi)兩數(shù)中較大的.下文在交叉概率函數(shù)中用f 簡化表示.

2.1.4 遺傳算法的交叉變異

(1)由于編碼方式為每兩位數(shù)字代表一組信息，因此本文的交叉掩碼取值為隨機偶數(shù).交叉概率函數(shù)(P)的計算公式見式(6).

式中：k1、k2為常數(shù)；fmax為種群最大適應度值；fav為群體平均適應值；f ′為要交叉的兩個個體中較大個體的適應度值.當 f ′大于等于fav，應該讓交叉概率P較小，防止適應度值大的個體統(tǒng)治群體，陷入局部最優(yōu)解；反之，則應該讓交叉概率較大，以重組出新的個體，擴展搜索空間.

(2)變異操作：本文的變異操作采用的是基本位變異，選取一定百分比的個體隨機變異染色體編碼的偶數(shù)位，即代表使用某種虛擬機類型數(shù)量的表示位，變異方式是將該位數(shù)字隨機加減 1，本文選取3%.這樣做的好處是變異后的染色體適應度值變得更好的概率較高.

2.1.5 非關(guān)鍵路徑虛擬機使用數(shù)量的收縮

為了進一步優(yōu)化遺傳算法通過迭代次數(shù)所得出的最優(yōu)解，提出了一種非關(guān)鍵路徑虛擬機使用數(shù)量收縮的方法.在遺傳算法通過多次迭代得出一個最優(yōu)解后，在不改變關(guān)鍵路徑的情況下，將非關(guān)鍵路徑上使用的虛擬機數(shù)量按照單價由高到低不斷收縮，直到再次收縮將會改變該解的關(guān)鍵路徑便停止收縮并輸出最優(yōu)解.

2.2 不可隨意分割批處理科學工作流調(diào)度

與可隨意分割批處理科學工作流相比，不可隨意分割批處理科學工作流每個任務節(jié)點所包含的任務包由于內(nèi)部的數(shù)據(jù)關(guān)系，任務包不可隨意分割.也就是說在執(zhí)行調(diào)度時，每個任務包只能放在一個虛擬機上進行處理，所以在把任務調(diào)度到虛擬機上時，與可隨意分割批處理科學工作流有區(qū)別.調(diào)度算法具體區(qū)別如下：

(1)在本文中，為了更好地使最終解所得到的調(diào)度成本最低以及時間盡量滿足用戶所給出的截止期，采用任務平均分配至每個虛擬機上的分配方式.具體分配方式如圖2 所示.由于任務包不可隨意分割，調(diào)度到每臺虛擬機上的任務包數(shù)量可能不同，所以每個任務節(jié)點所需的調(diào)度總時間取決于該任務節(jié)點上所使用的耗時最長的虛擬機.

(2)由于不可隨意分割批處理科學工作流每個任務節(jié)點子任務的不可隨意分割性，所以在改進遺傳算法的變異過程中所采取的基本位變異就有了上限，即虛擬機使用數(shù)量不能超過子任務數(shù)量，所以當變異位數(shù)已經(jīng)達到上限，則默認虛擬機使用數(shù)量變異只能減1.

圖2 虛擬機分配方式Fig.2 Virtual machine allocation mode

3 仿真實驗

使用Matlab 驗證本文所提模型以及算法的有效性.所有進行實驗的批處理科學工作流均為隨機生成，虛擬機類型與單周期租賃費用為亞馬遜云上選取的實例，共選取了五類具有代表性的虛擬機類型.將Tdeadline設(shè)置為100 min.亞馬遜云真實實例具體數(shù)據(jù)見表1.

表1 亞馬遜云資源真實實例數(shù)據(jù)表Tab.1 Amazon cloud resources real instance data sheet

表中數(shù)據(jù)全部來源于亞馬遜云官方提供的云資源的真實數(shù)據(jù)，其中vCPU 代表虛擬機CPU，每個虛擬機都有內(nèi)存，單位為GiB，帶寬主要影響虛擬機之間的傳輸速度，單位為Mbps.

本文在Matlab 平臺上模擬實現(xiàn)了改進的遺傳算法的可隨意分割批處理科學工作流任務調(diào)度與不可隨意分割批處理科學工作流任務調(diào)度算法，同時還原了任務可隨意分割按比例劃分截止期經(jīng)典調(diào)度算法與任務不可隨意分割按比例劃分截止期經(jīng)典調(diào)度算法，并與之進行對比.用于實驗的批處理科學工作流是通過Cai 等[11]使用的批處理科學工作流生成器完全隨機生成的.按比例劃分截止期經(jīng)典調(diào)度算法在執(zhí)行虛擬機資源配置時主要是根據(jù)待執(zhí)行任務量大小，即任務節(jié)點內(nèi)任務執(zhí)行時間預測值與任務個數(shù)的乘積，然后按照所占總?cè)蝿樟康陌俜直冗M行分配截止期的長短，最終按照所分得的時間配置虛擬機使其滿足相應分得的截止期.4 種算法的調(diào)度成本如圖3所示.

圖3 調(diào)度成本對比圖Fig.3 Scheduling cost comparison chart

任務調(diào)度成本是在某一特定數(shù)目任務節(jié)點時生成的批處理科學工作流下，算法運行100 次所取的平均值.由于按比例劃分截止期經(jīng)典調(diào)度算法劃分截止期的方式簡單的按照任務規(guī)模按比例分配截止期，且配置虛擬機類型與數(shù)量只是簡單按照是否滿足截止期配置，因此耗費的成本就會相對較高.本文所提的改進后的遺傳算法的不可隨意分割批處理科學工作流任務調(diào)度算法，由于其搜索空間廣且能并重虛擬機升級與并行度，且在算法得出最優(yōu)解后進一步對非關(guān)鍵路徑上所使用的虛擬機數(shù)量進行收縮，進一步縮減成本，所以解的效果要好一些；而基于遺傳算法的可隨意分割任務調(diào)度算法，由于模型相對理想化，所以在使用虛擬機類型時算法會比較偏向選擇價格低但并行度高的方式處理任務.亞馬遜云資源的實際標價并不是線性增加的，因此可隨意分割BIGA 算法的調(diào)度成本會低于不可隨意分割BIGA.

為了證明算法的有效性，圖4 為改進遺傳算法的成本調(diào)優(yōu)圖，具體實驗數(shù)據(jù)為在任務節(jié)點數(shù)為5 的隨機10 個批處理科學工作流生成1 000 次初始解，其中每個批處理科學工作流生成100 次，并計算這些初始解的平均調(diào)度成本，然后進行算法迭代，觀察隨著算法迭代次數(shù)的不斷增加，解的平均調(diào)度成本的變化.從圖4 可以看出改進遺傳算法通過一定次數(shù)的迭代，與最初始解相比成本縮減了近90%.

圖4 成本調(diào)優(yōu)圖Fig.4 Cost tuning diagram

為了檢驗本文種群初始化算法的有效性，將經(jīng)過本文所提的初始化種群優(yōu)化方法的可隨意分割批處理科學工作流任務調(diào)度算法和不可隨意分割批處理科學工作流任務調(diào)度算法與其他部分不變初始化種群為隨機生成的兩組算法所得的最終解的調(diào)度成本進行對比，圖5 和圖6 為基于改進遺傳算法的可隨意分割批處理科學工作流任務調(diào)度與不可隨意分割批處理科學工作流任務調(diào)度算法進行1 000 次初始種群優(yōu)化與不進行初始種群優(yōu)化的效果對比圖.

由圖5 和圖6 可以看出：兩種算法經(jīng)過初始種群優(yōu)化后所得的最終解均要大幅優(yōu)于未經(jīng)初始種群優(yōu)化的算法，其原因主要是經(jīng)過初始種群優(yōu)化后所生成的初始種群不僅具有隨機性，同時與隨機生成的初始種群相比，大部分個體都相對更為優(yōu)秀，這就使得在這樣的種群中進行交叉變異更容易產(chǎn)生優(yōu)秀解，一定程度上避免了算法陷入局部最優(yōu)的可能性.

圖5 可隨意分割BIGA 初始種群優(yōu)化與未優(yōu)化最終成本對比Fig.5 Final cost comparison of optimized and unoptimized freely split BIGA initial population

圖6 不可隨意分割BIGA 初始種群優(yōu)化與未優(yōu)化最終成本對比Fig.6 Final cost comparison of optimized and unoptimized not freely split BIGA initial population

最后，針對本文算法的執(zhí)行效率問題，通過實驗對比了4 種算法的執(zhí)行效率，結(jié)果如圖7 所示.

圖7 執(zhí)行效率對比Fig.7 Comparison of performance efficiency

由圖7 可以看出：兩種任務不可隨意分割的任務調(diào)度算法的執(zhí)行效率要明顯高于另外兩種可隨意分割的任務調(diào)度算法，且兩種任務可隨意分割的任務調(diào)度算法隨著任務節(jié)點數(shù)的增加其執(zhí)行效率也會降低，而任務不可隨意分割的兩種任務調(diào)度算法則沒有顯著影響.其原因是在進行任務調(diào)度虛擬機資源配置計算時，由于任務不可隨意分割的兩種任務調(diào)度算法其任務組內(nèi)的子任務不可隨意分割，導致虛擬機配置數(shù)量上限受到子任務數(shù)影響，所以其解搜索空間相對較??；而任務可隨意分割的兩種任務調(diào)度算法則相反，其解空間隨任務節(jié)點數(shù)的增加指數(shù)增大，所以相應的耗時也就更大.另外，由于隨著任務節(jié)點數(shù)的增大，其搜索空間是指數(shù)增大，所以耗時也會越來越多.

4 結(jié) 語

通過以上理論和實驗分析，按比例劃分截止期經(jīng)典調(diào)度算法解的生成方式簡單，且資源分配方案隨機性太大，而所提的兩種任務調(diào)度算法優(yōu)化了初始解的生成，使得初始解不至于離全局最優(yōu)解太遠，加快了算法的收斂速度.同時，通過并重虛擬機升級與并行度調(diào)整兩種操作使最終解更趨近于全局最優(yōu)，因此在任務調(diào)度成本上要比前者少.下一步將重點研究數(shù)據(jù)密集型批處理工作流任務關(guān)聯(lián)度聚類與本文方法的結(jié)合，以縮減網(wǎng)絡傳輸耗時，從而更全面地解決批處理工作流的云調(diào)度問題.

致謝：本研究同時受到國家自然科學基金(11503051，61402325)、國家自然科學基金委員會-中國科學院天文聯(lián)合基金(U1531111，U1531115，U1531246，U1731125，U1731243)資助，一并致謝.