預算約束和截止時間敏感的高能效云工作流調度

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

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

0 引 言

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

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

1 相關研究

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

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

2 系統模型

2.1 云數據中心模型

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

2.2 工作流模型

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

ti在VMvk上的執行時間定義為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) 分別表示執行ti和tp的VM索引號。

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

(4)

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

(5)

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

(6)

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

WD=α·Wm,min

(7)

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

2.3 能量模型

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

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

(8)

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

(9)

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

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

2.4 工作流預算約束

任務ti在VMvk上的執行費用代價為

(10)

式中：ck為VMvk的單位時間內的使用代價。則工作流的總執行代價為

(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。 工作流調度最小代價Cl的計算方式是：將所有工作流任務調度至擁有最小cτq/pτq,max值的虛擬機類型τq上的所得代價。而最高代價Ch則是將所有工作流任務調度至最大cτq/pτq,max值的虛擬機類型τq執行所得代價。因此，可將工作流預算定義為

BW=Cl+β·(Ch-Cl)

(12)

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

因此，工作流調度的預算約束為：CW≤BW。

3 工作流調度算法ESDWB

工作流調度算法的目標是在確保預算約束的同時，降低執行能耗和截止時間違例。該問題本質上是NP問題，本文將設計一種啟發式算法對其進行求解。

3.1 任務的截止時間、優先級和預算

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

D(ti)=α·LFT(ti)

(13)

若每個任務在其截止時間內完成，則可確保工作流整體在截止時間WD內完成。

為了實現待調度任務的選擇，以下列方式為任務分配優先級

(14)

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

為了決定單個任務的預算，引入參數工作流剩余預算SBW。初始SBW設置為BW-Cl。令cmin(ti) 為執行ti的最小代價。則對于第一個調度的任務ti，其預算為

B(ti)=SBW+cmin(ti)

(15)

算法需要為ti選擇合適的vk，使得ti在vk上的執行代價c(ti,vk) 在B(ti) 以內。而任務ti調度后，SBW更新為

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

(16)

通過這種方式，調度每個任務后，更新SBW，進而在新的SBW基礎上決定下一調度任務的預算。

3.2 ESDWB算法詳細設計

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

(17)

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

(18)

式中：Tk,i為ti之前調度至vk上的任務集，tb為ti之前vk上的調度任務

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

(19)

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

(20)

(21)

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

(22)

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

算法1：ESDWB

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

輸出：工作流調度解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)//調用算法2

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

(43)calculate Deadline violationDVusing Eq.(21)

(44)returnSW

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

(23)

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

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

(24)

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

Case2：ti之后無其它任務調度至vk。

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

(25)

算法2需要尋找速率大于等于pmin(ti,vk) 的可行vk集合PS。滿足pk,l=min(PS) 條件將得到最小的能耗。vk執行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

輸入：工作流調度解SW，工作流實際執行跨度Wm,a

輸出：更新后的調度解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]模擬云數據中心模型進行實驗仿真。數據中心中虛擬機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，這些取值對應于Amazon EC2中按需VM實例的vCPU的利用代價[14]。同時，與Google和Amazon的云服務提供商CSPs類似，將VM的帳單周期定義為最小值1 min，即：VM運行不滿1 min依然按1 min收費。假設數據中心內虛擬機間的平均帶寬為1 Gps。

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

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

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

4.2 性能指標

標準化能耗NEC：工作流W調度的標準化能耗NEC定義為

NEC=EW/EW,min

(27)

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

標準化跨度NM：工作流W調度的標準化跨度定義為

NM=Wm,a/WD

(28)

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

標準化代價NC：工作流W調度的標準化代價NC定義為

NC=CW/BW

(29)

若NC大于1，表明調度代價超過工作流預算約束。

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

4.3 實驗分析

圖1～圖3是仿真實驗結果。可以看到，FBCWS算法可以保證執行代價在預算以內，并有效降低執行跨度，但會導致較高能耗。DEWTS算法可以降低能耗并滿足工作流截止時間限制，但執行代價增加并超過了預算約束。本文的ESDWB算法可以在預算內有效調度工作流，并同時降低了截止時間違例和執行能耗。同時，ESDWB算法得到的執行跨度基本落入截止時間以內，即使未在截止時間內，也僅是較小的比例，但依然保持了代價在預算以內。對于CyberShake和Epigenomics工作流而言，包含大量任務間的數據傳輸，而ESDWB算法得到的執行跨度依然小于FBCWS和DEWTS算法，這是由于ESDWB算法會盡可能將存在多數據傳輸的前驅任務和后繼任務調度至相同虛擬機類型上，如此降低了數據傳輸時間。

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

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

5 結束語

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