蔣軍強(qiáng)　林亞平　謝國琪　張世文

1(湖南大學(xué)信息科學(xué)與工程學(xué)院　長沙　410082)2　　　(可信系統(tǒng)與網(wǎng)絡(luò)湖南省重點實驗室(湖南大學(xué))　長沙　410082)

?

時間約束的異構(gòu)分布式系統(tǒng)工作流能耗優(yōu)化算法

蔣軍強(qiáng)1,2林亞平1,2謝國琪1張世文1,2

1(湖南大學(xué)信息科學(xué)與工程學(xué)院長沙410082)2(可信系統(tǒng)與網(wǎng)絡(luò)湖南省重點實驗室(湖南大學(xué))長沙410082)

(jjq@hnu.edu.cn)

摘要針對現(xiàn)有異構(gòu)分布式可變電壓?頻率(dynamic voltage?frequency scaling, DVFS)計算系統(tǒng)下具有時間約束的工作流能耗優(yōu)化算法易陷入局部最優(yōu)的問題，提出了一種新的全局能耗優(yōu)化算法：反向蛙跳全局能耗感知算法,該算法利用工作流下界完成時間和約束時間之間存在的盈余，逐步從約束時間開始，以不同的躍度值向下界完成時間反向蛙跳，在此過程中基于局部最優(yōu)解的判斷不斷調(diào)整躍度值直至蛙跳終點，同時保留該過程中工作流滿足時間約束且任務(wù)運(yùn)行能耗最小的調(diào)度序列.在此基礎(chǔ)上利用處理器松弛時間回收技術(shù)，在保持任務(wù)間依賴關(guān)系和滿足工作流時間約束的前提下，調(diào)整處理器運(yùn)行電壓?頻率至更低的合適級別上，從而進(jìn)一步降低工作流運(yùn)行能耗.實驗表明：該算法能顯著降低工作流整體能耗，節(jié)能優(yōu)勢明顯.

關(guān)鍵詞異構(gòu)分布式系統(tǒng)；能耗優(yōu)化；時間約束；工作流；松弛時間回收

自世界上第1臺電子計算機(jī)“ENIAC”誕生至今，計算機(jī)已進(jìn)化成各種形狀、尺寸和規(guī)模的機(jī)器，成為人們?nèi)粘Ｉ钪须S處可見的物品(如手機(jī)).與此相對應(yīng)，計算系統(tǒng)也由最初的單一同構(gòu)式發(fā)展到今天的異構(gòu)分布式[1]，其體系結(jié)構(gòu)表現(xiàn)越來越靈活.異構(gòu)分布式計算系統(tǒng)是將物理上分散的多臺計算機(jī)通過通信網(wǎng)絡(luò)相互聯(lián)結(jié)組成邏輯上集中的系統(tǒng)對外提供計算服務(wù)，系統(tǒng)中各計算機(jī)硬件、軟件以及組成該系統(tǒng)的網(wǎng)絡(luò)間的通信協(xié)議不盡相同[2].近年來，新的異構(gòu)分布式計算模式和技術(shù)不斷被提出，如對等網(wǎng)絡(luò)(peer-to-peer computing)[3]、網(wǎng)格計算(grid computing)[4]和云計算(cloud computing)等[5].尤其是后者的提出，使得異構(gòu)分布式計算系統(tǒng)的發(fā)展呈現(xiàn)風(fēng)起云涌之勢.時至今日，云計算已經(jīng)成為一種成熟的技術(shù)被各大IT公司和科研機(jī)構(gòu)所廣泛采用，應(yīng)用在大數(shù)據(jù)處理、科學(xué)研究分析、復(fù)雜工作流處理等多個場景.同時，各大IT公司紛紛推出自己的云計算產(chǎn)品對公眾提供服務(wù)，如Amazon的EC2[6]、Google的App Engine[7].這些產(chǎn)品使用Hadoop[8],Spark[9]等軟件，組織起數(shù)量眾多、位置分散、性能各異的物理計算節(jié)點來構(gòu)成龐大的計算資源平臺，因此，云計算是一種典型的異構(gòu)分布式計算系統(tǒng).此外，伴隨信息爆炸式增長而產(chǎn)生的大數(shù)據(jù)[10]，其存儲中心通常意義上也屬于異構(gòu)分布式計算系統(tǒng)[11-12].

龐大的系統(tǒng)必然對應(yīng)著巨大的能量需求.有研究表明：一個擁有5萬個計算節(jié)點的數(shù)據(jù)中心一年所耗費的電量約為1×108kW·h，這相當(dāng)于一個10萬人口規(guī)模城市一年的耗電量[13].谷歌數(shù)據(jù)中心一年的耗電量高達(dá)1.12×109kW·h，隨之而來是其每年高達(dá)6 700萬美元的電費支出[12].此外，大型系統(tǒng)必不可少的輔助設(shè)施(如風(fēng)冷系統(tǒng))使得這些系統(tǒng)耗能越發(fā)巨大.高耗能也意味著大量的二氧化碳排放，有文獻(xiàn)指出，在美國每消耗1度電平均產(chǎn)生500 g的二氧化碳排放[14]，進(jìn)一步加劇了地球的溫室效應(yīng)以及對環(huán)境的破壞，在倡導(dǎo)“綠色計算”的今天，這無疑受人詬病.另外，高耗能通常與高電壓對應(yīng)，高電壓更容易使電子元器件產(chǎn)生高溫，如果計算節(jié)點長期處于高溫狀態(tài)下，無形中增加了計算節(jié)點出現(xiàn)潛在故障的幾率[15].因此，考慮異構(gòu)分布式計算系統(tǒng)下的能耗問題具有重要的應(yīng)用意義.

1相關(guān)工作

科學(xué)研究、電子商務(wù)等領(lǐng)域的許多應(yīng)用均可看做是工作流——一種面向過程建模和管理的核心技術(shù)，?？捎糜邢驘o環(huán)圖(directed acyclic graph, DAG)表示[20-21].用戶將工作流提交到計算系統(tǒng)后，一般會有附加的服務(wù)質(zhì)量(quality of service, QoS)要求，如費用、執(zhí)行時間、可靠性等.用戶期望工作流在執(zhí)行時滿足QoS要求，因此，基于QoS的工作流調(diào)度問題就是在所有滿足QoS的調(diào)度中選擇最合適的調(diào)度執(zhí)行.

