滿足帕累托最優(yōu)的多目標(biāo)云工作流調(diào)度算法

何留杰 李 波

1(黃河科技學(xué)院現(xiàn)代教育技術(shù)中心 河南 鄭州 450063)2(鄭州大學(xué)信息工程學(xué)院 河南 鄭州 450063)

0 引 言

大多數(shù)科學(xué)應(yīng)用，如生物信息學(xué)、化學(xué)和天文學(xué)領(lǐng)域等，均包含有大量優(yōu)先順序約束的任務(wù)集，其關(guān)系通常建立為有向無循環(huán)圖DAG任務(wù)模型。這些科學(xué)工作流涉及不同規(guī)模的復(fù)雜數(shù)據(jù)計(jì)算，并需要長周期的計(jì)算仿真，這要求高性能的計(jì)算能力和大規(guī)模基礎(chǔ)設(shè)施的可用性，而云計(jì)算則為其提供了不同QoS等級的服務(wù)支撐環(huán)境[1]。

云計(jì)算可以通過即付即用的方式向用戶提供按需、靈活和可擴(kuò)展的服務(wù)，其服務(wù)形式包括三種：基礎(chǔ)設(shè)施即服務(wù)IaaS、平臺即服務(wù)PaaS和軟件即服務(wù)SaaS。而云環(huán)境中的工作流DAG任務(wù)調(diào)度問題需要考慮的因素更多更復(fù)雜[2]：1) 用戶多樣的QoS需求，如：服務(wù)響應(yīng)時間、服務(wù)代價等；2) 云服務(wù)具有異質(zhì)、動態(tài)和彈性特征；3) 聯(lián)合云服務(wù)執(zhí)行工作流任務(wù)的方式多樣；4) 數(shù)據(jù)傳輸量更大。然而，工作流調(diào)度問題本質(zhì)上是聯(lián)合優(yōu)化問題，無法通過簡單啟發(fā)式算法或規(guī)則找到全局最優(yōu)解，是NP-完全問題，且與求解問題規(guī)模緊密相關(guān)。

目前的多數(shù)工作集中于兩個QoS參數(shù)優(yōu)化[3-4]：截止時間Deadline和預(yù)算Budget。本文將擴(kuò)展至多QoS需求，將QoS指標(biāo)定性為最小化用戶應(yīng)用的執(zhí)行代價和執(zhí)行跨度makespan，使工作流調(diào)度在確保用戶QoS偏好的同時，通過降低能耗以最大化云提供者的收益。基于此考慮，設(shè)計(jì)一種基于DVFS技術(shù)的多目標(biāo)離散PSO算法MODPSO，并以Pareto最優(yōu)的方式實(shí)現(xiàn)上述系統(tǒng)性能和系統(tǒng)能耗的同步優(yōu)化。

1 相關(guān)研究

異構(gòu)分布式系統(tǒng)中的工作流調(diào)度本質(zhì)上是個NP-完全問題，先前的工作中有很多啟發(fā)式或元啟發(fā)式調(diào)度算法對該問題進(jìn)行求解，最經(jīng)典的為異質(zhì)最早完成時間算法HEFT[5]。HEFT作為靜態(tài)算法可以最小化工作流執(zhí)行跨度makespan，且其結(jié)果服從任務(wù)間的依賴約束，較適用于傳統(tǒng)的分布式計(jì)算機(jī)環(huán)境。

另外一些工作則主要集中于最小化執(zhí)行時間，未考慮用戶的預(yù)算約束。然而，由于云計(jì)算的市場化特征，用戶必須對云資源使用進(jìn)行付費(fèi)，一些工作[6-7]則考慮了用戶預(yù)算和截止時間約束。文獻(xiàn)[6]提出一種基于預(yù)算約束的異構(gòu)最快完成時間算法BHEFT，該算法是經(jīng)典工作流調(diào)度算法HEFT的擴(kuò)展，考慮了任務(wù)調(diào)度時的最優(yōu)預(yù)算約束問題。文獻(xiàn)[7]提出一種異構(gòu)預(yù)算約束調(diào)度算法HBCS，通過定義代價因子調(diào)整可用預(yù)算與最低廉價格可能性的比例，實(shí)現(xiàn)調(diào)度優(yōu)化。文獻(xiàn)[8]提出的MOSC/D算法則是以工作流完工時間和費(fèi)用作為優(yōu)化目標(biāo)，通過目標(biāo)分解得到單一目標(biāo)的近似最優(yōu)解。

