(石家莊鐵道大學(xué) 信息科學(xué)與技術(shù)學(xué)院，河北 石家莊 050043)

工作流通常是數(shù)據(jù)密集型和計算密集型應(yīng)用，例如歐洲核子研究組織(CERN)在大型強子對撞器上進行的Compact_Muon_Solenoid的實驗，產(chǎn)生了超過5PB數(shù)據(jù)需要進一步分析；美國航天局(NASA)設(shè)定的目標(biāo)為在一天內(nèi)處理24TB數(shù)據(jù)，同時面臨著對這批數(shù)據(jù)進行可視化和分析的一系列后續(xù)任務(wù)。這些工作流具有大量的數(shù)據(jù)和計算需求，需要一個高性能計算環(huán)境。云計算環(huán)境基礎(chǔ)設(shè)施為大規(guī)模科學(xué)工作流提供了一個合適的環(huán)境。云計算環(huán)境將計算資源作為服務(wù)可根據(jù)用戶的約束需求動態(tài)地提供，用戶約束條件下的資源調(diào)度問題成為關(guān)鍵。針對現(xiàn)有進化算法存在的不足，提出一種截止時間約束條件下的工作流調(diào)度自適應(yīng)遺傳進化方法，依據(jù)修正均值自適應(yīng)調(diào)整交叉概率、變異概率以及選擇概率，利用修正均值來改進適應(yīng)度，引入懲罰函數(shù)自適應(yīng)修正適應(yīng)度，可避免進化方法陷入局部最優(yōu)，防止早熟結(jié)果的產(chǎn)生。

1 相關(guān)知識

近年來，約束條件下的工作流調(diào)度在云計算環(huán)境中被廣泛應(yīng)用，相關(guān)調(diào)度方法已成為了研究者們的研究重點和熱點。除了傳統(tǒng)調(diào)度方法的不斷優(yōu)化和改進之外，一些進化算法也被采用來生成近似最優(yōu)的調(diào)度策略。目前，研究者們針對約束條件下的工作流調(diào)度問題的處理主要是將有約束問題轉(zhuǎn)換為無約束問題。黃冀卓等[1]針對約束優(yōu)化問題轉(zhuǎn)換為無約束的雙目標(biāo)優(yōu)化問題，利用進化算法從多點出發(fā)尋找最優(yōu)解；Rodriguez et al[2]針對科學(xué)工作的流約束優(yōu)化問題，轉(zhuǎn)換為最小化執(zhí)行花費的優(yōu)化問題。然而，現(xiàn)有調(diào)度方法無法實現(xiàn)根據(jù)用戶需求及時調(diào)整調(diào)度策略，因此并不適用約束條件下的工作流調(diào)度問題；同時在處理該問題時使用靜態(tài)相關(guān)概率，并通過使用靜態(tài)懲罰函數(shù)完成從有約束問題到無約束問題的轉(zhuǎn)換。約束條件下的工作流調(diào)度進化方法中主要涉及種群個體的適應(yīng)度、選擇概率、交叉概率與變異概率以及懲罰函數(shù)幾個關(guān)鍵概念。

1.1 適應(yīng)度

適應(yīng)度是評價個體優(yōu)劣的關(guān)鍵，其決定了整個種群的進化方向。個體的適應(yīng)度越優(yōu)，則該個體越優(yōu)秀。適應(yīng)度目標(biāo)函數(shù)綜合約束條件、工作流數(shù)據(jù)等信息對個體適應(yīng)度進行評價。

1.2 選擇概率

基因選擇操作的機制一般是從當(dāng)前種群中挑選出適應(yīng)度最優(yōu)的個體作為下一代的親代，從而改善下代種群中的平均適應(yīng)度。進化算法的收斂速度基本上是通過選擇算子在搜索過程中的選擇概率所決定的。選擇概率表示個體被選中的概率，概率數(shù)值越大，則個體被選中遺傳到后代的機會越多。

1.3 交叉概率與變異概率

交叉變異操作是進化算法的基因操作的關(guān)鍵，進化機制是通過交叉和變異的重組改變種群中基因，并生成新的種群個體，以便在解空間中創(chuàng)造出新的點，避免陷入解空間的局部最優(yōu)區(qū)域中搜索。交叉概率指個體發(fā)生交叉操作的概率，變異概率是指個體發(fā)生交叉操作的概率，概率數(shù)值越大，則個體越容易發(fā)生交叉操作和變異操作。

1.4 懲罰函數(shù)

