一種云工作流任務調度能效優(yōu)化算法

王國豪，李慶華 ，劉安豐

1.麗水學院 工學院，浙江 麗水 323000

2.中南大學 信息科學與工程學院，長沙 410083

作為高性能計算平臺，云計算越來越多地為大規(guī)模密集型工作流應用提供了高性能的異構資源和運行環(huán)境[1]。工作流是任務間存在順序約束的一種應用模型，在科學、工業(yè)和工程領域中均得到了廣泛應用。而云環(huán)境中的工作流任務調度問題本質是在不同的可用資源與任務之間實現(xiàn)有效映射[2]，同時維持任務間固有的順序約束?；谫Y源提供方與用戶方對任務執(zhí)行的不同需求，云工作流調度目標也有所差異，主要考慮的優(yōu)化目標包括：執(zhí)行時間或執(zhí)行代價、系統(tǒng)可靠性等等。然而，由于云數(shù)據中心的廣泛部署的原因，能耗已經成為目前云計算環(huán)境面臨的主要難題，高能耗不僅提升成本，而且對環(huán)境有害。

目前，動態(tài)電壓/頻率擴展DVFS技術是云資源方在處理器上應用的一種能耗優(yōu)化常用方法，它可以根據資源負載動態(tài)縮放處理器電壓/頻率，降低處理器能耗[3]。但是，降低處理器資源的能耗的同時處理器的性能同樣會降低，這會導致工作流任務執(zhí)行時間的增加，并可能導致無法滿足期限時間的QoS約束。為了在滿足截止時間約束的同時提高工作流調度的能效，實現(xiàn)性能與能效的均衡調度，本文提出一種工作流任務調度能效優(yōu)化算法，算法以三階段式完成調度：初始任務映射、處理器資源合并和任務松馳。算法可在滿足截止時間約束同時降低執(zhí)行能耗，提高資源利用率，實現(xiàn)用戶需求與資源能耗的均衡。

1 相關工作

啟發(fā)式算法是解決工作流調度這類NP問題的常用方法，如基于異構最早完成時間的HEFT算法[4]可以以較低的時間復雜度得到較小的工作流執(zhí)行時間。同類型的啟發(fā)式算法通常以系統(tǒng)為中心或以用戶為中心選擇相應的優(yōu)化指標，如：執(zhí)行跨度[5]、資源利用率[6]、系統(tǒng)可靠性[7]和總體執(zhí)行代價[8]。這類線性啟發(fā)式算法通常都是單目標優(yōu)化的，基本不考慮執(zhí)行工作流任務時給資源方帶來的能耗問題。

考慮能耗問題的文獻中，文獻[9]提出一種選擇能量感知調度算法EAS，算法建立了一種考慮能耗和執(zhí)行時間的相對優(yōu)越函數(shù)，對于給定的任務，通過考慮當前最佳資源及其相應電壓縮放等級計算該函數(shù)值，并選擇最大的函數(shù)對應的資源作為任務的調度目標。但該調度結果是局部最優(yōu)的。文獻[10]提出基于復制與能量平衡調度算法EDB，算法可以通過副本機制提高工作流執(zhí)行效率，并維持可接受的能耗開銷，但由于算法中處理器始終處于最大電壓/頻率等級，因此總體而言，能耗過大。文獻[11]提出能量感知DAG調度算法EADAG，算法通過求解決定路徑的方式得到最小調度時間，同時在空閑調度中可以進行處理器電壓調整以降低能耗，同時對執(zhí)行時間也未產生影響。該算法與本文算法雖有類似，但在目標資源選擇上不是能效最優(yōu)的。文獻[12]提出基于DVFS的加強能效調度算法EES，可降低非關鍵任務的執(zhí)行頻率，將任務重分配至得到更低能耗的合適時間槽中。比較國外文獻，國內云工作流調度相關研究中[13～16]則甚少考慮能效優(yōu)化問題。