基于QoS的調(diào)度問題通常情況下是一個NP-難問題，已有許多文獻(xiàn)提出相應(yīng)的優(yōu)化算法[22-29].時間約束作為常見的QoS要求，出現(xiàn)在諸多應(yīng)用場景中，如實時天氣預(yù)報系統(tǒng)、在線視頻點播系統(tǒng)等.同樣地，能耗優(yōu)化近年來越來越受到工業(yè)界和學(xué)術(shù)界的關(guān)注，尤其是針對耗能巨大的大型異構(gòu)計算系統(tǒng)譬如云計算平臺和數(shù)據(jù)中心.其中既有通過合理措施降低自身運(yùn)行能耗[11,14,24]，也有利用可再生能源實現(xiàn)碳減排[12]，對綠色計算的發(fā)展起到了非常積極的促進(jìn)作用.進(jìn)一步地，針對具有先序約束的DAG工作流調(diào)度中的時間和能耗2個頗受用戶關(guān)注的問題，在異構(gòu)分布式可變電壓頻率計算系統(tǒng)下，Lee等人[25]提出ECS算法，該算法利用目標(biāo)函數(shù)來權(quán)衡能耗優(yōu)化與執(zhí)行時間之間的關(guān)系，從中選取函數(shù)值為最大正數(shù)值的處理器與電壓頻率組來執(zhí)行任務(wù)，本文同時也顯要地指出該算法不適合具有時間約束的實時系統(tǒng).Li[26]將這個多目標(biāo)優(yōu)化問題細(xì)分為3個問題：能耗約束下的工作流最小完成時間問題、時間約束下的能耗最小問題以及二者的綜合，并提出了相應(yīng)的算法，但算法針對的是具有先序約束的串行工作流.Su等人[27-28]提出可利用部分最優(yōu)化松弛技術(shù)將處理器的松弛時間回收，進(jìn)而降低任務(wù)的運(yùn)行電壓達(dá)到節(jié)能的目的，但根據(jù)文中的描述該算法更適合線性可變電壓頻率處理器場景.Tang等人[29]則提出在原始調(diào)度基礎(chǔ)上逐步關(guān)閉利用率不高的計算節(jié)點，在剩余計算節(jié)點上重新執(zhí)行調(diào)度直至調(diào)度完成時間大于約束時間，再在此基礎(chǔ)上使用改進(jìn)的Su的方法進(jìn)一步降低系統(tǒng)整體運(yùn)行能耗，但在實際環(huán)境中直接關(guān)閉計算節(jié)點顯得不切實際.

本文以異構(gòu)分布式可變電壓計算系統(tǒng)下具有時間約束的DAG工作流調(diào)度能耗優(yōu)化問題作為研究對象.基于約束時間與下界完成時間之間的盈余，引入最小躍度值與最大躍度值概念，逐步從約束時間開始，以不同的躍度值向下界完成時間反向蛙跳，每次跳躍均可以形成一大一小2個盈余時間值，分別將此二值附加到各個任務(wù)，得到各個任務(wù)新的最早完成時間，在此新的時間內(nèi)各個任務(wù)按照優(yōu)先級對全局所有處理器和電壓頻率組進(jìn)行遍歷，選取使任務(wù)運(yùn)行能耗最小且對應(yīng)最早完成時間不大于新的最早完成時間的處理器和電壓頻率組，將其指派給該任務(wù)運(yùn)行，同時注意保持任務(wù)之間的依賴關(guān)系.2個不同的盈余時間產(chǎn)生2個滿足時間約束的有效調(diào)度，基于2個有效調(diào)度運(yùn)行能耗大小的比較結(jié)果，重新設(shè)定下一輪反向蛙跳的起點與躍度值，同時保留其中運(yùn)行能耗最小的調(diào)度為當(dāng)前全局最優(yōu)調(diào)度，如此循環(huán)反向跳躍直至蛙跳終點.在全局最優(yōu)調(diào)度基礎(chǔ)上利用處理器松弛時間回收技術(shù)，在保持任務(wù)間依賴關(guān)系和滿足工作流時間約束的前提下，調(diào)整處理器的運(yùn)行電壓頻率至更低的合適級別上，從而進(jìn)一步降低DAG工作流整體能耗，最后實驗結(jié)果表明算法節(jié)能優(yōu)勢明顯.

2模型及問題定義

2.1系統(tǒng)模型

系統(tǒng)包含k個異構(gòu)的處理器及計算節(jié)點，它們互聯(lián)組成計算節(jié)點集P，P={p1,p2,…,pk}，每個計算節(jié)點均部署成可變電壓頻率模式，即pk∈P可運(yùn)行在不同的供電電壓與時鐘頻率上.設(shè)電壓集為V，頻率集為F，當(dāng)處理器運(yùn)行在電壓vl∈V時它對應(yīng)的時鐘頻率為fl∈F.當(dāng)處理器空閑時，它運(yùn)行在最低電壓vmin上以節(jié)能，約定最低電壓不能為0，即vmin>0.鑒于頻率切換時間很小(10～150 μs)，一般不考慮電壓切換開銷[15,25,29].同時假設(shè)各計算節(jié)點以同樣的速率交換數(shù)據(jù)，即不存在通信競爭.計算節(jié)點執(zhí)行任務(wù)的同時可以同步收發(fā)數(shù)據(jù)[20,25].

2.2應(yīng)用模型

并行工作流一般可用有向無環(huán)圖DAG來表示[20-21].一個DAG由節(jié)點集N和邊集E構(gòu)成，G=(N,E,W,C)，其中，N由n個節(jié)點組成，每個節(jié)點表示工作流中的單個任務(wù)；E由e條有向邊組成，它表示任務(wù)之間的依賴關(guān)系，邊上的權(quán)值表示任務(wù)之間的通信開銷.邊(i,j)∈E表示任務(wù)nj在收到任務(wù)ni的處理結(jié)果之前不能啟動，ni稱為nj的直接前驅(qū)任務(wù)，nj稱為ni的直接后繼任務(wù)；沒有前驅(qū)任務(wù)的節(jié)點稱為入口任務(wù)nentry，沒有后繼任務(wù)的節(jié)點稱為出口任務(wù)nexit；pred(ni)表示任務(wù)ni的直接前驅(qū)任務(wù)集，succ(ni)表示任務(wù)ni的直接后繼任務(wù)集.

W是一個|N|×|P|(本文用|X|表示集合X的大小)的矩陣，wi,k表示任務(wù)ni在處理器pk上，以最高電壓頻率運(yùn)行時的計算開銷；表示任務(wù)ni的平均計算開銷，它等于任務(wù)ni在所有處理器上的計算開銷之和除以處理器個數(shù).C是一個|N|×|N| 的矩陣，ci,j表示ni到nj的通信開銷，如果ni與nj運(yùn)行在同一計算節(jié)點上，則它們之間的通信開銷為0.

HEFT[20]算法作為著名的單工作流靜態(tài)調(diào)度算法，以其合理的時間復(fù)雜度和高效的執(zhí)行效率，不但被許多研究者引用獲得學(xué)術(shù)界廣泛關(guān)注，同時也在網(wǎng)格計算框架ASKALON[30]中予以實現(xiàn)，其有效性與實用性得以證明.本文也利用它來處理工作流任務(wù)的具體調(diào)度問題.與文獻(xiàn)[25,27-29]類似，本文的調(diào)度模型為離線模型.