除了makespan和執(zhí)行代價，能耗已經(jīng)成為云計(jì)算系統(tǒng)面臨的嚴(yán)峻問題[9]。云提供者不僅需要保證滿足用戶的QoS需求[10]，而且需要確保服務(wù)提供行為的收益保障，而這與資源的高能耗是相互影響的。能效本身與其他QoS需求(時間或代價)是相互沖突的目標(biāo)，考慮能耗將進(jìn)一步加大云工作流調(diào)度問題的復(fù)雜性。相關(guān)研究中，文獻(xiàn)[11]雖然考慮了能耗，但在調(diào)度時又忽略了代價問題。而文獻(xiàn)[12]提出的加強(qiáng)HEFT算法EHEFT則是實(shí)現(xiàn)了makespan與能耗的雙目標(biāo)最優(yōu)化。

綜合考慮目前的研究，多數(shù)集中于優(yōu)化單一或兩個目標(biāo)，且沒有考慮不同目標(biāo)間的相互影響，即執(zhí)行時間、執(zhí)行代價和能耗間的影響。針對該問題，筆者設(shè)計(jì)了一種多目標(biāo)調(diào)度算法MODPSO，并基于Pareto最優(yōu)中非支配解的概念設(shè)計(jì)均衡度更好的多目標(biāo)優(yōu)化調(diào)度方案。

2 問題描述

本文的目標(biāo)是將工作流任務(wù)分配至云資源，實(shí)現(xiàn)用戶QoS指標(biāo)與云提供者收益的最優(yōu)化(通過節(jié)省資源能耗)。本節(jié)將首先描述云計(jì)算模型，然后描述工作流調(diào)度與所處理的目標(biāo)QoS參數(shù)模型，并將工作流調(diào)度問題形式化為多目標(biāo)最優(yōu)化問題。

2.1 云計(jì)算模型

云計(jì)算環(huán)境為若干異質(zhì)物理主機(jī)組成的數(shù)據(jù)中心，數(shù)據(jù)中心以即付即用的模式可向用戶提供多種類型的服務(wù)。假設(shè)云系統(tǒng)由完全連通的異質(zhì)處理器資源集合P組成，P={p1,p2,…,pm}，處理器擁有可變的處理能力和不同的處理價格，參數(shù)配置如表1所示。每個處理器pj∈P均具有DVFS能力，即：可運(yùn)行于不同的電壓縮放等級VSLs(電壓按比例調(diào)節(jié)，即擁有時鐘頻率調(diào)節(jié)能力)。對于每個處理器pj∈P，v個VSLs組成的集合Vj均勻分布于三種不同的VSLs集合中，具體參數(shù)表1所示。

表1 資源相關(guān)參數(shù)

每個處理器資源pj∈P擁有一個鏈路集合Lpj={lj,p1,lj,p2,…,lj,pk}，1≤k≤m，其中，lj,i∈R+表示處理器pj與pi間鏈路的可用帶寬(單位：Mbps)，且令lj,j=1。假設(shè)在同一處理器上執(zhí)行的任務(wù)的通信代價忽略不計(jì)。表1給出了三種處理器資源的DVFS等級、相對速度，三種資源類型的執(zhí)行代價EC分別為1.14、0.57和0.76。

2.2 工作流DAG任務(wù)模型

云工作流應(yīng)用建模為有向無循環(huán)圖DAG，表示為G(V,E)。圖的節(jié)點(diǎn)集V={T1,T2,…,Tn}表示工作流應(yīng)用的任務(wù)集，圖的有向邊集合表示任務(wù)間的順序依賴或數(shù)據(jù)依賴關(guān)系，有向邊表示為Sizeij=(Ti,Tj)∈E，其中，Ti為Tj的父任務(wù)，Tj為Ti的子任務(wù)，Sizeij為Ti輸出和Tj接收的數(shù)據(jù)。工作流中，只有所有父任務(wù)完成，并且接收所有父任務(wù)發(fā)送的數(shù)據(jù)后才可以開始執(zhí)行其子任務(wù)。對于給定的工作流DAG中，不存在父任務(wù)的任務(wù)稱為入口任務(wù)Tentry，不存在子任務(wù)的任務(wù)稱為出口任務(wù)Texit。

假設(shè)每個任務(wù)Ti∈V擁有一個與其相連的基本執(zhí)行時間，對于每個主機(jī)是一個獨(dú)立值。令ETij表示任務(wù)Ti在計(jì)算資源pj上以最大速度和電壓(對應(yīng)表1中的等級1)運(yùn)行時得到的基本執(zhí)行時間，則任務(wù)Ti的平均執(zhí)行時間可定義為：