對于云環(huán)境，降低調度能耗不僅可以降低經濟代價，更可以提升系統(tǒng)服務可靠性。為了解決這一問題，在滿足截止時間約束時提高調度能效，實現(xiàn)性能與能效的均衡調度，本文提出一種工作流任務調度能效優(yōu)化算法，將工作流任務的能效調度優(yōu)化過程以三階段式進行：初始任務映射、處理器資源合并和任務松馳。算法可以在滿足截止時間約束的同時降低工作流的執(zhí)行能耗，提高資源利用率，實現(xiàn)用戶需求與資源能耗的均衡。

2 系統(tǒng)模型

2.1 資源模型

目標系統(tǒng)由異質處理器資源集合組成，表示為：P={pi}，處理器之間以全連通拓撲結構連接。任務集為：N={ni}。每個處理器 pj∈P具有DVFS功能，即可運行于不同的供電電壓與時鐘頻率，對應的計算性能可動態(tài)改變。對于處理器 pj∈P，定義其可運行的供電電壓集合為V={vs}，可運行的時鐘頻率集合為F={fs}。對應地，電壓運行等級為v1時，對應的時鐘頻率為等級f1。由于處理器資源在空閑狀態(tài)時仍然消耗能源，此時運行于最低頻率狀態(tài)vlowest，并對應處理器最大限度的能耗節(jié)省。

2.2 云工作流任務模型

云計算應用通常為并行的工作流任務，以有向無循環(huán)圖DAG表示，如圖1所示案例。工作流任務表示為G=(N,E)，由頂點集合N和有向邊集E組成，N為應用中的n個任務集合，E為任務間的邊集合，代表任務間的順序約束。任務ni與nj間的邊edge(i,j)∈E表示任務間的通信關系，僅當任務ni傳輸其輸出后任務nj才可以開始執(zhí)行。

工作流中，無前驅的任務稱為DAG入口任務（如圖1中的nentry），無后繼的任務稱為DAG出口任務（如圖1中的 nexit）。

圖1 工作流任務DAG示例

令wi,j為任務ni在處理器 pj上的執(zhí)行代價，則ni在所有可用資源上的平均執(zhí)行代價AECi可定義為：

定義DAG中有向邊的權值為ci,j，表示任務ni與nj間的通信代價。若任務ni與nj調度至同一資源執(zhí)行，此時忽略資源內的通信代價，定義ci,j=0。資源間的數(shù)據傳輸速率存儲于大小為 p×p的矩陣B內，資源的通信代價則由 p維向量S定義。定義為datai,j為任務ni與nj間的數(shù)據傳輸量，則調度至資源 pm的任務ni與調度至pk的任務nj間的通信代價可定義為：

則任務ni與nj間的平均通信代價可定義為：

其中，ATR為資源間的平均傳輸速率，ATC為通信啟動的平均時間代價。在進行任務調度時，任務按自底向下分級值的形式對任務進行優(yōu)先級排序，任務ni的分級值以遞歸方式定義為：

令EST(ni,pj)為調度至資源 pj的任務ni的最早開始時間，EFT(ni,pj)為調度至資源 pj的任務ni的最早完成時間。對于入口任務nentry，其EST計算為：

對于任務DAG模型中的其他任務（從入口任務開始），其EST和EFT的計算方法為：

其中，avil[pj]為資源 pj上最后調度的任務nk的最早完成時間，pred(ni)為任務ni的直接前驅集：

AFT(nm)為任務task(nm)的實際完成時間。如果任務為非入口任務，則返回任務ni所需所有數(shù)據到達資源pj的時間。AST(nm)為任務task(nm)的實際開始時間。如果nm=nentry,則AST(nm)=EST(nm)=EST(nentry)=0,此時可以通過遞歸計算AFT(nm)=AST(nm)+tm得到AFT(nm)。

DAG中的所有任務調度后，調度長度為出口任務nexit的實際完成時間。定義調度任務的最長路徑為關鍵路徑CP，最遲完成任務的完成時間為調度長度或makespan。如果出口任務多于一個，則最遲任務的makespan可定義為：

2.3 能耗模型

