張雪峰，杜孝平，王曉健，王 哲

(1.北京賽迪工業(yè)和信息化工程監(jiān)理中心有限公司 信息化管理與咨詢部，北京 100048； 2.北京航空航天大學(xué) 軟件學(xué)院，北京 100191；3.湘潭大學(xué) 信息工程學(xué)院，湖南 湘潭 411105)

0 引 言

工作流由特定序列的相互依賴任務(wù)集組成，是建模復(fù)雜科學(xué)與商業(yè)應(yīng)用的有效工具，需要大規(guī)模計算與存儲能力支持。云計算作為一種按需資源提供技術(shù)，其服務(wù)提供商CSPs可以通過互聯(lián)網(wǎng)以即付即用的方式向云用戶分發(fā)資源和服務(wù)。由于具備彈性、高效、可靠等特點，工作流應(yīng)用在云端部署與執(zhí)行擁有其它環(huán)境不具備的優(yōu)勢。工作流中的任務(wù)將運行于數(shù)據(jù)中心內(nèi)物理主機上的虛擬機設(shè)備上，此時的工作流任務(wù)調(diào)度則是必須解決的問題[1]。大規(guī)模虛擬化云數(shù)據(jù)中心在執(zhí)行任務(wù)過程中會消耗大量能源，對環(huán)境有害。而數(shù)據(jù)中心高能量代價又會降低CSPs的收益。因此，設(shè)計滿足能效的工作流調(diào)度方法是降低數(shù)據(jù)中心能耗的關(guān)鍵。此外，CSPs可提供不同類型具有不同能力和不同代價的虛擬機，而在異構(gòu)云環(huán)境中，用戶提交的多數(shù)工作流應(yīng)用具有預(yù)算約束和截止時間限制，滿足預(yù)算約束并降低截止時間違例也是工作流調(diào)度面臨的問題。

鑒于云數(shù)據(jù)中心中進行工作流任務(wù)調(diào)度是具有約束條件的優(yōu)化問題，本文將分兩個階段完成任務(wù)執(zhí)行，設(shè)計一種基于預(yù)算約束和截止時間敏感的高能效工作流調(diào)度算法。首先根據(jù)工作流結(jié)構(gòu)中的最長路徑計算任務(wù)優(yōu)先級，并在滿足剩余預(yù)算的前提下進行一次目標虛擬機的初選；然后在不影響工作流執(zhí)行跨度和預(yù)算約束的前提下，利用動態(tài)電壓/頻率調(diào)整機制，將上一階段生成的任務(wù)映射方案的執(zhí)行時間進行擴展，以便進一步降低工作流的整體執(zhí)行能耗?；谝陨瞎ぷ?，有效實現(xiàn)高能效任務(wù)調(diào)度。

1 相關(guān)研究

近年來，云環(huán)境中工作流調(diào)度問題已有相關(guān)研究。許多工作考慮了同質(zhì)環(huán)境[2-4]，而文獻[5,6]中也考慮了異質(zhì)云環(huán)境中預(yù)算約束的工作流調(diào)度問題，但都忽略了調(diào)度時的能耗問題。另一方面，文獻[7,8]在截止時間約束下對工作流調(diào)度能耗進行了優(yōu)化，但卻忽略了執(zhí)行代價問題。云工作流調(diào)度需要同時著眼于綠色計算和CSPs運營代價的降低。為了解決以上問題，本文將設(shè)計一種異質(zhì)云環(huán)境下的工作流調(diào)度方法，實現(xiàn)在預(yù)算約束下截止時間敏感型任務(wù)的高能效調(diào)度。