根據(jù)約束條件特性構(gòu)造懲罰項，將懲罰項加入到目標(biāo)函數(shù)中，是有約束問題轉(zhuǎn)化為無約束問題的關(guān)鍵。進化算法中對任意違反約束條件的個體進行懲罰，使該個體適應(yīng)度降低；從而保證整體種群同時具有可行域和不可行域，并在進化過程中使個體朝著可行域邊界進化。

2 工作流建模

圖1 簡單工作流模型

將工作流建模為一個有向無環(huán)圖(Directed Acyclic Graph， DAG)。首先將工作流描述為WFG=〈T,E〉，其中T表示工作流中任務(wù)的集合，用T={t1，t2，t3，…，tm}表示；E表示工作流中有向邊的集合，使用eij表示任務(wù)〈ti,tj〉之間的有向邊，如果在任務(wù)〈ti，tj〉之間存在有向邊eij，那么在任務(wù)〈ti，tj〉之間存在一條數(shù)據(jù)依賴關(guān)系，即任務(wù)ti可以認(rèn)為是任務(wù)tj的父節(jié)點，而任務(wù)tj可以認(rèn)為是任務(wù)ti的子節(jié)點。換句話說，任務(wù)ti的輸出數(shù)據(jù)作為任務(wù)tj的輸入數(shù)據(jù)?；谶@樣的描述，一個子節(jié)點任務(wù)能夠執(zhí)行的前提是其所有父節(jié)點任務(wù)全部執(zhí)行完畢， 假設(shè)任務(wù)ti的父節(jié)點任務(wù)只有任務(wù)tj，不存在其它父節(jié)點任務(wù)依賴，任務(wù)tj必須等其父節(jié)點任務(wù)ti執(zhí)行完成之后才能開始執(zhí)行。不具有父節(jié)點任務(wù)的任務(wù)則稱為根任務(wù)，用troot表示；不具有子節(jié)點任務(wù)的任務(wù)稱為葉子任務(wù)，用tleaf表示。此外，每個工作流WFG均具有一個截止時間DLWFG，作為工作流WFG最長執(zhí)行時間的時間約束。圖1展示了一個簡單工作流模型，圖中每個節(jié)點表示一個任務(wù)ti，節(jié)點之間的箭頭表示數(shù)據(jù)依賴關(guān)系eij。

云計算通過虛擬化技術(shù)將云環(huán)境的實體資源以虛擬機的形式表示。IaaS云服務(wù)供應(yīng)商提供多種類型的虛擬機，可以表示為VMtype={VM1，VM2，…，VMn}，不同類型的虛擬機提供了不同的計算能力。這里，VMi表示虛擬機的類型，PVMi表示VMi類型虛擬機的計算能力，CVMi表示虛擬機執(zhí)行任務(wù)時單位時間的花費。參考Vockler et al[3]的工作流應(yīng)用程序，采用Amazon EC2的規(guī)格設(shè)定虛擬機類型，并且虛擬機具有足夠執(zhí)行工作流任務(wù)的內(nèi)存。

根據(jù)Ostermann et al[4]的工作，為每種類型的虛擬機設(shè)定其每秒所執(zhí)行的浮點運算次數(shù)(FLOPS)作為其處理能力，并且該處理能力是已知的。假設(shè)工作流中每個節(jié)點任務(wù)為執(zhí)行基本單位，不可進一步分隔，一個節(jié)點任務(wù)僅在一個給定虛擬機上執(zhí)行。由于性能存在波動，通過引入性能波動變量fluvmj來對性能波動情況進行建模。

在IaaS云計算服務(wù)中，廣泛采用了“pay-per-use”模式，其中單位時長τ由服務(wù)供應(yīng)商制定。用戶對虛擬機的使用按照所用單位時長來付費，若使用時長超過單位時長，則向上取整。例如，假定τ=30 min，如果用戶對虛擬機的使用時長為31 min，那么用戶將按照2個單位時長(2*τ)進行付費。

圖2 工作流的一個調(diào)度示例

云計算下的工作流調(diào)度存在多種不同的優(yōu)化目標(biāo)。本文著重處理如何在滿足截止時間約束的條件下，盡可能最小化執(zhí)行花費，并保證負載平衡。這里，將該多優(yōu)化目標(biāo)問題建模為調(diào)度策略模型S=(R，M，TET，TEC)。其中，R表示所租借的計算資源集合；M表示任務(wù)到資源的映射關(guān)系；TET表示工作流整體執(zhí)行完成時間；TEC表示工作流整體執(zhí)行花費。圖2展示了圖1的工作流調(diào)度示例。