云環(huán)境中資源執(zhí)行任務的主要能耗來源包括動態(tài)功能 Edynamic和靜態(tài)功耗 Estatic，Estatic與 Edynamic成正比，且通常少于動態(tài)能耗Edynamic的30%，通常情況下，資源方總體能耗由動態(tài)能耗決定。為了簡化能耗模型，本文在實驗中僅考慮資源動態(tài)能耗部分。動態(tài)功耗Pdynamic定義為：

其中，K為與動態(tài)功耗相關的常量因子，取決于設備性能，vj,s為處理器 pj在等級s時間的供電電壓，fs為與電壓vj,s對應的頻率?？偰芎目啥x為：

其中，ti,j為任務ni在資源 pj上的執(zhí)行時間，v(i,pj,s)表示任務ni被調度至電壓等級為s的資源 pj上，fpj,s表示電壓等級s時資源pj的頻率。由于供電電壓和頻率在處理器空閑時間內不能調整至零，此時電壓為最低狀態(tài)vlowest，可節(jié)省能耗。所有可用資源在空閑時間內的能耗定義為：

其中，vjlowest和 fjlowest分別為資源 pj在最低電壓時的供電電壓和頻率，tjidle為 pj的空閑時間。

綜上，執(zhí)行DAG任務的總能耗定義為：

3 算法設計

本章設計調度長度makespan與能耗同步最小化的任務調度算法CWEES，算法包括三個階段：初始任務映射階段、處理器資源合并階段和任務松馳階段。為了降低處理器資源的使用數(shù)量，必須選擇合適的時間槽部署低載處理器上的任務，然后，調度就緒任務至具有DVFS功能的處理器上，實現(xiàn)降低能耗的目標。CWEES算法偽代碼如下：

Input：G(N,E)，resource setP

Output：scheduling solution π：G(N,E)→ P

1.MS_computing（）using Al.2

2.Processors_Merging（）using Al.3

3.T_slacking（）using Al.4

4.return the assignment of tasks to lower voltage/frequency processors

算法說明：CWEES算法總體包括三步，即步驟1調用子算法2通過HEFT計算初始makespan，步驟2調用子算法3進行資源合并，步驟3調用子算法4進行任務松馳，最后在步驟5返回任務調度方案。

3.1 初始任務映射階段

該階段需要按照任務自底向上分級ranku值的降序排列獲得所有任務的優(yōu)先級，ranku值的獲取從任務DAG的出口任務自底向上向入口任務進行計算，如公式（4）所示。該過程中，首先需要在不違背任務間的順序依賴約束條件下產生一個初始的任務排序，然后，利用HEFT算法計算排序中最后一個任務的初始makespan MS，最后，基于MS，根據用戶給定的一個擴展因子α,α≥0，計算所有任務的全局截止時間D，表示為：

本文目標是在截止時間D內盡可能降低任務執(zhí)行能耗，并完成所有任務。算法2 MS_Computing（）偽代碼如下：

Input：G(N,E)，resource setP and α

Output：MSand deadlineD

1.computeranku(ni)of all tasks

2.schedule tasks to all availible resource by HEFT

3.computeMSusing Eq.（9）

4.computeDusing Eq.（14）

5.returnMSandD

算法說明：步驟1通過自底向上方式從出口任務遍歷DAG的方式計算所有任務分級值，步驟2利用HEFT將任務調度至所有可用資源上，步驟3利用式（9）計算機 MS，步驟4利用式（14）計算截止時間D，最后在步驟5返回MS和D。

3.2 處理器資源合并階段

該階段過程如算法3所示。首先，計算每個開啟狀態(tài)處理器的分配任務數(shù)量，然后基于rankm值，根據{p1,p2,…,pn}對處理器進行降序排列。如果兩個不同處理器資源的rankm值相等，則擁有更小能量效率 peu的處理器被放置于處理器排序的前列。 peu的計算方法如下：

其中，pjmax表示處理器 j的最大功耗，pjidle表示處理器j空閑時的功耗。算法3 Processors_Merging（）偽代碼如下：

Input：G(N,E)、P 、ranking value、MSandD

Output：best turn-on processors list

1.initializeMS′=MS ，merge processors until the scheduling length is larger than D and initialize resource order

2.initializeranki=0for each i

3.whileMS′≤D

4. compute the number of tasks each turn-on processor has been assigned asrankm