參照文獻(xiàn)[20]，給出任務(wù)ni在處理器pk上的最早啟動時間(earliest start time, EST)EST(ni,pk)、最早完成時間(earliest finish time, EFT)EFT(ni,pk)和實際執(zhí)行時間ti分別為

EST(ni,pk)=

(1)

EFT(ni,pk)=EST(ni,pk)+ti，

(2)

(3)

Tmakespan=AFT(nexit).

(4)

同樣，根據(jù)文獻(xiàn)[20]給出任務(wù)ni的向上排序值計算公式：

(5)

2.3能耗模型

根據(jù)文獻(xiàn)[25,27]，有能耗

P=ACV2f,

其中,A代表芯片晶體管的平均開關(guān)數(shù)量，C為有效電容，V為供電電壓，f為時鐘頻率.文獻(xiàn)[25]中，將AC視作常數(shù)，本文沿用這一設(shè)定.

(6)

其中，ti可由式(3)求出.相應(yīng)地，系統(tǒng)空載能耗的計算為

(7)

Etotal=Erun+Eidle.

(8)

2.4問題定義

本文要解決的問題是將工作流G中n個具有依賴關(guān)系的任務(wù)調(diào)度至k個異構(gòu)的計算節(jié)點上并行運(yùn)行，在滿足時間約束的前提下使得G的整體能耗最小，形式化為

min(Erun+Eidle)，

s.t.Tmakespan≤Tdeadline,

其中,Tmakespan為工作流G的完成時間；Tdeadline為約束時間，由用戶事先給出.同時，因降頻導(dǎo)致處理時間延長，進(jìn)而造成額外的能量消耗，不在本文討論范圍之內(nèi).

3算法描述及復(fù)雜性分析

3.1算法描述

在給出本文算法描述之前，先來看一個DAG調(diào)度模型.為了更好地理解該算法，此處假設(shè)任務(wù)在處理器上的執(zhí)行速度相同，詳細(xì)數(shù)值由表1給出，表2為處理器的電壓頻率組.DAG模型由圖1給出.

Table 1　Computation Cost

Table 2　Voltage and Frequency Pairs

表2　電壓頻率組

Table 2　Voltage and Frequency Pairs

Voltage∕VFrequency∕GHz1.751.001.400.891.200.800.900.67

Fig. 1　An example DAG.圖1　示例DAG

針對表1、表2和圖1設(shè)定，使用HEFT算法生成該DAG的原始調(diào)度，可以得到Tmakespan=80，Etotal=339，如圖2(a)所示.

Fig. 2　Scheduling list of example DAG.圖2　DAG調(diào)度圖

Fig. 3　Scheduling list after each task moderates to lower frequency.圖3　各任務(wù)降頻后的調(diào)度圖

雖然示例DAG十分簡單，但是它很清晰地表達(dá)了本文將要提出的算法的核心思想，即在原始調(diào)度的基礎(chǔ)上逐步以不同的盈余時間值ΔS′同時增大各個任務(wù)的執(zhí)行時間，之后在此基礎(chǔ)上重新調(diào)度任務(wù)直至ΔS′=ΔS.需要引起注意的是，本文算法在任務(wù)重新調(diào)度過程中解除對處理器的限制，即任務(wù)可以在所有處理器及其對應(yīng)的所有電壓頻率組上遍歷搜索，從全局找尋能耗最優(yōu)調(diào)度.

如何在盈余時間ΔS內(nèi)找到最節(jié)能又滿足時間約束的有效調(diào)度，最簡單的方法是從下界完成時間Tlowerbound即(原始調(diào)度完成時間)開始，每次以最小搜索粒度譬如Δs=0.01(假設(shè)系統(tǒng)要求保留2位小數(shù))遞進(jìn)累加，再在新生成的盈余時間ΔS′基礎(chǔ)上對系統(tǒng)中的所有計算節(jié)點進(jìn)行掃描，然后在m=ΔSΔs次遍歷中找出合乎要求的調(diào)度.很顯然，隨著盈余時間的增大以及系統(tǒng)精度要求的提高，該算法時間復(fù)雜度會越來越高.經(jīng)過大量的實驗分析，當(dāng)盈余時間根據(jù)系統(tǒng)精度要求以對應(yīng)的最小搜索粒度譬如Δs=0.01進(jìn)行遞增時，m次遍歷中存在大量的冗余調(diào)度.舉例來說，使用文獻(xiàn)[25]中的DAG設(shè)定，約束時間Tdeadline=95，在電壓頻率組V={(1.75,1.0),(1.40,0.8),(1.20,0.6),(0.90,0.4)}下，使用HEFT算法得到它的下界完成時間Tlowerbound=88，則在盈余時間ΔS=7內(nèi)所有合乎要求的調(diào)度的盈余時間值與完成時間及運(yùn)行能耗(不包含處理器空載能耗)對應(yīng)關(guān)系如表3所示：

Table 3　The Correlation Between Surplus Time and Energy

從表3可以看出，當(dāng)ΔS′∈[3.51,4.75]時，調(diào)度序列完全相同，這意味著在125次遍歷中，有124次遍歷生成的調(diào)度為冗余調(diào)度，如果能通過某種措施有效地去除遍歷中的冗余調(diào)度，則算法時間復(fù)雜度將大幅降低.與此同時，從表3可以看出，所有有效調(diào)度中，運(yùn)行能耗最小值為163.74，此時ΔS′∈[5.92,6.00]，這說明將最大盈余時間ΔS=7直接分配給各個任務(wù)并不能得到運(yùn)行能耗最小的調(diào)度即運(yùn)行能耗最優(yōu)調(diào)度.但是盈余時間越大，可供選擇的有效調(diào)度將越多.大量實驗研究表明，以盈余時間ΔS的中點θ為分界點，則運(yùn)行能耗最優(yōu)調(diào)度其對應(yīng)的盈余時間ΔS′將出現(xiàn)在[Tlowerbound+θ,Tdeadline]值域內(nèi).

由此，引申出算法的設(shè)計思想：取2個大小不同的搜索粒度：最小搜索粒度和最大搜索粒度，算法從最大盈余時間ΔS開始反向演算，直至盈余時間小于θ.每次演算均基于不同的搜索粒度取2個不同的盈余時間，再基于二者使用HEFT算法將工作流在所有處理器和電壓頻率組上遍歷，得到2個有效調(diào)度(即既節(jié)能又滿足時間約束的調(diào)度，如果這樣的調(diào)度不存在，則以原始調(diào)度返回)，接下來基于2個有效調(diào)度能耗大小的判斷結(jié)果設(shè)定下一輪演算的盈余時間與搜索粒度——即算法的核心思想是：在局部最優(yōu)解的基礎(chǔ)上重新指定搜索范圍，期望以較小的時間復(fù)雜度、較快地接近全局最優(yōu)解.過程類似自然界中青蛙的運(yùn)動.