優(yōu)化目標(biāo)可描述為式(1)，在TET滿足截止時間約束的前提下，使TEC盡可能小。

Minimize(TEC) Subjuct to:TET≤DLWFG

(1)

3 約束條件下工作流調(diào)度自適應(yīng)進化方法

將基本遺傳算法建模為一個7元組向量模型，表示為

GA=(Mparm,F,s,c,m,Pc,Pm)

(2)

式中，Mparm表示種群的相關(guān)參數(shù)；F表示個體適應(yīng)目標(biāo)評價函數(shù)，假設(shè)適應(yīng)度越小表示該個體越優(yōu)秀；s表示選擇操作算子；c表示交叉算子；m表示交叉操作算子；Pc表示交叉概率；Pm表示變異概率。

針對云計算環(huán)境下有約束工作流調(diào)度問題進一步建模分析，提出了一種基于適應(yīng)度修正均值與約束懲罰的工作流調(diào)度自適應(yīng)遺傳算法(Adaptive Gentic Algorithms based on Modified Mean Fitness and Con-strainted Penalty，MP-AGA)，算法描述如下：

輸入：工作流模型WFG，約束條件。

輸出：算法所得最優(yōu)調(diào)度策略。

(1)按照約束初始化初代種群個體，構(gòu)建初代種群；

(2)評價當(dāng)前種群中每個個體；

①計算當(dāng)前種群中每個個體的適應(yīng)度，以及修正適應(yīng)度；

②自適應(yīng)計算選擇、交叉、變異概率，懲罰函數(shù)，最終適應(yīng)度；

(3)重復(fù)迭代直到終止條件出現(xiàn)；

①選擇個體作為下代種群的親代；

②通過交叉操作得到新的子代；

③評價所得個體；

(4)結(jié)束迭代，得到最優(yōu)結(jié)果。

3.1 自適應(yīng)計算選擇概率

根據(jù)“自然選擇”中的“優(yōu)勝劣汰，適者生存”的法則，在種群中選擇優(yōu)秀的個體進行繁衍，使后代種群中個體擁有更多的優(yōu)秀基因。當(dāng)代種群中任何個體均有可能被選中成為下代種群的親代，每個個體均具有一個選擇概率，概率應(yīng)滿足個體適應(yīng)度值越低越容易被選中的原則，采用的個體選擇概率計算式為

(3)

式中，當(dāng)所生成的隨機數(shù)小于Ps(i)時，認(rèn)為該個體沒有被選中；當(dāng)大于Ps(i)時，認(rèn)為該個體被選中。

為了防止因為偶然因素導(dǎo)致優(yōu)秀的個體沒有被選中的情況出現(xiàn)，在從當(dāng)代種群選擇個體時，進行多次選擇，將選擇出來的個體組成規(guī)模為z的群體。

3.2 自適應(yīng)計算交叉概率與變異概率

在GA算法中，交叉概率Pc和變異概率Pm越大，后代種群多樣性越豐富。但是如果交叉概率、變異概率過大，容易造成優(yōu)質(zhì)基因由于交叉、變異操作而丟失，造成進化步長過大，無法成功收斂到最優(yōu)解；此外，如果交叉、變異操作的概率過小，導(dǎo)致整個種群進化速度過慢，同時進化步長過小，容易陷入局部最優(yōu)的狀況。

生物進化過程說明了Pc和Pm應(yīng)該根據(jù)種群情況自適應(yīng)調(diào)整，且依賴于進化狀態(tài)。Zhang et al[5]將GA算法中的進化狀態(tài)劃分為4個優(yōu)化狀態(tài)：Initial，undermatured，maturing以及maturned階段。Pc和Pm可根據(jù)進化過程中不同的狀態(tài)自適應(yīng)調(diào)整。根據(jù)上述規(guī)則以及受到Srinivas et al[6]工作的啟發(fā)，提出了一種基于適應(yīng)度修正均值的自適應(yīng)計算概率方法，如式(4)和式(5)。

(4)

(5)

式中，Pc(i)表示當(dāng)代種群中第i個個體的交叉概率；Pm(i)表示當(dāng)代種群中第i個個體的變異概率。當(dāng)?shù)趇個個體適應(yīng)度f′(i)小于等于當(dāng)前種群適應(yīng)度的修正均值fcavg時，認(rèn)為該個體處于進化過程中的maturing和 maturned階段，使用交叉變異參數(shù)k3和k4；當(dāng)?shù)趇個個體適應(yīng)度f′(i)大于等于當(dāng)前種群適應(yīng)度的修正均值fcavg時，認(rèn)為該個體處于進化過程中的Initial和undermatured階段，使用交叉變異參數(shù)k1和k2。為避免突變產(chǎn)生的極差個體對種群整體適應(yīng)度均值的影響，采用ω來修正均值fcavg，其計算過程如下