5. computetp_j+=wi,j,rankj++for every iand every j

6. compute the energy efficiency for processorpjeu

7. assume peuis smaller then rankmis smaller

8. sort{p1,p2,…,pk-1}in descending order ofrankm

9. setk as the number of processors have been assigned tasks and schedule tasks in {p1,p2,…,pk-1} by HEFT and updateMS

10. ifMS′≤D

11. turn off processorpkin P

12. P′=P-{pk},k=k-1,p=k,MS′=MS

13. end if

14.end while

15.return P′

算法說明：步驟1首先進行初始調度長度設置，并合并資源直到調度長度大于D，同時進行資源序列的初始化，步驟2初始化任務的分級值為0，若MS′≤D，循環(huán)執(zhí)行步驟4～13。步驟4先計算每個已開啟處理器上分配的任務數(shù)量，步驟5計算每個任務在每個可用資源上的執(zhí)行時間和對應的資源的rankm值，步驟6計算對應處理器資源的能量效率為：

如果 peu更小時處理器rankm也較低，則在步驟8根據rankm降序排列處理器{p1,p2,…,pk-1}，步驟9先設置k為已分配任務的處理器數(shù)量，然后基于HEFT執(zhí)行{p1,p2,…,pk-1}上的任務列表并更新MS值，步驟10判斷當前調度長度與D的關系，若不大于，則在步驟11中關閉未利用處理器資源，并更新相關參數(shù)（步驟12）。最后，在步驟15返回有效的執(zhí)行處理器資源集合。

在前面k-1個處理器上重復該算法進行任務調度直到總調度長度大于D,k為在第一階段中初始分配任務時的處理器數(shù)量。完成一次循環(huán)后，如果調度長度仍不大于D，則關閉未分配任務的處理器，且k值減1。然后，將最后的調度結果存儲為最終的處理器選擇，并標記活躍處理器為集合P′。完成以上步驟后，為了處理給定任務組的工作流，保留相對高效的處理器以降低能耗浪費。

3.3 任務松馳階段

該階段中，空閑時間槽可被松馳并在不違背任務順序約束的同時利用DVFS技術進行重分配。如算法4所示，對于一個任務，允許的最遲完成時間LFT可計算為：

其中，

表示任務ni的直接后繼任務集，tj為任務的執(zhí)行時間。任務ni允許的松馳時間可計算為：

接下來需要降低和優(yōu)化任務ni的執(zhí)行時鐘頻率。首先，選擇擁有最大LFT的任務ni，如果Slack(ni)＞0,將任務ni的EST與其相同處理器上的前一任務的LFT進行比較。如果LFT(ni)＞EST(ni)，則表明兩個任務間擁有松馳時間間隔，重復該步驟直到找到與后續(xù)任務nm-1沒有松馳時間間隔的任務nm為止。利用式（19）計算處理器 pj上任務ni至nm的總執(zhí)行時間為：

利用式（20）計算處理器 pj上從任務ni至nm的總空閑時間：

然后，計算對于任務ni的最小運行頻率為：

通過比較與處理器pj的電壓/頻率等級集合，選擇與任務ni的實際運行頻率最接近且大于的fpj,s。然后，設置實際運行頻率為 fni,pj=fpj,s，并根據公式（22）更新ni的執(zhí)行時間為：

基于以上過程，處理器 pj上任務ni的執(zhí)行時槽可在[LFT(ni)-LFT(ni)]間改變。如此，在完成頻率擴展后，可計算任務ni的具體調度時間，并更新nx與其前驅的LFT。重復該過程直到所有任務被優(yōu)化調度。算法4 T_Slacking（）偽代碼如下：

Input：EST 、execution time of tasks、MS′andD

Output：execution tasks list with best voltage/frequencey level

1.computeLFT andSlack(ni)for every task

2.while exit un-optimal tasks do

3. ifSlack(ni)for task niexits

4. select the task niwith the biggestLFT and compute the idealfor taskni

5. pick outactual operation frequency fni,pj

6. updatefrequency between fpjmaxand fni,pjand the execution time ofnito

