截止時間約束云工作流調(diào)度代價優(yōu)化遺傳算法

余科軍，張建州

(1.成都師范學(xué)院 計算機科學(xué)學(xué)院，四川 成都 610000；2.四川大學(xué) 計算機學(xué)院，四川 成都 610065)

0 引 言

工作流調(diào)度廣泛應(yīng)用于各領(lǐng)域中大規(guī)模科學(xué)與工程問題的建模[1]，其常見定義方式為擁有多個節(jié)點和邊的有向無循環(huán)圖DAG形式，圖的節(jié)點即為任務(wù)，邊即為任務(wù)的依賴關(guān)系。由于工作流規(guī)模大，任務(wù)量多變，云計算的出現(xiàn)為其提供了一種更高效的運行環(huán)境。云計算以效用方式提供計算模式[2]，其服務(wù)類型包括IaaS、PaaS和SaaS，IaaS以虛擬機VMs形式提供硬件資源，PaaS為用戶提供開發(fā)及部署環(huán)境，SaaS則提供運行于云設(shè)施上Web應(yīng)用，顯然，IaaS云環(huán)境更加適用于科學(xué)工作流調(diào)度問題[3,4]。

工作流調(diào)度相關(guān)研究中，文獻[5]提出一種局部關(guān)鍵路徑調(diào)度算法IC-PCP，可在滿足截止時間約束下最小化執(zhí)行代價。算法優(yōu)先將處于局部關(guān)鍵路徑PCP的所有任務(wù)調(diào)度至費用最低的VM上，避免了PCP上的通信代價，但算法忽略了VMs的啟動和部署時間。文獻[6]中的RTC和RCT算法則是分別針對執(zhí)行時間優(yōu)先和執(zhí)行代價優(yōu)先的工作流調(diào)度算法，均屬于單目標(biāo)無約束最優(yōu)化，不符合云工作流的實際調(diào)度特征。文獻[7]提出一種約束條件下代價最優(yōu)化調(diào)度PSO算法，算法雖然考慮了云資源提供彈性與異構(gòu)特征，但仍未解決PSO存在的早熟問題。文獻[8]在混合云環(huán)境下提出混合整數(shù)非線性規(guī)化解決工作流調(diào)度問題，目標(biāo)是滿足期限約束并最小化執(zhí)行代價。類似文獻[8]，文獻[9]提出動態(tài)規(guī)化算法處理多約束工作流調(diào)度問題，但未考慮多類型VMs的提供環(huán)境。

本質(zhì)上，工作流調(diào)度是NP-完全問題，即：無法滿足工作流的時間依賴約束或無法為任務(wù)選擇正確的資源類型，這些均可導(dǎo)致過高的服務(wù)使用成本。針對這一問題，提出一種滿足截止時間約束的工作流調(diào)度代價最優(yōu)化遺傳算法CODC-GA，算法通過遺傳操作，以盡可能高的約束滿意度獲得調(diào)度代價最小化方案，并通過實際科學(xué)工作流測試算法性能。

1 系統(tǒng)模型

1.1 工作流模型

將工作流以有向無循環(huán)圖DAG表示為W=(T,E)，T=(t1,t2,…,tm) 為任務(wù)集合，E為邊集，ei,j為任務(wù)ti至tj間的有向邊，ti,tj∈T且ti≠tj， 即兩個任務(wù)間的數(shù)據(jù)依賴關(guān)系，任務(wù)ti稱為tj的父(前驅(qū))任務(wù)，任務(wù)tj稱為ti的子(后繼)任務(wù)，這種父子約束關(guān)系表明只有父任務(wù)ti完成后，子任務(wù)tj才可以開始執(zhí)行。通常，工作流DAG擁有單個入口任務(wù)tentry和出口任務(wù)texit，入口任務(wù)不存在父任務(wù)，出口任務(wù)不存在子任務(wù)。如圖1為擁有9個任務(wù)的工作流，邊上的權(quán)值表示任務(wù)間的數(shù)據(jù)傳輸量或傳輸時間，每個工作流擁有一個執(zhí)行截止時間約束TD，表示工作流完成的最晚期限。

圖1 工作流結(jié)構(gòu)

1.2 云資源模型

(1)

TT(eij)=Data(ti,out)/β

(2)

其中，Size(ti)為任務(wù)ti的大小，以浮點運行次數(shù)度量，PC(VMk)為VMk的處理能力，以每秒進行的浮點運行次數(shù)度量，TT(eij)為任務(wù)ti與tj之間數(shù)據(jù)傳輸量為Data(ti,out)和帶寬為β時的數(shù)據(jù)傳輸時間。假設(shè)同一云數(shù)據(jù)中心內(nèi)部的數(shù)據(jù)傳輸寬帶是相同的。

