王國(guó)豪，李慶華 ，劉安豐

1.麗水學(xué)院 工學(xué)院，浙江 麗水 323000

2.中南大學(xué) 信息科學(xué)與工程學(xué)院，長(zhǎng)沙 410083

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

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

1 相關(guān)工作

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

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

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

2 系統(tǒng)模型

2.1 資源模型

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

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

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

工作流中，無(wú)前驅(qū)的任務(wù)稱為DAG入口任務(wù)（如圖1中的nentry），無(wú)后繼的任務(wù)稱為DAG出口任務(wù)（如圖1中的 nexit）。

圖1 工作流任務(wù)DAG示例

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

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

則任務(wù)ni與nj間的平均通信代價(jià)可定義為：

其中，ATR為資源間的平均傳輸速率，ATC為通信啟動(dòng)的平均時(shí)間代價(jià)。在進(jìn)行任務(wù)調(diào)度時(shí)，任務(wù)按自底向下分級(jí)值的形式對(duì)任務(wù)進(jìn)行優(yōu)先級(jí)排序，任務(wù)ni的分級(jí)值以遞歸方式定義為：

令EST(ni,pj)為調(diào)度至資源 pj的任務(wù)ni的最早開(kāi)始時(shí)間，EFT(ni,pj)為調(diào)度至資源 pj的任務(wù)ni的最早完成時(shí)間。對(duì)于入口任務(wù)nentry，其EST計(jì)算為：

對(duì)于任務(wù)DAG模型中的其他任務(wù)（從入口任務(wù)開(kāi)始），其EST和EFT的計(jì)算方法為：

其中，avil[pj]為資源 pj上最后調(diào)度的任務(wù)nk的最早完成時(shí)間，pred(ni)為任務(wù)ni的直接前驅(qū)集：

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

DAG中的所有任務(wù)調(diào)度后，調(diào)度長(zhǎng)度為出口任務(wù)nexit的實(shí)際完成時(shí)間。定義調(diào)度任務(wù)的最長(zhǎng)路徑為關(guān)鍵路徑CP，最遲完成任務(wù)的完成時(shí)間為調(diào)度長(zhǎng)度或makespan。如果出口任務(wù)多于一個(gè)，則最遲任務(wù)的makespan可定義為：

2.3 能耗模型

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

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

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

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

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

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

本章設(shè)計(jì)調(diào)度長(zhǎng)度makespan與能耗同步最小化的任務(wù)調(diào)度算法CWEES，算法包括三個(gè)階段：初始任務(wù)映射階段、處理器資源合并階段和任務(wù)松馳階段。為了降低處理器資源的使用數(shù)量，必須選擇合適的時(shí)間槽部署低載處理器上的任務(wù)，然后，調(diào)度就緒任務(wù)至具有DVFS功能的處理器上，實(shí)現(xiàn)降低能耗的目標(biāo)。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

算法說(shuō)明：CWEES算法總體包括三步，即步驟1調(diào)用子算法2通過(guò)HEFT計(jì)算初始makespan，步驟2調(diào)用子算法3進(jìn)行資源合并，步驟3調(diào)用子算法4進(jìn)行任務(wù)松馳，最后在步驟5返回任務(wù)調(diào)度方案。

3.1 初始任務(wù)映射階段

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

本文目標(biāo)是在截止時(shí)間D內(nèi)盡可能降低任務(wù)執(zhí)行能耗，并完成所有任務(wù)。算法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

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

3.2 處理器資源合并階段

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

其中，pjmax表示處理器 j的最大功耗，pjidle表示處理器j空閑時(shí)的功耗。算法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′

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

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

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

3.3 任務(wù)松馳階段

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

其中，

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

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

利用式（20）計(jì)算處理器 pj上從任務(wù)ni至nm的總空閑時(shí)間：

然后，計(jì)算對(duì)于任務(wù)ni的最小運(yùn)行頻率為：

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

基于以上過(guò)程，處理器 pj上任務(wù)ni的執(zhí)行時(shí)槽可在[LFT(ni)-LFT(ni)]間改變。如此，在完成頻率擴(kuò)展后，可計(jì)算任務(wù)ni的具體調(diào)度時(shí)間，并更新nx與其前驅(qū)的LFT。重復(fù)該過(guò)程直到所有任務(wù)被優(yōu)化調(diào)度。算法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

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

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

3.4 算例說(shuō)明

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

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

圖2 工作流DAG任務(wù)示例

表1 任務(wù)執(zhí)行代價(jià)

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

表2 任務(wù)分級(jí)值rank

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

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

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

4.1 實(shí)驗(yàn)環(huán)境與性能指標(biāo)

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

考慮的性能指標(biāo)包括以下四種：

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

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

（3）平均執(zhí)行時(shí)間。表示得到給定DAG任務(wù)下的調(diào)度結(jié)果的算法運(yùn)行時(shí)間。

（4）能量節(jié)省效率。該指標(biāo)測(cè)量算法在基準(zhǔn)能耗Ebase基礎(chǔ)上能耗效率。利用HEFT的能耗作為基準(zhǔn)能耗Ebase，當(dāng)處理器空閑時(shí)，算法調(diào)整至最低頻率等級(jí)。

4.2 實(shí)驗(yàn)配置

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

圖3 算法調(diào)度結(jié)果示意圖

表3 資源參數(shù)

4.3 實(shí)驗(yàn)結(jié)果

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

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

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

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

圖6 擴(kuò)展因子α對(duì)算法性能的影響

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

圖7 通信計(jì)算比率CCR對(duì)算法性能的影響

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

5 結(jié)語(yǔ)

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

：

[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工作流在云計(jì)算環(huán)境下的可靠性調(diào)度方法[J].西安電子科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2016，43（2）：83-88.

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

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

[16]楊玉麗，彭新光，黃名選，等.基于離散粒子群優(yōu)化的云工作流調(diào)度[J].計(jì)算機(jī)應(yīng)用研究，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.