在給出算法的完整描述前，先給出相關(guān)定義：

定義1. 盈余時間.約束時間與下界完成時間的差值ΔS：

ΔS=Tdeadline-Tlowerbound≥0.

(9)

定義2. 蛙跳終點值.即搜索終點值，等于盈余時間ΔS的中點值，用θ表示:

(10)

定義3. 最小躍度值和最大躍度值.每一次反向蛙跳時的跨度值，分別用Δsmin和Δsmax來表示.實質(zhì)上，躍度值即為搜索粒度，為了更好地呼應(yīng)算法，分別用此二值對應(yīng)最小搜索粒度和最大搜索粒度.假設(shè)系統(tǒng)精度為ρ(即保留ρ位小數(shù))，則：

(11)

(12)

定義4. 盈余最早完成時間.任務(wù)ni的當(dāng)前實際完成時間加上盈余時間ΔS′之后的時間:

EFT′(ni,ΔS′)=AFT(ni)+ΔS′.

(13)

定義5. 任務(wù)運(yùn)行能耗.任務(wù)n在處理器p上以電壓頻率(vf)運(yùn)行，在運(yùn)行時間t內(nèi)所產(chǎn)生的能耗:

Erun(n)=αv2f×t，

(14)

其中，t可由式(3)求得.

定義6. 最終可用調(diào)度.算法優(yōu)化后的能耗最低調(diào)度用于工作流的實際調(diào)度，記為FSL.

算法完整描述如下：全稱為反向蛙跳全局能耗感知算法(backward frog-leaping global energy conscious scheduling, BFECS)，共分為3個階段：

1) 階段1稱為原始調(diào)度構(gòu)造階段，與文獻(xiàn)[27-29]一樣,利用HEFT算法求出DAG工作流原始調(diào)度及下界完成時間；

2) 階段2為反向蛙跳全局掃描階段，利用階段1求得的下界完成時間，求得它與約束時間之間的盈余，通過反向蛙跳全局掃描，找出其中既使工作流運(yùn)行能耗最小，同時又滿足時間約束的最優(yōu)調(diào)度(同樣利用HEFT算法求得)；

3) 階段3稱為松弛時間回收階段，在不破壞任務(wù)間依賴關(guān)系及不增加工作流運(yùn)行完成時間的前提下，調(diào)整階段2得到的運(yùn)行能耗最優(yōu)調(diào)度中任務(wù)的運(yùn)行電壓頻率至更低的合適級別上，進(jìn)一步降低DAG工作流的整體運(yùn)行能耗.當(dāng)約束時間等于下界完成時間即不存在盈余時間時，算法直接使用階段3進(jìn)行降能操作.

算法整體構(gòu)造如下：

算法1. BFECS算法.

輸入：DAG圖G=(N,E,W,C)、可變電壓處理器組P、電壓頻率組V；

輸出：最終可用調(diào)度FSL.

① 利用算法2求得原始調(diào)度；

② 利用算法3求得運(yùn)行能耗最優(yōu)調(diào)度；

③ 利用算法4求得最終可用調(diào)度.

下面分階段描述算法，階段1為原始調(diào)度構(gòu)造階段.

算法2. 原始調(diào)度構(gòu)造算法.

輸入：DAG圖G=(N,E,W,C)、可變電壓處理器組P、電壓頻率組V、約束時間Tdeadline、系統(tǒng)精度ρ;

輸出：原始調(diào)度SLorigin.

① 根據(jù)式(5)從出口任務(wù)開始自底向上計算出每個任務(wù)的向上排序值ranku(ni)；

② 對各個任務(wù)依據(jù)ranku(ni)降序排列，得到向上排序值降序任務(wù)列表TLdscranku；

③ 利用HEFT算法調(diào)度各個任務(wù)至合適的處理器上，每個處理器均運(yùn)行在最高電壓，即得到原始調(diào)度，記為SLorigin；

④ 對SLorigin使用式(4)求得Tmakespan，然后將其賦給Tlowerbound.

階段2為反向蛙跳全局掃描階段.

算法3. 反向蛙跳全局掃描算法.

輸入:原始調(diào)度SLorigin、可變電壓處理器組P、電壓頻率組V、向上排序值降序任務(wù)列表TLdscranku、下界完成時間Tlowerbound；

② ifTdeadline≤Tlowerbound

④ else

⑤ 根據(jù)式(9)計算盈余時間ΔS；

⑥ 根據(jù)式(10)計算蛙跳終點值θ；

⑦ 根據(jù)式(11)、式(12)計算最小躍度值Δsmin和最大躍度值Δsmax；

通過實驗觀察可知，算法階段2得到的調(diào)度序列某些任務(wù)之間存在如文獻(xiàn)[27-29]所描述的松弛時間，在不破壞任務(wù)間依賴關(guān)系的前提下，通過回收技術(shù)可以進(jìn)一步降低DAG工作流的運(yùn)行能耗.故算法階段3稱為松弛時間回收階段.參照文獻(xiàn)[27-29]，先給出一些相關(guān)描述知識.

針對某一任務(wù)ni，其最遲完成時間(latest finish time,LFT)的計算公式如下：

(15)

其中,tj表示任務(wù)運(yùn)行時間;ci,j表示任務(wù)ni和nj之間的通信開銷，如果ni與nj運(yùn)行在同一處理器上，則通信開銷ci,j=0.

任務(wù)的松弛時間計算為

Slack(ni)=LFT(ni)-AST(ni)-ti，

(16)

其中，AST(ni)表示任務(wù)ni的實際啟動時間(actual start time, AST)，ti定義與式(15)中tj類同.

對潛在的任務(wù)進(jìn)行降頻操作即回收松弛時間之前，先計算出每個任務(wù)的LFT(ni)與Slack(ni)，接下來遍歷向上排序值降序列表TLdscranku，每次從中選出隊頭任務(wù)ni，它運(yùn)行在處理器pk上，如果Slack(ni)>0，則意味著ni的完成時間可以由之前的AFT(ni)變更為LFT(ni)，即ni的運(yùn)行時間段可以被延長Slack(ni)個時間單位.在可變電壓頻率技術(shù)下，通過降低處理器的運(yùn)行頻率即可實現(xiàn)這一目的.假設(shè)任務(wù)ni完全消化掉松弛時間Slack(ni)時的最佳運(yùn)行頻率為fop，則：

(17)

fnew=min(fl|fl∈Fpk,fl≥fop)，

(18)

其中,Fpk為處理器pk上的離散頻率集.得到新的運(yùn)行頻率fnew后，進(jìn)一步求得ni新的執(zhí)行時間：

(19)

然后根據(jù)此時間更新任務(wù)ni的運(yùn)行時間段，并將此更新保存下來.接下來需要對任務(wù)ni所有的直接前驅(qū)任務(wù)nj∈pred(ni)，以及與ni運(yùn)行在同一處理器上的前緊鄰任務(wù)np(如果存在)進(jìn)行LFT和Slack更新操作，步驟依次為：