工作流調(diào)度也可考慮為不同目標的優(yōu)化問題，如：最小化執(zhí)行跨度、提升能效或降低代價等。目前主要有單目標優(yōu)化和多目標優(yōu)化兩類。文獻[9]通過有效調(diào)度降低了工作流的執(zhí)行跨度，而文獻[5]則將預(yù)算滿足度考慮為首要目標。相比而言，文獻[6]提出一種公平調(diào)度策略，可以同時最小化執(zhí)行跨度和滿足預(yù)算約束。文獻[10]提出一種進化多目標優(yōu)化方法，有效降低了執(zhí)行代價和執(zhí)行跨度。文獻[8]設(shè)計了基于DVFS的能效工作流調(diào)度算法，可在給定截止時間內(nèi)調(diào)度工作流。文獻[7]為同時改進資源利用率、降低能耗和滿足截止時間設(shè)計了一種新的工作流調(diào)度算法。文獻[11]則從代價和能效方面優(yōu)化了科學(xué)工作流調(diào)度。然而，以上研究中，文獻[7,8]沒有考慮工作流執(zhí)行代價，而文獻[5,6,12]中雖然考慮預(yù)算和執(zhí)行跨度，又未考慮工作流能耗。與以上工作不同，本文將設(shè)計新的調(diào)度算法，可以在給定預(yù)算內(nèi)，確保工作流的完成，并降低執(zhí)行能耗和截止時間違例情況發(fā)生。

2 系統(tǒng)模型

2.1 云數(shù)據(jù)中心模型

云計算環(huán)境中的數(shù)據(jù)中心是一種具有標準化、高密度、模塊化特征的大型基礎(chǔ)設(shè)施。在集中化管理的基礎(chǔ)上，支持高負荷，且能耗動態(tài)的滿足用戶需求，同時具有很好的伸縮性。數(shù)據(jù)中心資源使用是即付即用的，這種模式極大地提供了對工作流模式任務(wù)調(diào)度環(huán)境的支持。假設(shè)數(shù)據(jù)中心由n臺異構(gòu)虛擬機VM構(gòu)成，表示為V={v1,v2,…,vn}。 每臺VMvk的特征屬性包括：處理速率pk，單位MIPS；單位時間代價ck。假設(shè)數(shù)據(jù)中心提供x種類型VM，表示為Vtype={τ1,τ2,…,τx}，V中的每臺VM屬于Vtype中的一種特定類型，且相同類型的VM擁有相同特征屬性。

2.2 工作流模型

工作流應(yīng)用W可表示為有向無環(huán)圖G(T,E)，T={t1,t2,…,tm} 表示任務(wù)集，E表示任務(wù)間的有向邊集。任務(wù)ti的長度為li，單位MI。G(T,E) 的有向邊代表任務(wù)間的依賴。若在ti與tj間存在有向邊，則表明ti是tj的直接前驅(qū)，而tj是ti的直接后繼。集合pre(ti) 和suc(ti) 分別代表ti的所有直接前驅(qū)和直接后繼集合。ti與tj間的數(shù)據(jù)傳輸時間表示為TTij，取決于任務(wù)間的數(shù)據(jù)傳輸量及數(shù)據(jù)中心的內(nèi)部網(wǎng)絡(luò)帶寬。若ti與tj分配至同一VM上，則TTij=0。Tentry表示工作流中無任一前驅(qū)的入口任務(wù)集，Texit表示無任一前驅(qū)的出口任務(wù)集。

ti在VMvk上的執(zhí)行時間定義為ET(ti,vk)

ET(ti,vk)=li/pk

(1)

ti的最早開始時間EST(ti) 和最早完成時間EFT(ti) 通過如下遞歸方式計算

(2)

EFT(ti)=EST(ti)+ET(ti,vf(ti))

(3)

式中：f(ti) 和f(tp) 分別表示執(zhí)行ti和tp的VM索引號。

最遲開始時間LST(ti) 和最遲完成時間LFT(ti) 分別通過如下遞歸方式計算

(4)

LFT(ti)=LST(ti)+ET(ti,vf(ti))

(5)

式中：Wm,e表示工作流的估計執(zhí)行跨度makespan，計算為

(6)