(6)

式中，Sp表示當(dāng)前種群的大??；fc(i)表示修正后的種群個體適應(yīng)度；ω表示需要修正個體所占種群的百分比，這里僅修正極差個體，通過多次實驗經(jīng)驗設(shè)定為15%。通過引入修正均值，削弱因交叉、變異所產(chǎn)生的極差個體所帶來的影響。

3.3 基于自適應(yīng)懲罰的適應(yīng)度計算

(7)

個體i違反約束變量vf(i)如式(8)所示，該變量用于記錄個體i違反用戶約束條件的程度。

(8)

使用每代種群中的適用度值中的最大最小值，對適用度標(biāo)準(zhǔn)化，如式(9)所示。

(9)

(10)

圖3 種群分布情況示意

通常情況下，懲罰函數(shù)同個體違反約束的程度成正比，當(dāng)個體違反約束程度越高時，應(yīng)受到越嚴(yán)厲的懲罰；當(dāng)個體違反約束程度越低時，應(yīng)受到較輕的懲罰。同時，考慮到種群中個體分布情況rf，圖3示意了種群的分布情況，其中a、d子圖分別表示完全滿足約束條件(rf= 1)和完全不滿足約束條件(rf= 0)的情況；b子圖表示滿足約束條件個體占大多數(shù)(rf> 0.5)的情況；c子圖表示不滿足約束條件個體占大多數(shù)(rf< 0.5)的情況。因此，可以構(gòu)建自適應(yīng)懲罰函數(shù)，如式(11)所示。

pf(i)=(1-rf)vf(i)+rf·Xf(i)rf≠0

(11)

因此，根據(jù)式(10)與式(11)，最終的適應(yīng)度計算函數(shù)如式(12)所示，由2部分構(gòu)成。

(12)

4 實驗結(jié)果與分析

圖4 科學(xué)工作流Montage

4.1 測試工作流

為評價文中方法在解決云環(huán)境下科學(xué)工作流調(diào)度問題的性能，使用WorkflowSim框架來模擬云環(huán)境，實驗采用Montage科學(xué)工作流，其被廣泛應(yīng)用于調(diào)度算法的性能度量方面。Montage工作流的結(jié)構(gòu)如圖4所示，其層次分明，節(jié)點表示任務(wù)，箭頭表示數(shù)據(jù)依賴關(guān)系。

4.2 虛擬機配置模擬

模擬了IaaS云計算環(huán)境，該環(huán)境提供了一個單獨的數(shù)據(jù)中心，5個類型的虛擬機。虛擬機參數(shù)根據(jù)Amazon EC2配置，具體參數(shù)見表1。參考Ostermann et al[4]的工作來設(shè)置虛擬機的處理能力。

表1 實驗中所使用的虛擬機類型及其收費標(biāo)準(zhǔn)

同時考慮到虛擬機性能的波動，參考Schad et al[8]的工作，設(shè)置虛擬機性能波動參數(shù)fluvmj為10%～12%間的隨機數(shù)。

4.3 參數(shù)設(shè)置

實驗所需要的各個參數(shù)值需要根據(jù)之前的測試和多次實驗結(jié)果進行設(shè)定。參考Wu et al[9]以及Srinivas et al[10]的工作，參數(shù)設(shè)置如下：設(shè)定種群迭代次數(shù)為100代；計算資源為5個，具有不同的計算資源類型；設(shè)定k1=1.0、k2=0.5、k3=1.0、k4=0.5用來計算自適應(yīng)的交叉概率與變異概率。 所有的實驗均執(zhí)行在以下硬件環(huán)境：CPU為Inter Core i5-4570S；RAM為8 GB。

4.4 實驗結(jié)果分析

圖5 不同調(diào)度算法滿足截止時間約束程度對比

為了評價算法，選用了一些解決約束條件下優(yōu)化問題的傳統(tǒng)調(diào)度算法及典型進化算法作為對比，例如隨機(Random)算法、異構(gòu)環(huán)境最早結(jié)束時間(HEFT)算法、傳統(tǒng)遺傳算法(GA)、Maria et al提出的基于傳統(tǒng)PSO算法的調(diào)度策略(以Maria PSO表示)，以及Liu et al[11]提出的基于協(xié)同GA算法的CGA2算法。為了確保實驗結(jié)果的可信性，實驗中對于不同算法均重復(fù)30次，分別計算出每個科學(xué)工作流在每次實驗中的計算時間和計算花費，最后將30次實驗結(jié)果值取平均。