(1)

而利用相對執(zhí)行速度后，任務(wù)Ti在計(jì)算資源pj上的實(shí)際執(zhí)行時間為定義為：

(2)

假設(shè)工作流DAG的每條邊(Ti,Tj)∈E擁有一個權(quán)值DTTij，表示Ti與Tj間的數(shù)據(jù)傳輸時間，該時間通過執(zhí)行任務(wù)的資源(px與py)間帶寬BWx,y計(jì)算得到：

(3)

傳輸時間僅在任務(wù)處于不同處理器資源上執(zhí)行時才予以考慮，即：若任務(wù)在同一處理器上執(zhí)行，其通信時間設(shè)置為0。而且，執(zhí)行代價(EC)和傳輸代價(TC)分別與執(zhí)行時間和傳輸時間成反比。

令pred(Ti)表示任務(wù)Ti的所有前驅(qū)(父)任務(wù)集，succ(Ti) 表示任務(wù)Ti的所有后繼(子)任務(wù)集，EST(Ti,pj)為任務(wù)Ti在處理器pj上的最早開始時間，EFT(Ti,pj)為任務(wù)Ti在處理器pj上的最早完成時間，EST(Ti)和EFT(Ti)分別表示Ti在任意處理器上的最早開始與完成時間。EAT(Ti,pj)表示當(dāng)pj可以開始執(zhí)行Ti的最早可用時間，則：

(4)

EFT(Ti,pj)=ETij+EST(Ti,pj)

(5)

令A(yù)ST(Ti,pj)和AFT(Ti,pj)分別表示任務(wù)Ti在處理器pj上的實(shí)際開始時間和實(shí)際完成時間。如果調(diào)度于同一處理器上的另一任務(wù)Tk的實(shí)際完成時間晚于其EST(Tk,pj)，則AST(Ti,pj)和AFT(Ti,pj)是不同于其最早開始時間EST(Ti,pj)和EFT(Ti,pj)的。

為了決定工作流任務(wù)的調(diào)度次序，本文通過任務(wù)在DAG中所處的位置層次賦予任務(wù)優(yōu)先級，任務(wù)優(yōu)先級的定義方式有以下三種：

1) 基于向上分級的任務(wù)優(yōu)先級，定義為：

(6)

式中：AETi表示任務(wù)Ti的平均執(zhí)行時間，ADTTij表示Ti的平均數(shù)據(jù)通信(傳輸)時間。任務(wù)Ti的向上分級表示從任務(wù)Ti至Texit間的最長路徑的長度。從定義可以看出，任務(wù)的向上分級需要從出口任務(wù)開始計(jì)算，然后遞歸計(jì)算至工作流DAG的入口任務(wù)。

2) 基于向下分級的任務(wù)優(yōu)先級，定義為：

(7)

任務(wù)Ti的向下分級表示從任務(wù)Texit至任務(wù)Ti間的最長路徑的長度，同時，任務(wù)的向下分級需要從入口任務(wù)開始計(jì)算，然后遞歸計(jì)算至工作流DAG的出口任務(wù)。

3) 基于向上與向下分級之和的任務(wù)優(yōu)先級，定義為：

Psum(Ti)=Pup(Ti)+Pdown(Ti)

(8)

該分級可以綜合考慮任務(wù)在工作流DAG中與入口任務(wù)和出口任務(wù)間的距離，優(yōu)于單純僅考慮向上或向下分級的任務(wù)優(yōu)先級定義方法。實(shí)驗(yàn)中以該方式定義任務(wù)優(yōu)先級。

圖1描述了一種擁有10個任務(wù)的工作流應(yīng)用模型，表2給出了細(xì)節(jié)描述，表中給出了每個任務(wù)在每種處理器資源上的執(zhí)行時間和任務(wù)的平均執(zhí)行時間(表中前五列)，還給出了三種方式定義的任務(wù)優(yōu)先級。

圖1 DAG任務(wù)實(shí)例

任務(wù)p1p2p3AETiPup(Ti)Pdown(Ti)Psum(Ti)T114169131080108T213191816.677731108T311131914.338025105T41381712.678022102T512131011.67692493T61316912.6763.332790.33T70715111142.6662.33105T8511141035.6666.66102.33T98122016.6744.3363.66108T102171614.6714.6693.33108