Wm,e表示的是假設(shè)所有任務(wù)調(diào)度至最快類型VM上執(zhí)行時得到的執(zhí)行跨度，它被考慮為工作流的最小執(zhí)行跨度makespan。因此，工作流的截止時間WD可作如下定義

WD=α·Wm,min

(7)

式中：α為云用戶定義的截止時間因子，且α≥1。

2.3 能量模型

假設(shè)云基礎(chǔ)設(shè)施中的物理主機支持動態(tài)電壓/頻率擴展技術(shù)DVFS，每臺VM分配一個虛擬CPU vCPU，對應(yīng)于物理主機一個內(nèi)核。因此，VMvk∈V可以通過在 [Vk,min,Vk,max] 之間改變電壓等級運行在特定的CPU頻率上，頻率范圍為 [fk,min,fk,max]。 VMvk的動態(tài)功耗表示為

Pk=K·(Vk,l)2·fk,l

(8)

式中：K為與動態(tài)功率相關(guān)的常量參數(shù)，Vk,l為VMvk在等級l上的供應(yīng)電壓，fk,l為VMvm對應(yīng)電壓Vk,l的CPU頻率。則ti在vk上的執(zhí)行能耗E=PkET(ti,vk)。 故工作流W的總執(zhí)行能耗為

(9)

VMvk的處理速率pk取決于電壓和頻率，處于區(qū)間 [pk,min,pk,max]。pk,l代表電壓/頻率組合 (Vk,l,fk,l) 時VM的處理速率。盡管虛擬機在工作時可運行于最大電壓等級上，但利用DVFS可以動態(tài)的調(diào)整其電壓和頻率，從而提升能效。

在云數(shù)據(jù)中心內(nèi)進行工作流調(diào)度，需要基于當前數(shù)據(jù)中心內(nèi)虛擬機的資源配置和使用狀況，將每個工作流任務(wù)調(diào)度至目標函數(shù)最優(yōu)的虛擬機上執(zhí)行。尤其在異構(gòu)虛擬機配置下，任務(wù)的調(diào)度代價、計算時間都有所不同。尤其是，在任務(wù)執(zhí)行時，會導(dǎo)致物理主機相應(yīng)能耗時，工作流調(diào)度問題將需要理更全面的考慮影響因素，進而設(shè)計在約束條件下高能效的調(diào)度算法。

2.4 工作流預(yù)算約束

任務(wù)ti在VMvk上的執(zhí)行費用代價為

(10)

式中：ck為VMvk的單位時間內(nèi)的使用代價。則工作流的總執(zhí)行代價為

(11)

令cτq、pτq,min和pτq,max分別表示類型為τq的虛擬機VM的單位時間代價、最小處理速率和最大處理速率。對于相同類型的虛擬機，則擁有相同的單位時間代價和處理速率范圍。即：對于類型為τq的虛擬機vk，單位時間代價ck=cτq， 處理速率范圍 [pk,min,pk,max]=[pτq,min,pτq,max]。

對于類型為τq的虛擬機vk，計算其cτq/pτq,max。 工作流調(diào)度最小代價Cl的計算方式是：將所有工作流任務(wù)調(diào)度至擁有最小cτq/pτq,max值的虛擬機類型τq上的所得代價。而最高代價Ch則是將所有工作流任務(wù)調(diào)度至最大cτq/pτq,max值的虛擬機類型τq執(zhí)行所得代價。因此，可將工作流預(yù)算定義為

BW=Cl+β·(Ch-Cl)

(12)

式中：β為預(yù)算因子，且β∈[0,1)。

因此，工作流調(diào)度的預(yù)算約束為：CW≤BW。

3 工作流調(diào)度算法ESDWB

工作流調(diào)度算法的目標是在確保預(yù)算約束的同時，降低執(zhí)行能耗和截止時間違例。該問題本質(zhì)上是NP問題，本文將設(shè)計一種啟發(fā)式算法對其進行求解。

3.1 任務(wù)的截止時間、優(yōu)先級和預(yù)算