1) 針對ni的每1個直接前驅(qū)任務(wù)nj，首先計算出nj新的最遲完成時間LFT′(nj)：

tk-cj,k),AST(ndn(j))},

(20)

其中,tk,cj,k與式(15)中tj,ci,j定義類同.AFT(nk)為nj后繼任務(wù)nk的實際完成時間；ndn(j)表示與任務(wù)nj處于同一處理器上且排在nj之后運(yùn)行的第1個任務(wù)(如果存在)，如圖2(a)所示，ndn(1)=n3，ndn(2)=n4.式(20)可以確保nj新的最遲完成時間LFT′(nj)小于或等于后緊鄰任務(wù)的實際開始時間，目的是為了保證任務(wù)間依賴關(guān)系不被破壞.

2) 將LFT′(nj)代入式(16)后，可求得任務(wù)nj新的松弛時間Slack′(nj).

3) 同樣地，針對與ni運(yùn)行在同一處理器上ni的前一個任務(wù)，也稱前緊鄰任務(wù)np(如果存在)進(jìn)行同樣的LFT和Slack更新操作.以上更新操作執(zhí)行完成后，將任務(wù)ni移出序列.重復(fù)以上過程直至任務(wù)序列為空.算法具體描述如下：

算法4. 松弛時間回收算法.

輸出: 最終可用調(diào)度FSL.

② 根據(jù)式(15)計算所有任務(wù)的最遲完成時間LFT；

③ forTLdscranku≠? do

④ 從TLdscranku取出任務(wù)ni；

⑤ 根據(jù)式(16)求得任務(wù)的ni松弛時間Slack(ni)；

⑥ ifSlack(ni)>0 then

⑦ 根據(jù)式(17)求得任務(wù)ni的最佳運(yùn)行頻率fop；

⑧ 根據(jù)式(18)求得任務(wù)ni的實際運(yùn)行頻率fnew；

⑩ 更新任務(wù)ni的實際運(yùn)行頻率為fnew；

3.2算法復(fù)雜度分析

BFECS算法時間復(fù)雜度為O(m×p×v×e)，其中m為蛙跳次數(shù)，它與盈余時間ΔS、系統(tǒng)精度ρ正相關(guān)；p為處理器數(shù)；v為電壓頻率組數(shù)；e為DAG邊數(shù).

大量實驗研究表明，滿足時間約束的全局能耗最優(yōu)調(diào)度，其完成時間接近約束時間，即此時算法嘗試分配到各任務(wù)的盈余時間接近最大盈余時間.BFECS算法從約束時間開始反向搜索解空間，同時在搜索過程中基于返回結(jié)果與當(dāng)前最優(yōu)調(diào)度的判斷，不斷調(diào)整搜索粒度大小，期望以較快的速度找到最優(yōu)調(diào)度.算法從最大盈余時間開始反向演算這一設(shè)計思想，能更快地找到最優(yōu)解，提升算法收斂速度.

在算法每輪搜索中，總是將得到的調(diào)度與當(dāng)前最優(yōu)調(diào)度比較，如果新調(diào)度更有節(jié)能優(yōu)勢，則將它置為當(dāng)前最優(yōu)調(diào)度，否則保持當(dāng)前最優(yōu)調(diào)度不變.即算法在任何情況下均可以返回有效調(diào)度，算法是健壯的.

4實驗結(jié)果與分析

4.1環(huán)境與樣本設(shè)定

實驗選取算法HEFT[20]，EES[27]，DEWTS[29]與BFECS進(jìn)行比較，所有算法均用Java編寫，實驗環(huán)境為Windows 7 64 b，硬件配置為Intel Xeon E5-1603@2.80 GHz，4CPUs，16 GB RAM.

與文獻(xiàn)[20,27,29]類似，實驗使用隨機(jī)DAG工作流來評估算法.通過隨機(jī)設(shè)定DAG工作流的任務(wù)數(shù)、處理器數(shù)、計算開銷、通信開銷等參數(shù)，來模擬各種可能的并行工作流.具體為：任務(wù)數(shù)值域為n={20,40,60,80,100,120}.并行化因子值域為β={0.2,0.5,1.0,2.0,5.0}，該因子取值越大，則工作流并行度越高.通信計算比CCR的值域為ccr={0.1,0.5,1.0,2.0,5.0}，該比值越小，表示工作流為計算密集型，反之則為通信密集型.處理器數(shù)值域為p={4,8,16,32,64,128}.處理器異構(gòu)因子值域為ε={0.2,0.4,0.5,0.6,0.8,1.0}，該值越小，系統(tǒng)異構(gòu)性越不明顯.約束時間Tdeadline與下界完成時間Tlowerbound的差值與T之比(時間差值因子)α={0.2,0.4,0.6,0.8,1.0}，系統(tǒng)精度ρ=2即保留2位小數(shù).

同時，本文選取3個不同的具有DVFS功能的處理器作為實驗設(shè)定之一[29]，它們的電壓頻率組值如表4所示：

Table 4　The Voltage and Frequency Pairs of Three Different Processor

表4　3種不同處理器的電壓頻率組

Table 4　The Voltage and Frequency Pairs of Three Different Processor

LevelAMDAthlon-64IntelPentiumMAMDOpteron2218Voltage∕VFrequency∕GHzVoltage∕VFrequency∕GHzVoltage∕VFrequency∕GHz01.52.01.4841.41.302.611.41.81.4631.21.252.421.31.61.3081.01.202.231.21.41.1800.81.152.041.11.20.9560.61.101.851.01.01.051.060.90.8

4.2評價指標(biāo)

本文采用能耗比(energy consumption ratio,ECR)[15,29]和節(jié)能比(energy saving ratio,ESR)[29]作為評價指標(biāo)，將提出的BFECS算法與HEFT，EES和DEWTS進(jìn)行比較.其中DEWTS算法將無任務(wù)運(yùn)行的空閑計算節(jié)點斷電關(guān)機(jī)，被認(rèn)為不合實際，因此針對該算法我們在實驗中保持空閑計算節(jié)點的開啟.

能耗比ECR的計算為

其中,分母為關(guān)鍵路徑任務(wù)[20]CP在處理器pk(記使得關(guān)鍵路徑任務(wù)完成時間最小的處理器為pk)上以最高電壓頻率運(yùn)行時產(chǎn)生的運(yùn)行能耗.約定在空閑階段，處理器運(yùn)行在最低電壓頻率以節(jié)能.Etotal為當(dāng)前算法產(chǎn)生的整體能耗.

節(jié)能比表示約束時間內(nèi)算法節(jié)約的能耗(即HEFT算法產(chǎn)生的能耗Ebase與當(dāng)前算法產(chǎn)生的能耗Etotal之差)與Ebase的比值，它能直觀地反應(yīng)算法節(jié)能效率：