2.3 QoS參數(shù)模型

1) 能量模型:使用CMOS能量模型[13]，系統(tǒng)能耗主要由動態(tài)功耗部分組成，處理器功耗表示為：

ddynamic=ACefv2f

(9)

式中：A表示每個時鐘周期內(nèi)的開關(guān)次數(shù)，Cef表示有效電荷，v表示供電電壓，f表示運(yùn)行頻率。式(9)表明供電電壓占據(jù)功耗的主要部分，且是主要影響因素，因此，降低電壓對降低功耗具有更大影響。

本文將工作流的執(zhí)行能耗定義為：

(10)

(11)

式中：IDELj表示主機(jī)pj的空閑時槽，vminj和fminj分別表示pj的最低電壓和最小頻率，Ljk表示idlejk的空閑時間量。因此，云系統(tǒng)完成工作流任務(wù)集的總能耗可表示為：

Etotal=Eexe+Eidle

(12)

2) 時間模型：完成時間Ttotal即為用戶提交工作流直至得到結(jié)果間的執(zhí)行跨度makespan，可定義為出口任務(wù)的實(shí)際完成時間，表示為式(13)。該時間包括工作流執(zhí)行時間和網(wǎng)絡(luò)傳輸時間。執(zhí)行時間取決于負(fù)載與系統(tǒng)性能，而網(wǎng)絡(luò)傳輸時間則取決于網(wǎng)絡(luò)延遲和輸入數(shù)據(jù)量大小。

Ttotal=maxAFT(Texit)

(13)

3) 代價模型：由于云資源的市場化特征，服務(wù)使用需要付費(fèi)。工作流執(zhí)行代價Ctotal包括任務(wù)處理代價Cexe和數(shù)據(jù)傳輸代價Cdt，表示為：

Ctotal=Cexe+Cdt

(14)

(15)

數(shù)據(jù)傳輸代價Cdt可表示為：

(16)

式中：Sizeij表示Ti至Tj的輸出數(shù)據(jù)大小，TCij表示Ti所映射的處理器與Tj所映射的處理器間的通信代價。僅當(dāng)兩個任務(wù)擁有數(shù)據(jù)依賴時(Sizeij>0)才將通信代價計(jì)入總代價中。

4) 調(diào)度模型：給定以下調(diào)度場境：(1) 云提供者提供由m個異質(zhì)處理器資源組成的資源集P；(2) 用戶擁有由n個任務(wù)集合T組成的工作流應(yīng)用提交至處理器資源上執(zhí)行。那么，工作流DAG任務(wù)的調(diào)度問題即是構(gòu)造任務(wù)與處理器資源間的調(diào)度方案S，在不違背任務(wù)的執(zhí)行順序約束的情況下，實(shí)現(xiàn)相互沖突的多目標(biāo)同步最優(yōu)化，具體包括：執(zhí)行跨度makespan、執(zhí)行代價cost和執(zhí)行能耗energy。因此，本文的多目標(biāo)工作流調(diào)度最優(yōu)化問題可形式化為：

(17)

3 算法設(shè)計(jì)

3.1 多目標(biāo)最優(yōu)化問題

擁有m個決策變量和n個目標(biāo)的多目標(biāo)最優(yōu)化問題MOOP[14]可定義為：

min(y=f(x)=[f1(x),f2(x),…,fn(x)])

(18)

式中：x=(x1,x2,…,xm)∈X表示一個m維決策向量，X表示搜索空間，y=(y1,y2,…,yn)∈Y表示目標(biāo)向量，Y表示目標(biāo)空間。

常規(guī)MOOP中，不存在相對所有單一目標(biāo)的最優(yōu)解。如本文的優(yōu)化目標(biāo)(最小化執(zhí)行跨度makespan、最小化執(zhí)行代和最小化執(zhí)行能耗)本身是三個相互沖突的目標(biāo)，包括執(zhí)行跨度與執(zhí)行代價間的沖突，執(zhí)行跨度與執(zhí)行能耗間的沖突。針對這一問題，最終的調(diào)度期望解應(yīng)考慮為在三個目標(biāo)上為最優(yōu)的潛在解集合，該集合即為Pareto最優(yōu)集。以下定義與MOOP求解過程中相關(guān)的Pareto概念：

1) Pareto支配。對于兩個決策向量x1和x2，支配<定義為：

x1

(19)

決策向量x1支配x2，當(dāng)且僅當(dāng)：x1在所有目標(biāo)上等同于x2，且至少在一個目標(biāo)上x1嚴(yán)格優(yōu)于x2。