1.3 最優(yōu)化調(diào)度

將以上工作流調(diào)度問題定義為：尋找給定工作流W的可行調(diào)度S，使得總執(zhí)行時間TET不超過TD的同時，使總執(zhí)行代價TEC達到最小，即

(3)

式中：Ctype(vmk)為vmk的單位時間間隔的使用成本。

2 CODC-GA算法設(shè)計

本文設(shè)計了適用于解決云工作流調(diào)度的遺傳操作，包括：問題編碼、種群初始化、交叉與變異，并提出了滿足截止時間約束的代價優(yōu)化遺傳算法CODC-GA(cost optimization genetic algorithm under deadline constraint)。

2.1 符號定義

表1給出符號說明及定義。

定義1pred(ti)和succs(ti)。對于任務(wù)ti，其前驅(qū)任務(wù)集和后繼任務(wù)集分別為

pred(ti)={ti|tj∈T∧(tj,ti)∈E}

(4)

succs(ti)={ti|tj∈T∧(ti,tj)∈E}

(5)

定義2EST(ti)和EFT(ti)。任務(wù)的最早開始時間為當(dāng)所有前驅(qū)pred(tp)已經(jīng)執(zhí)行且pred(tp)與ti間的輸出數(shù)據(jù)已經(jīng)傳輸時，ti在最快VM上的開始執(zhí)行時間，最早完成時間為任務(wù)ti執(zhí)行完成的時間，分別為

(6)

EFT(ti)=EST(ti)+MET(ti)

(7)

定義3MET(ti)。任務(wù)ti的最小執(zhí)行時間定義為

(8)

定義4MET_W。工作流的最小執(zhí)行時間定義為

(9)

定義5Lev(ti)。任務(wù)ti在DAG中的拓撲分級定義為

(10)

表1 符號說明

定義6ST(ti)和FT(ti)。任務(wù)ti的開始時間和完成時間分別定義為

(11)

(12)

定義7Avail(VMk)。如果任務(wù)ti是VMk上最后分配的任務(wù)，則VMk的就緒時間定義為

(13)

定義8LSTVMk和LETVMk。VMk的租用開始時間即為VMk執(zhí)行任務(wù)的就緒時間，VMk的租用結(jié)束時間即為VMk資源提供停止時間。

2.2 問題編碼

為了表示工作流調(diào)度的染色體形式，引入3個數(shù)組：Task2Index、Task2VM和VM2Host，Task2Index為任務(wù)索引，即根據(jù)任務(wù)執(zhí)行順序為每個任務(wù)分配整數(shù)索引，Task2VM為任務(wù)-虛擬機映射，即任務(wù)被分配至目標(biāo)虛擬機VM，VM2Host為VM-主機部署，即選擇VM的部署目標(biāo)主機資源池。初始狀態(tài)下，算法根據(jù)工作流的依賴約束尋找可能的任務(wù)順序，然后分配索引(從1至任務(wù)最大數(shù)量)至每個任務(wù)。

一個調(diào)度則可由Task2Index、Task2VM和VM2Host這3個數(shù)組表示，圖1表示的工作流結(jié)構(gòu)對應(yīng)的一種調(diào)度可以圖2進行編碼，第一行為任務(wù)位置(Task2Index)，由任務(wù)序列中ti的索引l表示，第二行為對應(yīng)每個索引l的任務(wù)ti所映射的VM(Task2VM)，第三行為任務(wù)ti所映射的VM所部署的主機。如：索引5對應(yīng)的任務(wù)t3被映射至VM1，而VM1部署于資源3。

圖2 調(diào)度方案染色體編碼方案

2.3 種群初始化

種群初始化過程為：首先，產(chǎn)生n個有序任務(wù)列表List(Oi)={O1,O2,…,On}∈O，n表示CODC-GA的種群大小，每個List(Oi)均包括所有任務(wù)， (ti)={t1,t2,…,tm}∈T，m為任務(wù)總數(shù)。利用圖3的方法對所有任務(wù)進行排序。方法輸入為有序List(Oi)空集和任務(wù) (ti)={t1,t2,…,tm}∈T， 初始狀態(tài)下，選擇一個有序List(Oi)∈O空集，然后，選擇任務(wù)ti并將ti置入List(Oi)列表尾部，如果ti的所有前驅(qū)任務(wù)已被添加至List(Oi)或tp∈pred(ti)==?， 則從T中移除ti，更新T=T-{ti}； 否則，將ti的前驅(qū)任務(wù)添加至List(Oi)，并重復(fù)該過程直到所有任務(wù)ti被添加至List(Oi)為止。至此，List(Oi)∈O包含所有任務(wù)ti且滿足工作流任務(wù)間的依賴關(guān)系。如果此時仍存在List(Oi)空集，則重復(fù)該過程。該過程完成后，可形成n個有序列表List(Oi)，每個List(Oi)中包含滿足依賴關(guān)系的所有任務(wù) (ti)={t1,t2,…,tm}∈T。