由此可以看出，只需將BFECS與EES，DEWTS兩個算法比較即可.同樣約定在空閑階段，處理器運(yùn)行在最低電壓頻率上以節(jié)能.

4.3實驗結(jié)果及分析

Fig. 4　Average ECR under different task numbers.圖4　不同任務(wù)數(shù)下各算法能耗比

實驗1. 比較各個算法在不同任務(wù)數(shù)下的ECR值.具體步驟為：固定其他參數(shù)(異構(gòu)因子ε=0.5，并行化因子β=1.0，處理器數(shù)p=32，通信計算比ccr=0.5，時間差值因子α=0.2)，改變?nèi)蝿?wù)數(shù)，每個算法各運(yùn)行1 000遍，然后取其ECR平均值.

從圖4可以看出，在不同任務(wù)數(shù)下，BFECS算法能耗為HEFT算法能耗的77.5%～81.3%，DEWTS算法的79.7%～83.5%，EES算法的94.3%～98.3%，為4種算法中能耗最低的算法，且節(jié)能效率比較穩(wěn)定.與其他3種算法不同，BFECS在所有計算節(jié)點上遍歷，從所有有效調(diào)度中找出最節(jié)能的調(diào)度，因此它的節(jié)能效率得以較好保證.

實驗2. 比較各個算法在不同處理器數(shù)下的ECR值.具體步驟為：固定其他參數(shù)(任務(wù)數(shù)n=40，異構(gòu)因子ε=0.5，并行化因子β=1.0，通信計算比ccr=0.5，時間差值因子α=0.2)，改變處理器數(shù)，每個算法各運(yùn)行1 000遍，然后取其ECR平均值.

從圖5可以看出，隨著計算節(jié)點的增多，各算法的能量消耗形勢趨同明顯.源于計算節(jié)點的增多導(dǎo)致潛在的空閑計算節(jié)點同時增多，空載耗能成為主要的影響因素.但在4種算法中BFECS算法仍然屬于能耗最小的算法，在處理器數(shù)量可變情況下，BFECS算法能耗為HEFT算法的68.4%～93.2%，DEWTS算法的76.3%～94.1%，EES算法的88.9%～99.2%，算法節(jié)能效率明顯且穩(wěn)定.

Fig. 5　Average ECR under different numbers of processors.圖5　不同處理器數(shù)下各算法能耗比

實驗3. 比較各個算法在不同約束時間下的ECR值.具體步驟為：固定其他參數(shù)(任務(wù)數(shù)n=60，處理器數(shù)p=32，異構(gòu)因子ε=0.8，并行化因子β=2.0，通信計算比ccr=0.5)，改變時間差值因子，每個算法各運(yùn)行1 000遍，然后取其ECR平均值.

圖6中，隨著時間差值因子的增大即約束時間的增大，BFECS算法的節(jié)能優(yōu)勢相對于EES算法逐步縮小.源于增大的盈余時間使得BFECS算法與EES算法同時給予各任務(wù)以更高的概率運(yùn)行在處理器的低電壓位上，因此兩者能耗趨同明顯.盈余時間的增大雖然有助于DEWTS算法以更大概率遷移任務(wù)至同一處理器上運(yùn)行，但在大規(guī)模并行工作流中，增大的盈余時間不足以抵消高并行度所帶來的影響，因此其節(jié)能效率逐漸被BFECS和EES拉開距離，與HEFT一起成為耗能較高的算法，并且當(dāng)約束時間超過一定的范圍之后，DEWTS算法中空閑計算節(jié)點越來越多，它逐漸超越HEFT算法成為最不節(jié)能的算法.反之，當(dāng)時間差值因子減小時，BFECS算法節(jié)能優(yōu)勢較EES更為明顯，如當(dāng)α=0.4時它的能耗為EES算法的94.8%，當(dāng)α=0.2時它的能耗為EES算法的83.1%.整體而言，BFECS算法在約束時間可變時，它的能耗約為HEFT算法的42.9%～58.4%，DEWTS算法的42.9%～66.1%，EES算法的83.1%～99.9%.

Fig. 6　Average ECR under different deadlines.圖6　不同約束時間下各算法能耗比

實驗4. 比較各個算法在不同處理器異構(gòu)因子下的ECR值.具體步驟為：固定其他參數(shù)(任務(wù)數(shù)n=40，并行化因子β=2.0，處理器數(shù)p=32，通信計算比ccr=0.5，時間差值因子α=0.2)，改變處理器異構(gòu)因子，每個算法各運(yùn)行1 000遍，然后取其ECR平均值.

本組實驗中，首先選取一個基準(zhǔn)平均計算開銷譬如說100，然后基于此值，根據(jù)不同的異構(gòu)因子隨機(jī)生成各任務(wù)在每個處理器上的計算開銷，最終通過計算開銷數(shù)值來體現(xiàn)處理器的異構(gòu)性.從圖7可以看出，BFECS算法在降低能耗方面恒定保有領(lǐng)先優(yōu)勢，為HEFT算法的59.9%～63.4%，DEWTS算法的66.6%～72.1%，EES算法能耗的91.3%～95.7%.從實驗也可以看出，BFECS算法對系統(tǒng)異構(gòu)性不敏感，節(jié)能效率比較穩(wěn)定.

Fig. 7　Average ECR under different hetero factors of processors.圖7　不同處理器異構(gòu)因子下各算法能耗比

實驗5. 比較各個算法在不同任務(wù)數(shù)下的ESR值.具體步驟為：固定其他參數(shù)(異構(gòu)因子ε=0.5，并行化因子β=1.0，處理器數(shù)p=32，通信計算比ccr=0.5，時間差值因子α=0.2)，改變?nèi)蝿?wù)數(shù)，每個算法各運(yùn)行1 000遍，然后取其ESR平均值.

從圖8可以看出，不同任務(wù)數(shù)下，BFECS算法在節(jié)能方面比EES算法高出2.49%～30.2%，比DEWTS算法高出0.6～1.98倍，為3種算法中節(jié)能比最高的算法.任務(wù)數(shù)較少時，工作流運(yùn)行能耗也小，在固定數(shù)量的計算節(jié)點上，BFECS算法從全局篩選出最節(jié)能的調(diào)度，此時節(jié)能比最高.隨著任務(wù)數(shù)的增多，工作流運(yùn)行能耗相應(yīng)增大，在計算節(jié)點與時間差值因子固定的情況下，潛在能耗節(jié)約概率隨之減小，此時BFECS算法與EES算法的節(jié)能比逐步接近，但BFECS仍為最節(jié)能的算法.

Fig. 8　Average ESR under different task numbers.圖8　不同任務(wù)數(shù)下各算法節(jié)能比