2) Pareto最優(yōu)。決策向量x1為Pareto最優(yōu)，當(dāng)且僅當(dāng)：

no?x2∈X:x2

(20)

3) Pareto最優(yōu)集。Pareto最優(yōu)集Ps為所有Pareto最優(yōu)決策向量的集合：

PS={x1∈X|no?x2∈X:x2

(21)

4) Pareto最優(yōu)邊界。Pareto最優(yōu)邊界PF為目標(biāo)空間中Pareto最優(yōu)集合的邊界：

PF={f(x)=(f1(x),f2(x),…,fn(n)|x∈Ps}

(22)

如果x1不被集合中任意決策向量支配，則x1表示給定集合的非支配解。

Pareto最優(yōu)決策向量在不使得任一目標(biāo)變得更差的情況下是無法得到加強(qiáng)的。當(dāng)決策向量在整個搜索空間中均不被支配時，該決策向量即為Pareto最優(yōu)。

3.2 粒子群最優(yōu)化

3.2.1標(biāo)準(zhǔn)PSO

PSO是一種受動物群體社會活動啟發(fā)的基于種群的隨機(jī)優(yōu)化方法[15]，屬于進(jìn)化計(jì)算的一類，由于其簡單性和社會行為優(yōu)化特征而受到廣泛使用。PSO中的一個粒子類似于在D維搜索空間中移動的魚或鳥，所有粒子擁有與其性能相關(guān)的適應(yīng)度，評估粒子的速度。在任意時間粒子位置同時受最佳位置pBest和問題空間中的最佳粒子位置gBest所影響，因此，在搜索過程中，粒子趨向于朝著更優(yōu)的搜索區(qū)域移動。搜索空間中的粒子狀態(tài)由兩個要素決定：速度和位置，在每一代中更新方式為：

(23)

(24)

步驟1隨機(jī)初始化粒子在搜索空間中的位置和速度；

步驟2評估所有粒子的目標(biāo)值，設(shè)置每個粒子的pBest為當(dāng)前位置，設(shè)置gBest為初始最佳粒子的位置；

步驟3根據(jù)式(21)和式(22)更新粒子速度和位置；

步驟4根據(jù)設(shè)置的最優(yōu)適應(yīng)度函數(shù)評估解空間中每個粒子對應(yīng)位置的適應(yīng)度值；

步驟5針對每個粒子，比較其當(dāng)前目標(biāo)值與pBest的大小，如果當(dāng)前值更優(yōu)，則以當(dāng)前位置和目標(biāo)值更新pBest；

步驟6決定當(dāng)前整個種群中帶有最優(yōu)目標(biāo)值的最佳粒子，如果目標(biāo)值優(yōu)于gBest，則以當(dāng)前最佳粒子更新gBest；

步驟7如果滿足終止條件，則輸出gBest及其當(dāng)前目標(biāo)值，否則，返回步驟2。

傳統(tǒng)PSO適宜于求解連續(xù)最優(yōu)化問題，然而，本文討論的工作流調(diào)度問題的決策變量是離散型變量，故本質(zhì)上為離散多目標(biāo)最優(yōu)化問題，即組合優(yōu)化問題。為了解決這一問題，本文設(shè)計(jì)了一種結(jié)合DVFS的離散PSO算法MODPSO對該問題進(jìn)行了求解。算法的主要工作包括：(1) 基于工作流調(diào)度的離散決策變量特征重新定義了PSO的粒子位置和速度；(2) 通過改進(jìn)PSO算法使其可以產(chǎn)生一個滿足不同優(yōu)化目標(biāo)要求的非支配解集合，而不僅僅考慮單一目標(biāo)優(yōu)化。

3.2.2多目標(biāo)優(yōu)化PSO

工作流調(diào)度可定義為三元組集合S=[](i∈[1,n],j∈[1,m],k∈[1,L(j)])，其中，n表示工作流待調(diào)度的任務(wù)數(shù)量，m表示云環(huán)境中可用的處理器資源數(shù)量，L(j)表示處理器j的VSLs數(shù)量。同時，對MODPSO算法求解工作流調(diào)度的變量和規(guī)則作如下描述：

一個粒子的位置代表工作流調(diào)度的一個可行解，由三元組的集合組成。每個三元組的含義為：任務(wù)Ti被調(diào)度至電壓等級為Lk的處理器Pj上執(zhí)行，同時表明粒子位置滿足任務(wù)間的順序約束。

種群中被選粒子的新位置的產(chǎn)生過程服從以下規(guī)則：

(25)

(26)

運(yùn)算符定義如下：

(1) 減運(yùn)算符Θ。兩個粒子的位置x1和x2之差定義為一個三元組集合，其內(nèi)的每個三元組中，x1相對應(yīng)于的每個元素是否與x2相同。如果不同，三元組得到最低VSL值的位置上的(service和VSL)。對于擁有相同內(nèi)容的x1和x2，其對應(yīng)的VSLs將被減小。(VSL的縮放會影響能耗、makespan和代價)

(2) 乘運(yùn)算符?。常量值與速度之乘積定義為一個三元組集合，其中，門限α∈[0,1]，每個三元組產(chǎn)生一個隨機(jī)數(shù)r，比較r和α，當(dāng)r≥α?xí)r，減小三元組中的VSL，否則，增加VSL。該運(yùn)算符可以增強(qiáng)算法的搜索能力。

