截止時(shí)間約束的工作流調(diào)度自適應(yīng)進(jìn)化方法

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

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

1 相關(guān)知識(shí)

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

1.1 適應(yīng)度

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

1.2 選擇概率

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

1.3 交叉概率與變異概率

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

1.4 懲罰函數(shù)

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

2 工作流建模

圖1 簡(jiǎn)單工作流模型

將工作流建模為一個(gè)有向無(wú)環(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é)點(diǎn)，而任務(wù)tj可以認(rèn)為是任務(wù)ti的子節(jié)點(diǎn)。換句話說(shuō)，任務(wù)ti的輸出數(shù)據(jù)作為任務(wù)tj的輸入數(shù)據(jù)?；谶@樣的描述，一個(gè)子節(jié)點(diǎn)任務(wù)能夠執(zhí)行的前提是其所有父節(jié)點(diǎn)任務(wù)全部執(zhí)行完畢， 假設(shè)任務(wù)ti的父節(jié)點(diǎn)任務(wù)只有任務(wù)tj，不存在其它父節(jié)點(diǎn)任務(wù)依賴，任務(wù)tj必須等其父節(jié)點(diǎn)任務(wù)ti執(zhí)行完成之后才能開(kāi)始執(zhí)行。不具有父節(jié)點(diǎn)任務(wù)的任務(wù)則稱為根任務(wù)，用troot表示；不具有子節(jié)點(diǎn)任務(wù)的任務(wù)稱為葉子任務(wù)，用tleaf表示。此外，每個(gè)工作流WFG均具有一個(gè)截止時(shí)間DLWFG，作為工作流WFG最長(zhǎng)執(zhí)行時(shí)間的時(shí)間約束。圖1展示了一個(gè)簡(jiǎn)單工作流模型，圖中每個(gè)節(jié)點(diǎn)表示一個(gè)任務(wù)ti，節(jié)點(diǎn)之間的箭頭表示數(shù)據(jù)依賴關(guān)系eij。

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

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

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

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

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

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

Minimize(TEC) Subjuct to:TET≤DLWFG

(1)

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

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

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

(2)

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

針對(duì)云計(jì)算環(huán)境下有約束工作流調(diào)度問(wèn)題進(jìn)一步建模分析，提出了一種基于適應(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è)體，構(gòu)建初代種群；

(2)評(píng)價(jià)當(dāng)前種群中每個(gè)個(gè)體；

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

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

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

①選擇個(gè)體作為下代種群的親代；

②通過(guò)交叉操作得到新的子代；

③評(píng)價(jià)所得個(gè)體；

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

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

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

(3)

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

為了防止因?yàn)榕既灰蛩貙?dǎo)致優(yōu)秀的個(gè)體沒(méi)有被選中的情況出現(xiàn)，在從當(dāng)代種群選擇個(gè)體時(shí)，進(jìn)行多次選擇，將選擇出來(lái)的個(gè)體組成規(guī)模為z的群體。

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

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

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

(4)

(5)

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

(6)

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

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

(7)

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

(8)

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

(9)

(10)

圖3 種群分布情況示意

通常情況下，懲罰函數(shù)同個(gè)體違反約束的程度成正比，當(dāng)個(gè)體違反約束程度越高時(shí)，應(yīng)受到越嚴(yán)厲的懲罰；當(dāng)個(gè)體違反約束程度越低時(shí)，應(yīng)受到較輕的懲罰。同時(shí)，考慮到種群中個(gè)體分布情況rf，圖3示意了種群的分布情況，其中a、d子圖分別表示完全滿足約束條件(rf= 1)和完全不滿足約束條件(rf= 0)的情況；b子圖表示滿足約束條件個(gè)體占大多數(shù)(rf> 0.5)的情況；c子圖表示不滿足約束條件個(gè)體占大多數(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)度計(jì)算函數(shù)如式(12)所示，由2部分構(gòu)成。

(12)

4 實(shí)驗(yàn)結(jié)果與分析

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

4.1 測(cè)試工作流

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

4.2 虛擬機(jī)配置模擬

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

表1 實(shí)驗(yàn)中所使用的虛擬機(jī)類型及其收費(fèi)標(biāo)準(zhǔn)

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

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

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

4.4 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

5 結(jié)論

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