首先，分析不同算法在截止時間約束滿足程度方面的表現(xiàn)，以百分比的柱狀圖形式展示，如圖5所示。

由圖5可見，在截止時間約束滿足程度的表現(xiàn)方面，不同的算法在4種不同截止時間約束下針對Montage科學(xué)工作流表現(xiàn)有所差異。實驗結(jié)果表明，隨機(Random)算法在不同截止時間約束下很難滿足用戶的約束；HEFT算法約束滿足率均為100%；就傳統(tǒng)GA以及Maria PSO算法而言，在較寬松的截止時間約束下，約束滿足率較為滿意，而在較為苛刻的截止時間約束下，約束滿足率則差強人意；CGA2雖然在一般截止時間約束下，約束滿足率為100%；但當(dāng)約束極其嚴(yán)格時，約束滿足率則低至10%左右。而提出的MP-AGA方法在不同截止時間約束下均令人滿意。在4種不同截止時間約束條件下進行對比實驗，將6種不同調(diào)度算法的計算執(zhí)行時間和執(zhí)行花費的實驗結(jié)果均值作為數(shù)據(jù)點繪制在圖6中。

在圖6中，虛線中表示截止時間約束，縱坐標(biāo)表示TET，橫坐標(biāo)表示TEC。從圖5中的不同符號的點的分布可以看出不同方法在不同截止時間約束下的執(zhí)行時間和執(zhí)行花費。隨機算法由于是隨機地將計算任務(wù)和計算資源進行分配，并未進行有目的的優(yōu)化，執(zhí)行時間和執(zhí)行花費不可控，隨機性較大；HEFT算法總能將完成時間控制在一個盡可能小的水平，但由于其存在貪心算法的性質(zhì)，在復(fù)雜的情況下不能找到最優(yōu)調(diào)度策略，其執(zhí)行花費也較大；就傳統(tǒng)GA以及Maria PSO算法而言，它們僅使用簡單靜態(tài)的懲罰函數(shù)，從而導(dǎo)致在進化過程中排斥任何違反約束的解決方案；傳統(tǒng)GA的執(zhí)行花費會隨著截止時間約束嚴(yán)格程度而逐步增加；Maria PSO算法的執(zhí)行花費則較為穩(wěn)定；CGA2雖然引入了自適應(yīng)懲罰函數(shù)，但其最終結(jié)果以后會獲得一個貪婪解，無法尋到最優(yōu)解，同時由于引入額外種群造成了額外的計算量，在較為寬松的截止時間約束下產(chǎn)生比傳統(tǒng)GA較高的執(zhí)行花費。MP-AGA方法在不同截止時間約束下最貼近截止時間，并且花費均具有較低執(zhí)行花費。

圖6 截止時間約束下不同調(diào)度算法的執(zhí)行時間和執(zhí)行花費對比

5 結(jié)論

提出了一種云計算環(huán)境下基于截止時間約束并最小化執(zhí)行花費的科學(xué)工作流任務(wù)調(diào)度MP-AGA方法，考慮了云計算環(huán)境的異構(gòu)性和性能波動，以及不同計算資源間的任務(wù)所需數(shù)據(jù)的傳輸時間。實驗選用典型的科學(xué)工作流Montage，選取Random、HEFT、GA、Maria PSO及CGA25種算法作為對比。實驗結(jié)果表明所提出的MP-AGA算法可以滿足截止時間約束，并且能夠在貼近用戶截止時間約束的執(zhí)行時間下花費更小的成本。同時，研究工作仍存在需進一步完善改進之處，如調(diào)度策略主要是針對單一科學(xué)工作流進行研究，在整個調(diào)度過程中存在資源閑置的情況，未能完全充分利用計算資源；適應(yīng)度計算函數(shù)中優(yōu)化目標(biāo)僅包含執(zhí)行時間和執(zhí)行花費兩項，過于單一，未能充分考慮用戶多種多樣的需求；所模擬的實驗環(huán)境為單數(shù)據(jù)中心環(huán)境，未考慮多數(shù)據(jù)中心的情況下的計算資源分配的問題；在資源調(diào)度過程中，未考慮計算所造成的能耗問題，不適當(dāng)?shù)恼{(diào)度策略可能會造成高能耗的情況。