(3) 加運(yùn)算符⊕。兩個位置相加的結(jié)果定義為占優(yōu)位置。

具體步驟如算法1所示。

算法1MODPSO算法

1. fori=1 toSnum

2. forj=1 tom

3. randomly initializeVSL(j)

//初始化j的電壓等級

4. initializeS[i] with HEFT

//以HEFT算法對種群S進(jìn)行初始化

5. initizlize the velocityVof each particle

//初始化粒子速度

6.V[i]=0(S[i])

7. initialize the Personal Best (pBest) of each particle

//初始化粒子pBest

8.pBest[i]=S[i]

9. evaluate objectives of each particle

//評估粒子目標(biāo)

10. evaluateS[i]

11. initialize the Global Best particle (gBest) with the best one among theSNumparticles

//初始化粒子gBest

12. end for

13. add the non-dominated solutions found inSinto EA

//添加非支配解至EA中

14. initialize the iteration numbert=0

//初始化迭代次數(shù)

15. repeat untilt>G

16. fori=1 toSNum

17. randomly select the global best particle for S from the External Archive EA and store its position ingBest

//從EA選擇全局最優(yōu)粒子

18. calculate the new velocityV[i] according to Equation (23)

//計(jì)算新的粒子速度

19. compute the new position ofS[i] according to Equation (26)

//計(jì)算新的粒子位置

20. ift

21. perform mutation onS[i]

//執(zhí)行變異操作

22. evaluateS[i]

//評估粒子

23. end for

24. update the personal best solution of each particleS[i]

//更新粒子最優(yōu)解

25. ifS[i]≤pBests[i]∨(S[i]～pBests[i])

26.pBests[i]=S[i]

27. update External ArchiveEA

//更新EA

28. add all new non-dominated solution inSintoEA

//添加新的非支配解至EA

29. ifS[i]≮x,x∈EA,EA=EA∪{S[i]}

30. remove all particles dominated byS[i] inEA

//移除所有EA中被S[i]支配的粒子