實驗6. 比較各個算法在不同處理器數(shù)下的ESR值.具體步驟為：固定其他參數(shù)(任務(wù)數(shù)n=40，異構(gòu)因子ε=0.5，并行化因子β=1.0，通信計算比ccr=0.5，時間差值因子α=0.2)，改變處理器數(shù)，每個算法各運(yùn)行1 000遍，然后取其ESR平均值.

從圖9可以看出，隨著計算節(jié)點的增多，節(jié)能比呈下降趨勢，源于計算節(jié)點的增多導(dǎo)致潛在的空閑計算節(jié)點同時增多，空載耗能成為主要影響因素.整體而言，BFECS算法在節(jié)能方面比EES算法高出12.25%～47.5%，比DEWTS算法高出0.87～6.35倍，節(jié)能優(yōu)勢明顯.在實驗設(shè)定中，DEWTS算法由于不能關(guān)閉空閑計算節(jié)點，而是代之以最低電壓頻率空載運(yùn)行，隨著計算節(jié)點的增多它變得越來越不節(jié)能.

Fig. 9　Average ESR under different numbers of processors.圖9　不同處理器數(shù)下各算法節(jié)能比

實驗7. 比較各個算法在不同約束時間下的ESR值.固定其他參數(shù)(任務(wù)數(shù)n=60，處理器數(shù)p=32，異構(gòu)因子ε=0.8，并行化因子β=2.0，通信計算比ccr=0.5)，改變時間差值因子，每個算法各運(yùn)行1 000遍，然后取其ESR平均值.從實驗3可以看出，當(dāng)約束時間超過一定的范圍之后，DEWTS超越HEFT成為最不節(jié)能的算法，勢必導(dǎo)致本組實驗中的節(jié)能比出現(xiàn)負(fù)數(shù)，因此，本組實驗將時間差值因子限定在一個較小的取值范圍，具體為α={0.1,0.2,0.3,0.4,0.5}.

從圖10可以看出，當(dāng)時間差值因子較小時，如α=0.1或0.2時，BFECS算法在節(jié)能方面，比EES算法高出28.1%～40.7%，比DEWTS算法高出1.15～3.02倍.當(dāng)時間差值因子增大時，BFECS和EES兩種算法在節(jié)能方面差距逐漸縮小，源于增大的盈余時間導(dǎo)致計算節(jié)點空載幾率同步增大，空載能耗成為主要的影響因素.極端情況下，當(dāng)約束時間足夠大時，所有任務(wù)均運(yùn)行在最低電壓頻率上，此時BFECS與EES在節(jié)能效率方面近乎相同.反觀DEWTS算法，增長的盈余時間導(dǎo)致它的空閑計算節(jié)點越來越多，它變得越來越不節(jié)能，圖10較好地印證了這點.

Fig. 10　Average ESR under different deadlines.圖10　不同約束時間下各算法節(jié)能比

實驗8. 比較各個算法在不同異構(gòu)因子下的ESR值.固定其他參數(shù)(任務(wù)數(shù)n=40，并行化因子β=2.0，處理器數(shù)p=32，通信計算比ccr=0.5，時間差值因子α=0.2)，改變時間差值因子，每個算法各運(yùn)行1 000遍，然后取其ESR平均值.

Fig. 11　Average ESR under different hetero factors of processors.圖11　不同異構(gòu)因子下各算法節(jié)能比

從圖11可以看出，在異構(gòu)因子的變化的情況下，BFECS算法持續(xù)保有較好的節(jié)能優(yōu)勢.整體而言，在節(jié)能比方面，它比EES算法高出5.8%～11.5%，比DEWTS算法高出45.1%～97.2%倍，為最節(jié)能之算法且對系統(tǒng)異構(gòu)因素不敏感.

5結(jié)束語

本文利用DAG工作流下界完成時間與約束時間之間的盈余，引入最小躍度值和最大躍度值概念，提出了一種滿足時間約束的能耗優(yōu)化算法BFECS.與其他算法相比，BFECS總覽全局，從所有可行調(diào)度中找出運(yùn)行能耗最小的工作流調(diào)度，再利用松弛時間回收技術(shù)，在保持任務(wù)間依賴關(guān)系及滿足工作流時間約束的前提下，調(diào)整任務(wù)的運(yùn)行電壓頻率至更低但合適級別上，從而進(jìn)一步降低DAG工作流的整體能耗.實驗結(jié)果證實了BFECS算法的優(yōu)越性.另外，該方法在實際應(yīng)用中還有若干問題有待解決，如本文研究的是離線模型，未就任務(wù)執(zhí)行時可能存在的“掉隊”(straggler)情況進(jìn)行考慮，因此，未來將該情況融入到離線模型中是一個非常有價值的研究問題.

參考文獻(xiàn)

[1]Tanenbaum A S, Bos H. Modern Operating Systems[M]. Upper Saddle River, NJ: Prentice Hall, 2014

[2]Hwang K, Dongarra J, Fox G C. Distributed and Cloud Computing: From Parallel Processing to the Internet of Things[M]. San Francisco, CA: Morgan Kaufmann, 2013

[3]Fox G. Peer-to-Peer networks[J]. Computing in Science & Engineering, 2001, 3(3): 75-77

[4]Yang Guangwen, Jin Hai, Li Minglu, et al. Grid computing in China[J]. Journal of Grid Computing, 2004, 2(2): 193-206

[5]Zou Futai, Zhang Liang, Chen Shudong. Peer-to-peer network, grid computing and cloud computing—principles and security[M]. Beijing: Tsinghua University Press, 2012 (in Chinese)(鄒福泰, 張亮, 陳曙東. 對等網(wǎng)絡(luò)、網(wǎng)格計算與云計算——原理與安全[M]. 北京: 清華大學(xué)出版社, 2012)

[6]Amazon. Amazon Elastic Compute Cloud (EC2) [EBOL]. [2016-02-18]. http:www.amazon.comec2

[7]Google. Google App Engine [EBOL]. [2016-02-18]. http:appengine.google.com

[8]Apache. Hadoop [EBOL]. [2016-02-18]. http:hadoop.apache.org

[9]Apache. Spark [EBOL]. [2016-02-18]. http:spark.apache.org

[10]Wu Xindong, Zhu Xingquan, Wu Gongqing, et al. Data mining with big data[J]. IEEE Trans on Knowledge and Data Engineering, 2014, 26(1): 97-107

[11]Rao Lei, Liu Xue, Xie Le, et al. Coordinated energy cost management of distributed Internet data centers in smart grid[J]. IEEE Trans on Smart Grid, 2012, 3(1): 50-58

[12]Deng Wei, Liu Fangming, Jin Hai, et al. Harnessing renewable energy in cloud datacenters: Opportunities and challenges[J]. IEEE Network, 2014, 28(1): 48-55

[13]Greenberg A, Hamilton J, Maltz D A, et al. The cost of a cloud: Research problems in data center networks[J]. ACM SIGCOMM Computer Communication Review, 2008, 39(1): 68-73