7.allocatetimeslotfornito[LFT(ni)-LFT(ni)]

8. update LFT of all predecessor task for niand LFT ofnxwhich be executed beforenion pj

9. end if

10.end while

11.return execution tasks list

算法說明：步驟1計算每個任務的LFT和松馳時間Slack(ni)，步驟2～10對每個非最優(yōu)任務作循環(huán)操作，首先在步驟3判斷當前任務是否存在松馳時間，若存在，則執(zhí)行步驟4～8。步驟4選擇擁有最長LFT的任務ni并計算其理想運行頻率，步驟5選擇任務的實際運行頻率，步驟6在[fpjmax,fni,pj]間更新任務的執(zhí)行頻率并更新ni的執(zhí)行時間為，步驟7為ni分配時槽為[LFT(ni)-LFT(n)]，步驟8更新n的所有前驅任務的LFT并ii更新處理器 pj上ni的前一任務nx的LFT。若不存在非最優(yōu)任務，則最后在步驟11返回任務的執(zhí)行序列。

CWEES算法在維持任務調度所要求的截止時間性能的同時，可以降低任務執(zhí)行總能耗，其主要思想可總結為：首先優(yōu)化處理器的使用數(shù)量，重新分配輕載處理器上的任務至其他資源上，實現(xiàn)對運行處理器數(shù)量的降低。并充分利用處理器上任務執(zhí)行間的剩余空閑時槽，利用DVFS技術降低處理器的電壓和時鐘頻率，有效擴展任務執(zhí)行時間，降低處理器運行能耗。

3.4 算例說明

本節(jié)利用一個算例說明CWEES算法的實現(xiàn)思路。算例設置5個具有DVFS功能的同異處理器資源，運行時的供電電壓等級為{1.2 V，1.1 V，1.0 V，0.9 V，0.8 V，0.7 V}，對應的運行頻率等級為{1.0 GHz，0.8 GHz，0.6 GHz，0.5 GHz，0.4 GHz，0.3 GHz}。

首先，根據任務的自底向上分級值對任務進行降序排列，任務DAG結構如圖2所法。表1給出了10個任務在處理器上的執(zhí)行代價。為了簡化問題，假設所有處理器的性能是相同的，即同一任務在所有處理器上的擁有相同的執(zhí)行時間。

圖2 工作流DAG任務示例

表1 任務執(zhí)行代價

表2給出了利用公式（4）計算的任務自底向下分級值。通過降序排列，可得到任務序列為：{n0,n2,n1,n5,n4,n6,n3,n8,n7,n9}。

表2 任務分級值rank

圖3（a）給出HEFT算法的初始調度結果，圖3（b）給出了未使用處理器合并的EES算法的初始調度結果。利用算法3的處理器合并，算法可以決定開啟的處理器。圖3（c）給出本文算法進行處理器合并的結果。在該算例中，處理器 p3和 p2在不違背順序約束的前提下被輪流開啟，且并未增加調度長度。處理器 p2和 p3上的任務4和任務6均被調度到處理器 p4。如圖3（d）所示，這些任務的執(zhí)行時間均在更低的電壓等級下得到松馳，以降低能耗，這即為CWEES算法得到的最終調度結果。為了簡化分析，該算例中設置了5個同質處理器，且α=0，即D=MS。

圖3（a）中，HEFT的 MS=80，同時可計算出處理器的繁忙時間=92，空閑時間=308，故資源利用率僅為23%，總能耗Etotal=177.756，包括132.48的動態(tài)能耗和45.276的空閑能耗。同樣，EES和CWEES的資源利用率分別為34.875%和54.875%，能效分別為22.6%和29.5%。該算例表明結合DVFS的處理器合并機制可以降低能耗，同時維持執(zhí)行性能需求。

4 仿真實驗

4.1 實驗環(huán)境與性能指標

本節(jié)評估所提算法性能，選擇算例中啟發(fā)式算法HEFT[4]和EES[12]作為比較基準算法。HEFT未考慮能耗代價，執(zhí)行效率較高。EES是基于DVFS的加強能效調度算法，可降低非關鍵任務的執(zhí)行頻率，將任務重分配至能耗更低的合適時間槽中。選擇CloudSim[17]作為工作流調度仿真平臺，該平臺可用于仿真云基礎設施和服務，提供可重復和可控制的實驗環(huán)境。