圖3 種群初始化

同時，為List(Oi)中的每個任務(wù)分配VM時，將任務(wù)調(diào)度至成本最低的VM上，即產(chǎn)生CODC-GA的初始種群。

2.4 適應(yīng)度評估

算法產(chǎn)生的調(diào)度方案適應(yīng)度評估方法如圖4所示，具體步驟為：輸入為染色體(Task2Index,Task2VM,VM2Host)編碼、工作流任務(wù)總量m及VMs總數(shù)量k，然后，對包含VMs的VM_Pool初始化為空、exeTime矩陣、transferTime矩陣、Map、TET和TEC均初始化為0，利用式(1)計算任務(wù)在可用VMs上的exeTime[m][k]，利用式(2)計算任務(wù)ti與tj間的transferTime[m][m]，從Task2Index中選擇索引對應(yīng)的每個任務(wù)ti，將其調(diào)度目標(biāo)選擇為Task2VM的VMk上，并利用式(11)和式(12)分別計算任務(wù)的開始時間ST(ti)和完成時間FT(ti)。

圖4 適應(yīng)度評估

然后，以開始時間ST(ti)和完成時間FT(ti)將ti調(diào)度至VMk，更新包括ti的VMk上的映射Map。計算VMk的租用開始時間LSTVMk和租用結(jié)束時間LETVMk。如果該VM不在VM_Pool中，則需要重新VM_Pool；否則，無需更新LSTVMk，租用結(jié)束時間LETVMk直接等同于ti的完成時間FT(ti)。重復(fù)以上過程直到所有任務(wù)被調(diào)度。最后，通過式(3)計算TET和TEC。

2.5 遺傳算子

(1)交叉操作

算法通過已有的兩個父調(diào)度間的交叉操作產(chǎn)生新的子調(diào)度。首先，考慮兩個交叉概率pc為100%的父調(diào)度P1和P2，選擇[0,1]間的隨機值與交叉概率100%比較，如果隨機值小于或等于100%，則執(zhí)行交叉操作，否則，終止交叉。執(zhí)行交叉時，隨機選擇兩個整數(shù)i，j，1≤i≤j≤m，m為任務(wù)總量，表示父調(diào)度P1中的任務(wù)索引。然后，選擇父調(diào)度P1的索引l∈[i,j]間的所有任務(wù)，將這些任務(wù)放入子調(diào)度C1中，但其任務(wù)順序及相應(yīng)的Task2VM和VM2Host從父調(diào)度P2得到，因此，此時得到的子調(diào)度兩個索引間j-i+1個任務(wù)間依然服從父調(diào)度P2中的依賴約束，同時將其它剩余任務(wù)(索引l∈(1,…,i-1,j+1,…,m)) 按照在父調(diào)度P1中的位置直接拷貝至子調(diào)度C1中。同理，父調(diào)度P2的子調(diào)度C1根據(jù)以上同樣的方式得到。

以圖5為例：在父調(diào)度P1上隨機選擇兩個值i=3和j=6，即對應(yīng)于Task2Index中索引i=3和j=6間的任務(wù)為 (t4,t5,t3,t6)， 然后，從父調(diào)度P2中選擇任務(wù) (t4,t5,t3,t6) (P2中4個任務(wù)的執(zhí)行順序為 (t3,t4,t6,t5)， 對應(yīng)VM為 (1,4,3,1)， 對應(yīng)主機類型為 (2,2,2,1)) 置入子調(diào)度中，因此，P1的子調(diào)度中索引i=3和j=6間將包括任務(wù) (t4,t5,t3,t6)， 并更改對應(yīng)VM為 (1,4,3,1)， 對應(yīng)類型為 (2,2,2,1)。 同時，將在索引1、2、7、8上的剩余任務(wù)t1、t2、t7和t8拷貝至子任務(wù)C1的對應(yīng)位置上。父調(diào)度P2的子調(diào)度C2產(chǎn)生過程可同上得到。

圖5 交叉操作

(2)變異操作