假設(shè)每個任務(wù)在最快類型的VM上執(zhí)行，通過式(4)、式(5)可計算其最遲開始時間LST(ti) 和最遲完成時間LFT(ti)。 因此，可以按比例擴展LFT(ti) 決定任務(wù)ti的截止時間D(ti)

D(ti)=α·LFT(ti)

(13)

若每個任務(wù)在其截止時間內(nèi)完成，則可確保工作流整體在截止時間WD內(nèi)完成。

為了實現(xiàn)待調(diào)度任務(wù)的選擇，以下列方式為任務(wù)分配優(yōu)先級

(14)

式中：ETavg(ti)為所有VM類型上任務(wù)執(zhí)行的平均時間，而優(yōu)先級Pr(ti)代表ti至出口任務(wù)間的最長路徑。

為了決定單個任務(wù)的預(yù)算，引入?yún)?shù)工作流剩余預(yù)算SBW。初始SBW設(shè)置為BW-Cl。令cmin(ti) 為執(zhí)行ti的最小代價。則對于第一個調(diào)度的任務(wù)ti，其預(yù)算為

B(ti)=SBW+cmin(ti)

(15)

算法需要為ti選擇合適的vk，使得ti在vk上的執(zhí)行代價c(ti,vk) 在B(ti) 以內(nèi)。而任務(wù)ti調(diào)度后，SBW更新為

SBW=SBW-(c(ti,vk)-cmin(ti))

(16)

通過這種方式，調(diào)度每個任務(wù)后，更新SBW，進而在新的SBW基礎(chǔ)上決定下一調(diào)度任務(wù)的預(yù)算。

3.2 ESDWB算法詳細設(shè)計

本文將提出的截止時間敏感和預(yù)算約束的能效工作流調(diào)度算法命名為ESDWB，詳細過程如算法1所示。ASF(ti,vk) 和AFT(ti,vk) 分別代表ti在vk上的實際開始時間和實際完成時間。為了計算ASF(ti,vk)， 引入PST(ti) 代表ti的可能開始時間，定義為

(17)

這表明只有在所有前驅(qū)任務(wù)完成并發(fā)送數(shù)據(jù)后，ti才可能執(zhí)行。ASF(ti,vk) 和AFT(ti,vk) 分別遞歸定義如下

(18)

式中：Tk,i為ti之前調(diào)度至vk上的任務(wù)集，tb為ti之前vk上的調(diào)度任務(wù)

AFT(ti,vk)=AST(ti,vk)+ET(ti,vk)

(19)

因此，工作流的實際執(zhí)行跨度makespanWm,a和截止時間違例比例可分別計算為

(20)

(21)

ESDWD算法：算法1首先嘗試將ti調(diào)度至正在執(zhí)行其前驅(qū)任務(wù)的VM上(步驟(8)～步驟(18))以避免數(shù)據(jù)傳輸時間，從而降低ti的實際完成時間，這同時還有助于減小工作流調(diào)度的實際makespanWm,a和截止時間違例比例DV。若ti沒有前驅(qū)，或存在截止時間違例/預(yù)算約束問題，無法進行以上選擇，則重新為其選擇合適的VM類型，即步驟(9)～步驟(38)。此過程中，需要計算在其截止時間以內(nèi)完成ti的最小處理速率ps(ti)

(22)

計算ps(ti) 后，即可決定截止時間以內(nèi)可完成ti的VM類型，將其定義為集合Q。算法1將Q按處理速率升序排列并嘗試為ti選擇VM類型，越低的速率對應(yīng)越小的電壓和頻率，能耗也更低。若Q中的VM類型無法保證任務(wù)在預(yù)算內(nèi)完成，則選擇違例任務(wù)截止時間的VM類型。同時需要選擇在其預(yù)算內(nèi)可用的最快VM類型，即步驟(31)～步驟(37)。算法1中，G代表在預(yù)算B(ti) 內(nèi)能夠調(diào)度ti的VM類型集合，τb為G中最快處理速率的VM成員。通過這種方式，可以計算工作流的實際跨度makespanWm,a。