[14]Deng Wei, Liu Fangming, Jin Hai, et al. Reliability-aware server consolidation for balancing energy-lifetime tradeoff in virtualized cloud datacenters[J]. International Journal of Communication Systems, 2014, 27(4): 623-642

[15]Zhang Longxin, Li Kenli, Xu Yuming, et al. Maximizing reliability with energy conservation for parallel task scheduling in a heterogeneous cluster[J]. Information Sciences, 2015, 319: 113-131[16]Wikipedia. Dynamic voltage scaling[EBOL]. (2016-01-06) [2016-02-18]. https:en.wikipedia.orgwikiDynamic_voltage_scaling

[17]Chandrakasan A P, Sheng S, Brodersen R W. Low-power CMOS digital design[J]. IEICE Trans on Electronics, 1992, 75(4): 371-382

[18]Wang Lizhe, Von Laszewski G, Dayal J, et al. Towards energy aware scheduling for precedence constrained parallel tasks in a cluster with DVFS[C]Proc of the 10th IEEE Int Conf on Cluster, Cloud and Grid Computing (CCGrid 2010). Piscataway, NJ: IEEE, 2010: 368-377

[19]Gerards M E T, Hurink J L, Kuper J. On the interplay between global DVFS and scheduling tasks with precedence constraints[J]. IEEE Trans on Computers, 2015, 64(6): 1742-1754

[20]Topcuoglu H, Hariri S, Wu M. Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Trans on Parallel and Distributed Systems, 2002, 13(3): 260-274

[21]Guoqi Xie, Liangjiao Liu, Liu Yang, et al. Scheduling trade-off of dynamic multiple parallel workflows on heterogeneous distributed computing systems[J]. Concurrency and Computation-Practice & Experience，2016, 1: 1-18

[22]Yuan Yingchun, Li Xiaoping, Wang Qian. Time optimization heuristics for scheduling budget-constrained grid workflows [J]. Journal of Computer Research and Development, 2009, 46(2): 194-201 (in Chinese)(苑迎春, 李小平, 王茜, 等. 成本約束的網(wǎng)格工作流時間優(yōu)化方法[J]. 計算機(jī)研究與發(fā)展, 2009, 46(2): 194-201)

[23]Liu Cancan, Zhang Weimin, Luo Zhigang, et al. Workflow cost optimization heuristics based on advanced priority rule [J]. Journal of Computer Research and Development, 2012, 49(7): 1593-1600 (in Chinese)(劉燦燦, 張衛(wèi)民, 駱志剛, 等. 基于改進(jìn)優(yōu)先級規(guī)則的工作流費用優(yōu)化方法[J]. 計算機(jī)研究與發(fā)展, 2012, 49(7): 1593-1600)

[24]Liu Fangming, Zhou Zhi, Jin Hai, et al. On arbitrating the power-performance tradeoff in SaaS clouds[J]. IEEE Trans on Parallel and Distributed Systems, 2014, 25(10): 2648-2658

[25]Lee Y C, Zomaya A Y. Energy conscious scheduling for distributed computing systems under different operating conditions[J]. IEEE Trans on Parallel and Distributed Systems, 2011, 22(8): 1374-1381

[26]Li Keqin. Scheduling precedence constrained tasks with reduced processor energy on multiprocessor computers[J]. IEEE Trans on Computers, 2012, 61(12): 1668-1681

[27]Huang Qingjia, Su Sen, Li Jian, et al. Enhanced energy-efficient scheduling for parallel applications in cloud[C]Proc of the 12th IEEE Int Symp on Cluster, Cloud and Grid Computing (CCGrid 2012). Los Alamitos, CA: IEEE Computer Society, 2012: 781-786

[28]Su Sen, Huang Qingjia, Li Jian, et al. Enhanced energy-efficient scheduling for parallel tasks using partial optimal slacking[J]. The Computer Journal, 2015: 58(2): 246-257

[29]Tang Zhuo, Qi Ling, Cheng Zhenzhen, et al. An energy-efficient task scheduling algorithm in DVFS-Enabled cloud environment[J]. Journal of Grid Computing, 2016: 14(1): 55-74

[30]Fahringer T, Prodan R, Duan R, et al. ASKALON: A grid application development and computing environment[C]Proc of the 6th IEEE Int Workshop on Grid Computing. Los Alamitos, CA: IEEE Computer Society, 2005: 122-131

Jiang Junqiang, born in 1980. PhD candidate. Student member of China Computer Federation. His main research interests include cloud computing, parallel computing and resource scheduling.

Lin Yaping, born in 1955. Professor and PhD supervisor in Hunan University since 1996. Senior member of China Computer Federation. His main research interests include cloud computing, machine learning, network security and wireless sensor networks.

Xie Guoqi, born in 1983. PhD, postdoctoral researcher. Member of China Computer Federation. His main research interests include distributed systems, embedded systems, real-time systems (xgqman@hnu.edu.cn).

Zhang Shiwen, born in 1987. PhD candidate. His main research interests include security and privacy issues in social networks, cloud computing, sensor network, and data mining (shiwenzhang@hnu.edu.cn).

收稿日期：2016-03-10；修回日期：2016-05-12

基金項目：國家自然科學(xué)基金項目(61472125)

通信作者：林亞平(yplin@hnu.edu.cn)

中圖法分類號TP393

Energy Optimization Heuristic for Deadline-Constrained Workflows in Heterogeneous Distributed Systems

Jiang Junqiang1,2, Lin Yaping1,2, Xie Guoqi1, and Zhang Shiwen1,2

1(CollegeofComputerScienceandElectronicEngineering,HunanUniversity,Changsha410082)2(KeyLaboratoryforDependableSystemandNetworksofHunanProvince(HunanUniversity),Changsha410082)

AbstractMost of existing energy optimization heuristics with deadline constraint for workflows in DVFS-enabled heterogeneous distributed systems usually trap in local optima. In this paper, we propose a new energy optimization heuristic called backward frog-leaping global energy conscious scheduling: BFECS. This algorithm makes full use of surplus time between the lowerbound of the workflow and the constrained deadline. Specifically, it starts from the constrained deadline, and leapfrogs towards the lowerbound of the workflow with different leap interval. During the whole process of leapfrogging, the leap intervals are continually changed according to the locally optimal value until the endpoint of leapfrogging is reached; the scheduling sequence with least run energy consumption is also saved at the same time. Furthermore, more energy consumption can be reduced by leveraging slack time reclamation technique, and the idle time slots caused by precedence constraints can be assimilated by the tasks through running at a lower and suitable voltage?frequency using DVFS technique, without violating the precedence constraints of the workflow and breaking the deadline. The experimental results show that the proposed algorithm can decrease energy consumption significantly.

Key wordsheterogeneous distributed systems; energy optimization; deadline constraint; workflow; slack time reclamation

This work was supported by the National Natural Science Foundation of China (61472125).