熊聰聰，陳長(zhǎng)博，趙 青，林 穎

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

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

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

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

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

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

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

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

為了方便描述，對(duì)批處理科學(xué)工作流進(jìn)行如下建模：

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

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

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

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

圖1 標(biāo)準(zhǔn)批處理科學(xué)工作流DAG圖Fig.1 DAG diagram of standard batch processing science workflow

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

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

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

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

2.1.1 編碼方式

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

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

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

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

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

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

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

2.1.3 適應(yīng)度函數(shù)

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

第y 個(gè)任務(wù)節(jié)點(diǎn)使用j 個(gè)i 類虛擬機(jī)的執(zhí)行任務(wù)所需時(shí)間(ty)的計(jì)算公式見式(2).

式中：tyi為單個(gè)i 類虛擬機(jī)執(zhí)行第y 個(gè)任務(wù)節(jié)點(diǎn)所需的預(yù)估時(shí)間；tbi為虛擬機(jī)的啟動(dòng)以及執(zhí)行軟件的安裝時(shí)間.

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

第y 個(gè)任務(wù)節(jié)點(diǎn)使用j 個(gè)i 類虛擬機(jī)的執(zhí)行任務(wù)所需的總費(fèi)用(Cy)的計(jì)算公式見式(3).

式中：a 為虛擬機(jī)的租用周期；ci為第i 類虛擬機(jī)單個(gè)租用周期的單價(jià).

總費(fèi)用Ctotal為每個(gè)任務(wù)節(jié)點(diǎn)的費(fèi)用的連續(xù)累加和，其計(jì)算式見式(4).

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

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

2.1.4 遺傳算法的交叉變異

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

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

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

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

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

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

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

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

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

圖2 虛擬機(jī)分配方式Fig.2 Virtual machine allocation mode

3 仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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

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