算法1：ESDWB

輸入：工作流W，截止時間WD，預(yù)算BW

輸出：工作流調(diào)度解SW

(1)determine deadlineD(ti) of each tasktiin task setTofWusing Eq.(13)

(2)calculate priorityPr(ti) of each task using Eq.(14)

(3)sort the tasks inTin descending order of their prio-rities

(4)SBW←SBW-Cl,SW←null

(5)foreachti∈Tdo

(6)vf(ti)←null

(7) calculateB(ti) using Eq.(15)

(8)if(pred(ti)≠null)then

(9) sort the tasks inpred(ti) in descending order of the data size to be thansferred toti

(10)foreachtp∈pred(ti)do

(11)vk←vf(tp)

(12)if((AFT(ti,vk)≤D(ti) && (c(ti,vk)≤B(ti)))then

(13)vf(ti)←vk,SW←SW∪

(14) updateSBWusing Eq.(16)

(15)break

(16)endif

(17)endforeach

(18)endif

(19)if((pred(ti)=null) or (vf(ti)=null))then

(20) computeps(ti) using Eq.(22)

(21)Q←{τq|τq∈Vtype∧(pτq,max≥ps(ti))}

(22) sort the VM type in setQin ascending order of theirpτq,maxvalues

(23)foreachτq∈Qdo

(24) consider an idle or new VMvkof typeτq

(25)if(c(ti,vk)≤B(ti))then

(26)vf(ti)←vk,SW←SW∪

(27) updateSBWusing Eq.(16)

(28)break

(29)endif

(30)endforeach

(31)if(vf(ti)=null)then

(32)G←{τg|τg∈Vtype∧(li/pτg,max×cτg≤B(ti))}

(33)τb←{τg|τg∈G∧(pτg,max≥pτy,max,τy∈G)}

(34) consider an idle or new VMvkof typeτb

(35)vf(ti)←vk,SW←SW∪

(36) updateSBWusing Eq.(16)

(37)endif

(38)endif

(39)endforeach

(40)calculate actual makespan of workflowWm,ausing Eq.(20)

(41)SW←ERT(SW,Wm,a)//調(diào)用算法2

(42)calculate energyEWand costCWusing Eq.(9) and Eq.(11)

(43)calculate Deadline violationDVusing Eq.(21)

(44)returnSW

算法2的作用是在不影響工作流W執(zhí)行跨度和預(yù)算約束下的情況下，利用DVFS擴展前一階段的任務(wù)完成時間以降低能耗。其中，ExFT(ti) 為ti的擴展完成時間，定義為

(23)

上式表明ti的擴展完成時間并未影響工作流的執(zhí)行跨度和后繼任務(wù)的實際開始時間。

若ExFT(ti)大于AFT(ti)，則認為ti擁有松馳時間可以擴展。調(diào)度至vk上的ti的完成時間可擴展至其可能的完成時間PExET(ti,vk)

(24)

當決定ti在vk上可能的擴展完成時間時，考慮以下兩種情況：

Case2：ti之后無其它任務(wù)調(diào)度至vk。

在可能的擴展完成時間PExFT(ti,vk) 內(nèi)在vk上完成ti的最小處理速率pmin(ti,vk) 計算為

(25)

算法2需要尋找速率大于等于pmin(ti,vk) 的可行vk集合PS。滿足pk,l=min(PS) 條件將得到最小的能耗。vk執(zhí)行ti的能耗為

E=(K·(Vk,l)2·fk,l)·(li/pk,l)

(26)

由于處理速率正比于頻率，則能耗E∝(Vk,l)2。 由后文表1可知，以于給定的VM類型，電壓越低，頻率越低，處理速率也越低。因此，需要從PS中選擇最小的處理速率，并更新VM的頻率，即步驟(8)～步驟(12)，這有助于降低能耗。

算法2：ERT-Energy Reduction of Tasks

輸入：工作流調(diào)度解SW，工作流實際執(zhí)行跨度Wm,a

輸出：更新后的調(diào)度解SW

(1)foreachti∈Tdo

(2)vk←vf(ti)

(3) calculateExFT(ti) using Eq.(23)

(4)if(ExFT(ti)>AFT(ti,vk))then

(5) determinePExFT(ti,vk) using Eq.(24)

(6) calculatepmin(ti,vk) using Eq.(25)

(7)PS←{pk,l|pk,l∈[pk,min,pk,max]∧(pk,l≥pmin(ti,vk))}

(8)pk,l←min(PS),fk,l←frequency corresponding topk,l

(9)ifpk,l

(10) update the frequency of VMvkfromfk,maxtofk,lfor taskti

(11) updateET(ti,vk) andAFT(ti,vk) in the scheduleSW

(12)endif

(13)endif

(14)endforeach

(15)returnSW

4 實驗評估

4.1 實驗搭建

利用WorkflowSim平臺[13]模擬云數(shù)據(jù)中心模型進行實驗仿真。數(shù)據(jù)中心中虛擬機VM類型有3種Type1、Type2和Type3，3種VM類型分別運行ADM Turion MT-34處理器、AMD Opteron 2218處理器和Intel Xeon E5450處理器。表1給出了3類虛擬機中處理器的處理屬性。3種VM類型中每臺VM的代價分別為$0.0058/hour、$0.0116/hour和$0.023/hour，這些取值對應(yīng)于Amazon EC2中按需VM實例的vCPU的利用代價[14]。同時，與Google和Amazon的云服務(wù)提供商CSPs類似，將VM的帳單周期定義為最小值1 min，即：VM運行不滿1 min依然按1 min收費。假設(shè)數(shù)據(jù)中心內(nèi)虛擬機間的平均帶寬為1 Gps。

利用4種現(xiàn)實科學(xué)工作流結(jié)構(gòu)CyberShake、Epigeno-mics、SIPHT和Montage進行仿真測試，科學(xué)工作流具體特征見文獻[15]。由于截止時間因子α和預(yù)算因子β對工作流的截止時間滿意度具有較大影響，構(gòu)建不同的(α,β)取值給合進行實驗。對于特定的β值，更大的α可以增加截止時間滿意的概率。而對于特定的α值，更大的β可以增加預(yù)算滿意的概率。通過調(diào)整(α,β)，用戶可以根據(jù)工作流調(diào)度的時間和代價的優(yōu)先考慮在其中進行取舍。

表1 不同處理器的電壓/頻率配置

為了評估ESDWB算法的性能，將其與兩種典型工作流調(diào)度算法FBCWS[6]和DEWTS[8]進行對比分析。FBCWS算法在滿足用戶預(yù)算的前提下嘗試最小化工作流執(zhí)行跨度，而DEWTS算法在確保執(zhí)行跨度在截止時間內(nèi)的前提下降低工作流調(diào)度能耗。

4.2 性能指標

標準化能耗NEC：工作流W調(diào)度的標準化能耗NEC定義為

NEC=EW/EW,min

(27)

式中：EW為式(9)計算的工作流W的執(zhí)行能耗，EW,min為所有算法中獲得的最小能耗值。

標準化跨度NM：工作流W調(diào)度的標準化跨度定義為

NM=Wm,a/WD

(28)

式中：Wm,a為式(20)計算的工作流實際執(zhí)行跨度，WD為工作流截止時間。若NM大于1，表明截止時間發(fā)生違例。

標準化代價NC：工作流W調(diào)度的標準化代價NC定義為

NC=CW/BW

(29)

若NC大于1，表明調(diào)度代價超過工作流預(yù)算約束。

選擇標準化能耗、跨度和代價3個指標進行性能對比的原因在于：對于云數(shù)據(jù)中心環(huán)境中的工作流調(diào)度問題而言，調(diào)度能耗、跨度和代價3個指標間擁有相互沖突的性質(zhì)。通常，性能越強的虛擬機可以提升工作流執(zhí)行效率，降低跨度，但執(zhí)行代價也越高。而執(zhí)行能耗又同時與執(zhí)行時間和虛擬機功率(計算性能)相關(guān)。而取標準值后可以統(tǒng)一比較的量綱。3個指標的選取也可以更加全面比較調(diào)度算法的綜合性能。

4.3 實驗分析

圖1～圖3是仿真實驗結(jié)果?？梢钥吹?，F(xiàn)BCWS算法可以保證執(zhí)行代價在預(yù)算以內(nèi)，并有效降低執(zhí)行跨度，但會導(dǎo)致較高能耗。DEWTS算法可以降低能耗并滿足工作流截止時間限制，但執(zhí)行代價增加并超過了預(yù)算約束。本文的ESDWB算法可以在預(yù)算內(nèi)有效調(diào)度工作流，并同時降低了截止時間違例和執(zhí)行能耗。同時，ESDWB算法得到的執(zhí)行跨度基本落入截止時間以內(nèi)，即使未在截止時間內(nèi)，也僅是較小的比例，但依然保持了代價在預(yù)算以內(nèi)。對于CyberShake和Epigenomics工作流而言，包含大量任務(wù)間的數(shù)據(jù)傳輸，而ESDWB算法得到的執(zhí)行跨度依然小于FBCWS和DEWTS算法，這是由于ESDWB算法會盡可能將存在多數(shù)據(jù)傳輸?shù)那膀?qū)任務(wù)和后繼任務(wù)調(diào)度至相同虛擬機類型上，如此降低了數(shù)據(jù)傳輸時間。