31.EA=EA-{y∈EA|y

//更新外部文檔EA

32. if the archive is full then randomly select the article to be replaced fromEA

//若EA已滿，則隨機(jī)選擇移除粒子

33. return the Pareto front

//返回Pareto邊界，即調(diào)度解集合

參數(shù)說明：SNum表示種群的粒子模型，m表示處理器資源數(shù)量，S表示粒子的群體，EA表示存儲Pareto邊界的外部存檔(External Archive)，G表示最大迭代次數(shù)，Pm表示變異概率。

算法說明：總體而言，MODPSO算法劃分為五步：第一步利用HEFT算法的調(diào)度解對種群進(jìn)行初始化操作，即步驟1-12；第二步尋找種群中的非支配解并添加至存儲Pareto邊界的外部文檔EA中，即步驟13；第三步進(jìn)行迭代初始化，即步驟14；第四步則通過循環(huán)迭代不斷對種群粒子進(jìn)行不斷進(jìn)化，即步驟15-32；第五步則返回Pareto邊界集，即步驟33。具體來說，算法首先初始化粒子位置和速度，如步驟1-12。為了得到粒子位置，每個資源的VSL(電壓和頻率)首先被隨機(jī)初始化，即步驟3，然后利用HEFT算法產(chǎn)生最小化makespan的有效可行解，即步驟4。重復(fù)該過程多次之后即可初化化群體中的所有粒子位置，如步驟5-11。初始狀態(tài)時，每個粒子的速度V和最優(yōu)位置pBest歸屬于粒子本身。算法建立一個EA(外部文檔)存儲進(jìn)化過程中找到的非支配粒子，如步驟13。在所有初始化后，算法的主循環(huán)中，在EA中選取了最優(yōu)全局位置后，計(jì)算每個粒子的新速度與位置并執(zhí)行變異操作，如步驟18-23，然后評估粒子并更新其對應(yīng)的pBest，如步驟24-28。EA在每次迭代中均需要更新，如步驟31。算法到達(dá)終止條件后，EA中存儲的Pareto邊界即為最終調(diào)度最優(yōu)解，如步驟33。

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

本節(jié)在CloudSim[16]中構(gòu)建仿真實(shí)驗(yàn)對算法有效性作出評估。實(shí)驗(yàn)中，模擬了圖1描述的人工合成工作流應(yīng)用和兩種通用工作流結(jié)構(gòu)：并行和混合結(jié)構(gòu)。選取兩種著名的現(xiàn)實(shí)世界應(yīng)用任務(wù)作為測試數(shù)據(jù)源，即以神經(jīng)科學(xué)工作流作為并行工作流應(yīng)用，基因科學(xué)工作流作為混合工作流應(yīng)用。圖2給出了兩種科學(xué)工作流的簡化結(jié)構(gòu)描述，括號中的數(shù)值表示節(jié)點(diǎn)任務(wù)的長度(執(zhí)行指令數(shù)，單位：Millions of Instructions/MI)，每個任務(wù)的輸入和輸出數(shù)據(jù)量分布于10 MB與1 024 MB之間。工作流結(jié)構(gòu)通過Pegasus工作流發(fā)生器[17]進(jìn)行創(chuàng)建。

(a) 混合工作流結(jié)構(gòu)

(b) 并行工作流結(jié)構(gòu)圖2 兩種科學(xué)工作流

實(shí)驗(yàn)分別在資源數(shù)量為3、4、5、6和12時進(jìn)行測試，資源特征如表1所示。資源定價及代價模型參考Amazon EC2[18]，不同類型資源間的數(shù)據(jù)傳輸代價模型則參考Amazon CloudFront[19]。有關(guān)MODPSO的參數(shù)設(shè)置如下：種群規(guī)模SNum=50，種群進(jìn)化最大迭代次數(shù)G=100。

由于目前缺乏考慮云資源異質(zhì)特征和同步考慮三個QoS標(biāo)準(zhǔn)(makespan、代價和能耗)的相關(guān)工作，本文選取了經(jīng)典HEFT算法及其變種多目標(biāo)算法EHEFT[12]作為性能比較的基準(zhǔn)算法，驗(yàn)證MODPSO算法在多目標(biāo)優(yōu)化上的有效性。

圖3、圖4和圖5分別給出了MODPSO和EHEFT兩種算法在合成工作流、混合工作流和并行工作流中的Pareto邊界情況，同時，MODPSO中任務(wù)優(yōu)先級由式(8)定義。可以看出，不同于EHEFT算法僅得到單個解，MODPSO算法可以得到一個非支配解集合，主要原因在于三目標(biāo)優(yōu)化是相互沖突的，不存在對于單個目標(biāo)的最優(yōu)解。同時，MODPSO算法得到的解滿足Pareto最優(yōu)，能夠在三個優(yōu)化目標(biāo)間實(shí)現(xiàn)更好的均衡。另外，針對三種不同的工作流結(jié)構(gòu)，其Pareto邊界的分布情況也是不一樣的。混合型工作流的Pareto邊界分布比較并行工作流顯得更加凌亂，主要是并行工作流的結(jié)構(gòu)具有更好的對稱性，任務(wù)的層次分明，導(dǎo)致求解Pareto最優(yōu)解時粒子位置具有更好的連貫性，其Paerto邊界分布更具有線性特征，合成工作流的結(jié)果與并行工作流的分布相近，主要是圖1的結(jié)構(gòu)接近于并行工作流特征。同時，混合型工作流中的Pareto最優(yōu)解數(shù)量也明顯多于并行工作流，這也是由其更復(fù)雜的結(jié)構(gòu)特征導(dǎo)致的。

圖3 合成工作流的非支配解

圖4 混合型工作流的非支配解

圖5 并行工作流的非支配解

表3和圖6顯示了在合成工作流中MODPSO相比較HEFT和EHEFT得到的性能增益情況。可以看出，在所提供的處理器不同時，MODPSO在makespan上平均可以降低0%和0.04%，在執(zhí)行代價上平均可以降低12.67%和9.84%，在能耗上平均可以降低27.67%和25.9%。由于HEFT是僅考慮makespan的單目標(biāo)優(yōu)化，該性能是相當(dāng)?shù)摹D6則給出了資源數(shù)量不同時的性能改進(jìn)情況。