算法通過每個任務(wù)的拓撲分級保持任務(wù)依賴的方式進行變異操作。首先，對于一個新調(diào)度，在[0,1]間選擇一個隨機值，并與變異概率pm比較，決定是否進行變異，將變異概率設(shè)置為小于或等于30%。如果隨機值小于或等于30%，則執(zhí)行變異，隨機選擇兩個整數(shù)i，j，1≤i≤j≤m，如果lev(Task2Index[i]=lev(Task2Index[j]， 則將Task2Index[i] 與Task2Index[j] 對應(yīng)的任務(wù)進行互換。同時，如果在Task2Index[i] 與Task2Index[j] 間存在索引q對應(yīng)的任務(wù)tl，使得lev(tl)

以圖6為例：隨機選擇兩個值i=4和j=6，lev(Task2Index[4]=lev(Task2Index[6]， 將兩個索引Task2Index[4]和Task2Index[6]對應(yīng)的任務(wù)t5和t6互換，進一步，由于Task2Index[4]和Task2Index[6]間存在索引5對應(yīng)任務(wù)t3，且lev(t3)

圖6 變異操作

CODC-GA算法在執(zhí)行過程中如果得到的新調(diào)度在滿足截止時間約束的同時擁有更小的執(zhí)行代價，將取代種群中原有的調(diào)度，并不斷迭代，直至產(chǎn)生最優(yōu)調(diào)度方案。

3 仿真實驗

3.1 實驗配置

為了評估CODC-GA算法性能，利用仿真工具包CloudSim[10]進行仿真測試，并引入4種科學(xué)工作流作為測試源，包括：Montage、LIGO、Epigenomics及CyberShake[11]，每種工作流包含不同的結(jié)構(gòu)和特征，結(jié)構(gòu)如圖7所示。Montage為天文學(xué)領(lǐng)域中的工作流形式，任務(wù)以I/O密集型為主，對CPU計算能力要求不高，LIGO為物理學(xué)領(lǐng)域引力波工作流形式，任務(wù)以計算密集型為主，且對內(nèi)存要求較多，Epigenomics為信息生物領(lǐng)域的工作流形式，任務(wù)以計算密集型為主，且對內(nèi)存要求較多，CyberShake為地震學(xué)領(lǐng)域的工作流形式，任務(wù)以數(shù)據(jù)密集型為主，且對計算能力和內(nèi)存存儲均有較高要求。同時，為了符合現(xiàn)實科學(xué)工作流的隨機化規(guī)模特點，筆者在每種工作流中設(shè)置了3種不同大小的任務(wù)規(guī)模，包括：small(50個任務(wù))、medium(100個任務(wù))及l(fā)arge(1000個任務(wù))。

圖7 4種工作流結(jié)構(gòu)

實驗配置包含5種不同計算能力的VMs，參考Amazon EC2[12]的VM配置，具體參數(shù)見表2。表2中，一個ECU等同于1.0 GHz～1.2 GHz的CPU處理能力，任務(wù)的處理時間可由該值計算得到，單個數(shù)據(jù)中心中VMs的性能變化服從均值12%和標(biāo)準(zhǔn)差10%的正態(tài)分布，數(shù)據(jù)傳輸時間變化服從均值9.5%和標(biāo)準(zhǔn)值5%的正態(tài)分布。

表2 VMs類型

為了評估算法性能，定義每種工作流的截止時間約束，首先將所有任務(wù)按順序調(diào)度至最快VM上，然后計算工作流最小執(zhí)行時間MET_W，該值為執(zhí)行跨度下限。為了設(shè)置工作流截止時間，考慮兩種截止時間約束：硬約束和軟約束，截止時間通過下式設(shè)置

D=MET_W×(1+γ)

(14)

式中：γ為約束因子，MET_W為工作流最小執(zhí)行時間，即式(9)，當(dāng)0≤γ<12時表示截止時間硬約束，當(dāng)12≤γ≤32時表示截止時間軟約束，實驗中γ值以步長0.4進行改變。

遺傳參數(shù)設(shè)置為：種群規(guī)模為400，最大迭代次數(shù)為500，交叉概率為100%，變異概率為30%，通過CODCGA算法的交叉、變異及適應(yīng)評估方法對初始種群進行優(yōu)化，不斷迭代，直到找到滿足約束的代價最小化調(diào)度可行解。

選擇IC-PCP[5]、RTC[6]、RCT[6]和PSO[7]算法作為性能比較的基準(zhǔn)算法。IC-PCP基于云資源按需提供與即付即用定價模式等特征，重點在工作流調(diào)度時考慮了VMs的異構(gòu)性、性能動態(tài)變化特征和任務(wù)間的數(shù)據(jù)傳輸時間等要素，但未考慮任務(wù)計算時間和VM的啟動時間影響。RTC和RCT是分別針對執(zhí)行時間優(yōu)先和執(zhí)行代價優(yōu)先提出的工作流調(diào)度最優(yōu)化算法，重點側(cè)重于健壯性和容錯問題。PSO通過將粒子表示工作流任務(wù)進行編碼，但沒有表示資源信息，且粒子在不同方向的移動可能導(dǎo)致個體最優(yōu)，無法得到全局最優(yōu)，另外，該算法在硬約束時，較難找到可行解。

3.2 實驗結(jié)果

(1)截止時間性能評估

表3比較了算法對截止時間滿意度的情況。在Montage工作流的硬約束中，CODC-GA擁有高于IC-PCP 93%的滿意度，對于LIGO和CyberShake工作流，CODC-GA優(yōu)于IC-PCP 88.5%，對于Epigenomics工作流，CODC-GA優(yōu)于IC-PCP 83.5%，顯然，對于硬約束，IC-PCP在每種工作流中均無法滿足截止時間約束，而CODC-GA比IC-PCP更優(yōu)。同時，3種工作流中，無論硬約束還是軟約束，CODC-GA均擁有比RTC、RCT和PSO更高的約束滿意度。

表3 截止時間滿意度/%

另外，可以看出，IC-PCP在軟約束下性能是有所提高的，但綜合看來，IC-PCP在兩類約束下性能均較差，主要是由于該算法忽略了云的動態(tài)特征和VMs性能的動態(tài)變化，此外，該算法也沒有考慮延時問題，這對工作流的執(zhí)行跨度擁有較大影響。CODC-GA同時考慮了以上因素，能夠估算單個任務(wù)的開始時間和完成時間，確保任務(wù)在截止時間內(nèi)完成。RCT和RTC基于資源選擇策略，一定程度上忽略了VMs的性能變化。PSO與CODC-GA均屬于智能算法，但PSO的調(diào)度方案編碼方式缺乏資源信息，可能導(dǎo)致因VM性能的不同而無法滿足截止時間約束的情況。

(2)執(zhí)行時間和執(zhí)行代價性能評估

圖8和圖9比較了算法的執(zhí)行時間和執(zhí)行代價情況，其中，橫坐標(biāo)的含義為：若小于或等于1.2，表示硬約束，否則表示軟約束。

圖8 執(zhí)行時間

圖9 執(zhí)行代價

可以看出，IC-PCP在每種工作流中均擁有最長的執(zhí)行時間，而執(zhí)行代價也最小，由于該算法無法滿足工作流的截止時間約束，因此，即使代價最小也無法完成最優(yōu)化調(diào)度目標(biāo)。其它算法中，CODC-GA在Montage工作流中擁有比RCT低28%的執(zhí)行時間，比PSO低11%，比RTC低22%。在LIGO工作流中，CODC-GA的執(zhí)行時間比RCT低22%，比PSO低43%，比RTC低43%。在CyberShake工作流中，CODC-GA的執(zhí)行時間比RCT低27%，比PSO低17%，比RTC低6%。在Epigenomics工作流中，CODC-GA的執(zhí)行時間比RCT低38%，比PSO低20%，比RTC低47%。同樣地，CODC-GA在執(zhí)行代價方面也均優(yōu)于其它算法。

綜合執(zhí)行代價、執(zhí)行時間及截止時間約束滿意度等結(jié)果來看，CODC-GA可以在降低執(zhí)行代價的同時得到最高的約束滿意度，在硬約束中，CODC-GA在4種工作流形式中均擁有最高的約束滿意度并更低的執(zhí)行代價。截止時間約束相對寬松后，CODC-GA可以同時降低執(zhí)行時間和執(zhí)行代價。

4 結(jié)束語

云計算可以提供高性能計算資源解決大規(guī)模科學(xué)工作流調(diào)度問題。為了解決滿足工作流截止時間約束同時的執(zhí)行代價最優(yōu)化問題，提出了一種工作流調(diào)度遺傳算法，算法重點考慮了云資源異構(gòu)、VMs性能動態(tài)可變等特征，設(shè)計了全新的調(diào)度編碼方案、種群初始化以及遺傳交叉和變異操作，以得到最優(yōu)的工作流調(diào)度方案。現(xiàn)實工作流的測試結(jié)果表明，比較同類算法，算法不僅擁有最高的截止時間滿意度，而且執(zhí)行時間更短，執(zhí)行代價更低。