考慮的性能指標包括以下四種：

（1）能耗效率ECR。表示DAG任務執(zhí)行的總能耗與關鍵路徑上最快完成處理器上的任務執(zhí)行能耗之比，計算方法為：

（2）資源利用率。表示為使用資源與全部資源的比例。

（3）平均執(zhí)行時間。表示得到給定DAG任務下的調度結果的算法運行時間。

（4）能量節(jié)省效率。該指標測量算法在基準能耗Ebase基礎上能耗效率。利用HEFT的能耗作為基準能耗Ebase，當處理器空閑時，算法調整至最低頻率等級。

4.2 實驗配置

為了使用實驗環(huán)境配置更具代表性，實驗模擬仿真了四組不同的具有DVFS能力的異構處理器資源，其類型和電壓/頻率等各項參數(shù)的取值均是實際環(huán)境中AMD Athlon-64、Intel Pentium M、AMD Opteron 2218和ADM Turion MT-34等處理器的真實參數(shù)，具體如表3所示。實驗中以隨機的方式產生工作流DAG任務模型，同時，為了負載狀況更具一般性，實驗中以多種規(guī)模的任務負載和任務組成進行仿真測試，具體為：將隨機DAG任務數(shù)量分布于{20，40，80，160，320，400}中，而任務中的通信/計算類任務的比率CCR為{0.1，0.5，1.0，2.0，5.0}，可用處理器資源的數(shù)量集為2至32，以指數(shù)2進行遞增。

圖3 算法調度結果示意圖

表3 資源參數(shù)

4.3 實驗結果

實驗1觀察任務數(shù)量對算法性能的影響。圖4（a）是平均資源利用率情況。明顯地，EES和CWEES雖然在不同的電壓/頻率等級均可提高資源利用率，但CWEES表現(xiàn)更好，其最大資源利用率達到80%。圖4（b）中是平均ECR情況，根據定義，ECR越小，算法性能越好。DE在能耗節(jié)省上擁有更大的優(yōu)勢，其ECR值的正比例下降比較EES更加穩(wěn)定，這是EES僅采用了DVFS節(jié)能技術，沒有利用資源合并。圖4（c）是任務集的平均執(zhí)行時間，其值為總執(zhí)行時間除以任務數(shù)量。隨著任務增加，三種算法的平均執(zhí)行時間均趨于降低。這是由于隨著任務增加，隨機DAG規(guī)模也將增加，HEFT中的單個任務的平均執(zhí)行時間逐漸趨于平衡，EES和CWEES的平均時間高于HEFT，雖然兩種算法需要節(jié)省能耗，犧牲了部分執(zhí)行效率。CWEES在利用DVFS前進行處理器合并的方式得到最優(yōu)資源數(shù)量，降低了空閑能耗，且其平均任務執(zhí)行時間低于EES。EES僅側重于能耗優(yōu)化，忽略了其他性能條件的影響。圖4（d）是算法在HEFT上得到的能量節(jié)省效率指標?？梢钥闯?，CWEES較EES能效更高，這源于其資源合并機制。而隨著任務數(shù)的增加，CWEES的性能變得更好。但當任務數(shù)量達到某門限值時，該指標會降低。平均來說，CWEES較EES可節(jié)省7%左右能耗。