表3 合成工作流的性能增益

圖6 不同資源量下MODPSO比較HEFT和EHEFT獲得的性能增益

表4和圖7給出了現(xiàn)實(shí)世界工作流應(yīng)用的執(zhí)行情況。表4給出了處理器改變時的性能改進(jìn)情況，可以看出，對于混合工作流結(jié)構(gòu)，MODPSO在EHEFT的QoS標(biāo)準(zhǔn)基礎(chǔ)上，在makespan上平均可以降低0.92%，在代價上平均可以降低11.76%，在能耗上平均可以降低8.32%；而對于并行工作流結(jié)構(gòu)，在makespan上平均可以降低3.29%，在代價上平均可以降低22.58%，在能耗上平均可以降低20.82%。相比HEFT的makespan基本是相當(dāng)?shù)模捎赾ost和energy的性能提升較多，主要是由于HEFT僅考慮執(zhí)行時間最小，未考慮資源代價和資源選擇優(yōu)化。比較而言，在并行工作流結(jié)構(gòu)中可以在三個目標(biāo)上實(shí)現(xiàn)更好的優(yōu)化，相比混合型工作流得到更大的增益，主要原因在于并行工作流中的任務(wù)可以并行執(zhí)行，在執(zhí)行效率與執(zhí)行代價上小于任務(wù)間約束關(guān)系更加復(fù)雜的混合型工作流結(jié)構(gòu)。

表4 現(xiàn)實(shí)科學(xué)工作流的性能增益情況

圖7 不同工作流下MODPSO比較HEFT和EHEFT獲得的性能增益

以上評估結(jié)果在人工合成工作流結(jié)構(gòu)中也可以得到證實(shí)，這表明MODPSO算法不僅可以降低執(zhí)行代價和能耗，而且在執(zhí)行跨度上也可以得到與EHEFT相近的結(jié)果，且在不同工作流結(jié)構(gòu)下結(jié)果是一致的，進(jìn)一步證明了算法的有效性。

實(shí)驗(yàn)中，由于資源數(shù)量設(shè)置了上限，可以發(fā)現(xiàn)，對于所有類型工作流結(jié)構(gòu)，某些資源并未得到利用。圖8給出了12個資源上調(diào)度人工合成工作流時的資源負(fù)載狀況。而從圖9可以看出，即使資源數(shù)量增加，總代價和總能耗也不一定減少。從圖中結(jié)果得到的結(jié)論是：1) QoS指標(biāo)會隨著資源數(shù)量增加而先降低，直到資源到達(dá)一定門限數(shù)量(本實(shí)驗(yàn)中為6)。這主要是因?yàn)橘Y源數(shù)量增加時，單個資源上調(diào)度的任務(wù)更少，任務(wù)可延長其執(zhí)行時間，而資源則有更多的機(jī)會降低其電壓和頻率以得到更少的總能耗。2) 到達(dá)門限資源數(shù)量后，QoS指標(biāo)開始提升，這是由于此時執(zhí)行時間由處理器間的通信時間支配，這會減小資源降低電壓和頻率的機(jī)率。綜合考慮，最小化QoS指標(biāo)的門限資源數(shù)量是可以獲取的。

圖8 合成工作流中資源負(fù)載狀況

圖9 合成工作流下QoS指標(biāo)的變化

5 結(jié) 語

本文提出了一種新的多目標(biāo)最優(yōu)化DAG粒子群算法MODPSO求解云環(huán)境中的工作流調(diào)度最優(yōu)化問題。算法可以同步優(yōu)化相互沖突的目標(biāo)：執(zhí)行跨度makespan、執(zhí)行代價和能耗。同時，算法可以產(chǎn)生一個非支配解集合，為用戶評估其偏好提供了更好的靈活性，并可以選取一種調(diào)度方案滿足其QoS需求。通過工作流應(yīng)用的仿真測試，驗(yàn)證了算法的性能。結(jié)果表明，算法可以產(chǎn)生較好的Pareto最優(yōu)解集合，實(shí)現(xiàn)多目標(biāo)間的均衡最優(yōu)化。