此外，ESDWB算法還通過DVFS調(diào)整虛擬機的電壓和頻率，有效實現(xiàn)能效提升。盡管一些情況中ESDWB算法的能耗高于DEWTS算法，但依然低于FBCWS算法。而且，與DEWTS算法不同，ESDWB算法的執(zhí)行代價從未超過預(yù)算約束。因此，綜合在能效提升、降低執(zhí)行跨度和代價方面，本文的ESDWB算法依然是3種算法中表現(xiàn)最好的。

對于不同類型的工作流任務(wù)而言，Epigenomics任務(wù)以計算密集型為主，Montage任務(wù)以I/O密集型為主，對CPU要求不高，SIPHT任務(wù)以計算密集型為主，對內(nèi)存要求較高，而CyberShake任務(wù)以數(shù)據(jù)密集型為主，對計算能力和內(nèi)存存儲均有較高要求。在NEC測試結(jié)果上，ESDWS算法在CyberShake和Montage工作流上都得到了最少的能耗，在Epigenomics和SIPHT工作流上略高于DEWTS算法。在NM測試結(jié)果上，ESDWS算法在CyberShake和Epigenomics工作流上跨度最小，在SIPHT和Montage工作流上略高。在NC測試結(jié)果上，ESDWS算法則在4種工作流類型上都擁有最小的執(zhí)行代價。綜合來看，無論工作流中的任務(wù)類型如何變化，ESDWS算法在綜合優(yōu)化調(diào)度能耗、執(zhí)行跨度，尤其是計算代價方面，還是具有更穩(wěn)定的性能。

5 結(jié)束語

本文提出了一種面向截止時間敏感和預(yù)算約束的能效云工作流調(diào)度算法。算法可以保證調(diào)度解代價在預(yù)算約束內(nèi)，并通過有效綻放處理器速率將任務(wù)調(diào)度至合適的虛擬機上，同時避免任務(wù)的截止時間違例。此外，基于DVFS的處理器頻率降低還提升的調(diào)度能效，降低了數(shù)據(jù)中心能耗。實驗結(jié)果驗證了算法的性能優(yōu)勢。下一步的研究方向可以探索考慮工作流任務(wù)間數(shù)據(jù)傳輸代價的工作流調(diào)度算法研究問題，也可以從多云模型的角度研究工作流的調(diào)度問題。