實驗2觀察處理器數(shù)量對算法性能的影響。處理器數(shù)量在[2，32]間，任務數(shù)量為400。圖5（a）是處理器數(shù)量對資源利用率的影響?？梢钥闯觯Y源數(shù)量變化對HEFT影響不大，由于HEFT僅考慮調度時間最小。隨著資源數(shù)量增加，執(zhí)行時間會降低但更多資源會保持空閑而浪費。由于利用了DVFS的任務松馳機制，EES和CWEES優(yōu)于HEFT。隨著資源數(shù)量增加，CWEES的優(yōu)勢更為明顯，由于此時處理器合并將帶來更大的性能提升。圖5（b）是平均ECR?？梢钥闯?，資源數(shù)為8之前，ECR值增加緩慢，由于此時總能耗增加并不多。相對而言，CWEES的ECR指標增加最為緩慢，由于其能耗最低。圖5（c）是平均執(zhí)行時間。明顯地，平均執(zhí)行時間會隨資源量的增加而降低。同樣地，資源數(shù)為8之前，執(zhí)行時間下降更快，之后則趨于平穩(wěn)。EES和CWEES高于HEFT，由于前兩者針對能耗節(jié)省，不同程度地會犧牲單個任務的執(zhí)行時間。而EES僅側重于降低能耗，CWEES則利用DVFS技術優(yōu)化了資源使用數(shù)量。因此，CWEES的平均執(zhí)行時間低于EES。圖5（d）是能量節(jié)省效率情況?？梢钥闯觯Y源數(shù)小于8時，該指標相對更小。隨著資源量的增加，該指標明顯升高，且CWEES是優(yōu)于EES的。

圖4 任務數(shù)量對算法性能的影響

圖5 處理器數(shù)率量對算法性能的影響

圖6 擴展因子α對算法性能的影響

實驗3觀察擴展因子α對算法性能的影響。實驗設置400個任務和48個可用處理器，每種類型12個。圖6（a）是資源利用率情況。在初始情況下，EES和CWEES的資源利用率會隨著擴展因子的增加而增加，而HEFT基本保持不變，該因子對HEFT不產生影響，由于HEFT僅關注于優(yōu)化任務的最早完成時間。對于EES，α從15%增加至90%時，利用率從53%增加至70%，而當α進一步增加后，利用率將下降，由于此時任務的松馳時間達到了極限值。相比而言，CWEES的利用率提升更快，而這是以犧牲部分任務執(zhí)行時間為代價的。圖6（b）顯示擴展因子對的HEFT的ECR沒有影響。對于EES和DE，α∈[15%,60%]時，ECR是降低的，而CWEES的下降速率快于EES，由于CWEES在進行頻率擴展前進行了處理器合并。在ECR的最小值方面，CWEES也是低于EES的，這源于空閑時槽被重復利用的結果。圖6（c）的平均執(zhí)行時間上，EES和CWEES的執(zhí)行時間會隨著擴展因子遞增，CWEES更低，接近于HEFT。主要原因是EES為降低能耗犧牲了過多的效率，而CWEES在執(zhí)行效率與能效方面更加的均衡。圖6（d）觀察擴展因子與能量節(jié)省效率間的關系。可以看出，EES和CWEES表現(xiàn)更好，且CWEES的能效較EES增加更快。但到達各自的門限值后，能效開始下降，這是由于處理器合并和松馳時間是受限的。

圖7 通信計算比率CCR對算法性能的影響

實驗4觀察通信計算比率CCR對算法性能的影響。CCR反映的是工作流任務的組成。圖7（a）是資源利用率情況?？梢钥闯?，CWEES在滿足截止時間的同時可以達到最高的資源利用率，當CCR=2時，CWEES的利用率達到80%。對于EES，CCR=0.5時，資源利用率最高為60%，HEFT為58%。原因可解釋為EES和HEFT適應于計算密集型應用，由于此時CCR較低而得到了最高的利用率。而CWEES則同時適應于計算密集型和通信密集型應用任務。圖7（b）是ECR情況。圖中顯示，CCR=0.5時，HEFT和EES擁有最低的ECR，分別為6.9和4.1。CWEES在CCR=2時擁有最高的ECR=4。HEFT，EES和CWEES中CWEES性能更高。而比較EES，CWEES中CCR對ECR具有更小的影響。該結果表明HEFT和EES更適用于計算密集型應用，而CWEES適應于兩種類型的應用。圖7（c）是平均執(zhí)行時間情況。HEFT仍然是在三種算法中在執(zhí)行效率上最好的，由于其僅關注于優(yōu)化執(zhí)行時間。而CWEES的平均執(zhí)行時間小于EES，這源于CWEES在利用DVFS之前進行了資源合并。圖7（d）是能量節(jié)省效率情況?？梢钥闯?，CCR=0.5時，EES能效最高，CCR=2，CWEES能效最高，總體來說，算法的平均能效約44%，而CWEES比EES能效更高。

5 結語

為了解決截止時間約束下工作流調度能耗最小化問題，提出了一種能效調度優(yōu)化算法。算法將能效優(yōu)化調度劃分為三個階段求解：初始任務映射、處理器資源合并和任務松馳。通過三階段式求解，算法可以得到最優(yōu)工作流調度方案，在保證資源利用率和滿足時間約束前提下，極大降低執(zhí)行工作流總能耗。實驗結果證明算法在隨機工作流結構中測試是有效可行的。進一步研究將關注于除了時間外的其他維度的QoS約束，如費用、可靠性約束等，求解多約束下的工作流調度能效算法。

：

[1]Smanchat S，Viriyapant K.Taxonomies of workflow scheduling problem and techniques in the cloud[J].Future Generation Computer Systems，2015，52（3）：1-12.

[2]Liu L，Zhang M，Lin Y，et al.A survey on workflow managementand scheduling in cloud computing[C]//14th IEEE/ACM International Symposium on Cluster，Cloud and Grid Computing.USA：IEEE Press，2014：837-846.

[3]Arroba P，Risco-Mart J L，Zapater M，et al.Server power modeling for run-time energy optimization of cloud computing facilities[J].Energy Procedia，20l4，62：401-410.

[4]Topcuoglu H，Hariri S，Wu M Y.Performance-effective and low-complexity task scheduling for heterogeneous computing[J].IEEE Transactions Parallel Distributed Systems，2012，13（3）：260-274.

[5]Selvi S，Manimegalai D.Task scheduling using two-phase variable neighborhood search algorithm on heterogeneous computing and grid environments[J].Arabian Journal for Science and Engineering，2015，40（3）：817-844.

[6]Lee Y C，Han H，Zomaya A Y，et al.Resource-efficient workflow scheduling in clouds[J].Knowledge-Based Systems，2015，80（C）：153-162.

[7]Abudhagir U S，Shanmugavel S.A novel dynamic reliability optimized resource scheduling algorithm for grid computing system[J].Arabian Journal for Science and Engineering，2014，39（10）：7087-7096.

[8]Arabnejad H，Barbosa J G.A Budget constrained scheduling algorithm for workflow applications[J].Journal of Grid Computing，2014，12（4）：665-679.

[9]Wang Y，Sheng M，Wang X，et al.Energy-optimal partial computation offloading using dynamic voltage scaling[C]//IEEE International Conference on Communication Workshop.IEEE，2015：2695-2700.

[10]Liang A，Pang Y.A Novel，Energy-aware task duplicationbased scheduling algorithm of parallel Tasks on Clusters[J].Mathematicaland Computational Application，2016，22（1）：2-9.

[11]Baskiyar S，Abdel-Kader R.Energy aware DAG scheduling on heterogeneous systems[J].Cluster Computing，2013，13（4）：373-383.

[12]Huang Q，Su S，Li J，et al.Enhanced energy-efficient scheduling for parallel applications in cloud[C]//Ieee/acm International Symposium on Cluster，Cloud and Grid Computing.IEEE，2012：781-786.

[13]景維鵬，吳智博，劉宏偉，等.多DAG工作流在云計算環(huán)境下的可靠性調度方法[J].西安電子科技大學學報：自然科學版，2016，43（2）：83-88.

[14]王潤平，陳旺虎，段菊.一種科學工作流的云數(shù)據布局與任務調度策略[J].計算機仿真，2015，32（3）：421-426.

[15]王巖，汪晉寬，王翠榮，等.QoS約束的云工作流調度算法[J].東北大學學報：自然科學版，2014，35（7）：939-943.

[16]楊玉麗，彭新光，黃名選，等.基于離散粒子群優(yōu)化的云工作流調度[J].計算機應用研究，2014，31（12）：3677-3681.

[17]Goyal T，Singh A，Agrawal A.Cloudsim：simulator for cloud computing infrastructure and modeling[J].Procedia Engineering，2012，38（4）：3566-3572.