時間約束的異構分布式系統工作流能耗優化算法

蔣軍強　林亞平　謝國琪　張世文

1(湖南大學信息科學與工程學院　長沙　410082)2　　　(可信系統與網絡湖南省重點實驗室(湖南大學)　長沙　410082)

?

時間約束的異構分布式系統工作流能耗優化算法

蔣軍強1,2林亞平1,2謝國琪1張世文1,2

1(湖南大學信息科學與工程學院長沙410082)2(可信系統與網絡湖南省重點實驗室(湖南大學)長沙410082)

(jjq@hnu.edu.cn)

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

關鍵詞異構分布式系統；能耗優化；時間約束；工作流；松弛時間回收

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

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

1相關工作

科學研究、電子商務等領域的許多應用均可看做是工作流——一種面向過程建模和管理的核心技術，常可用有向無環圖(directed acyclic graph, DAG)表示[20-21].用戶將工作流提交到計算系統后，一般會有附加的服務質量(quality of service, QoS)要求，如費用、執行時間、可靠性等.用戶期望工作流在執行時滿足QoS要求，因此，基于QoS的工作流調度問題就是在所有滿足QoS的調度中選擇最合適的調度執行.

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

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

2模型及問題定義

2.1系統模型

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

2.2應用模型

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

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

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

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

EST(ni,pk)=

(1)

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

(2)

(3)

Tmakespan=AFT(nexit).

(4)

同樣，根據文獻[20]給出任務ni的向上排序值計算公式：

(5)

2.3能耗模型

根據文獻[25,27]，有能耗

P=ACV2f,

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

(6)

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

(7)

Etotal=Erun+Eidle.

(8)

2.4問題定義

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

min(Erun+Eidle)，

s.t.Tmakespan≤Tdeadline,

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

3算法描述及復雜性分析

3.1算法描述

在給出本文算法描述之前，先來看一個DAG調度模型.為了更好地理解該算法，此處假設任務在處理器上的執行速度相同，詳細數值由表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設定，使用HEFT算法生成該DAG的原始調度，可以得到Tmakespan=80，Etotal=339，如圖2(a)所示.

Fig. 2　Scheduling list of example DAG.圖2　DAG調度圖

Fig. 3　Scheduling list after each task moderates to lower frequency.圖3　各任務降頻后的調度圖

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

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

Table 3　The Correlation Between Surplus Time and Energy

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

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

在給出算法的完整描述前，先給出相關定義：

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

ΔS=Tdeadline-Tlowerbound≥0.

(9)

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

(10)

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

(11)

(12)

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

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

(13)

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

Erun(n)=αv2f×t，

(14)

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

定義6. 最終可用調度.算法優化后的能耗最低調度用于工作流的實際調度，記為FSL.

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

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

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

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

算法整體構造如下：

算法1. BFECS算法.

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

輸出：最終可用調度FSL.

① 利用算法2求得原始調度；

② 利用算法3求得運行能耗最優調度；

③ 利用算法4求得最終可用調度.

下面分階段描述算法，階段1為原始調度構造階段.

算法2. 原始調度構造算法.

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

輸出：原始調度SLorigin.

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

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

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

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

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

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

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

② ifTdeadline≤Tlowerbound

④ else

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

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

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

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

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

(15)

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

任務的松弛時間計算為

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

(16)

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

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

(17)

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

(18)

其中,Fpk為處理器pk上的離散頻率集.得到新的運行頻率fnew后，進一步求得ni新的執行時間：

(19)

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

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

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

(20)

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

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

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

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

輸出: 最終可用調度FSL.

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

③ forTLdscranku≠? do

④ 從TLdscranku取出任務ni；

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

⑥ ifSlack(ni)>0 then

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

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

⑩ 更新任務ni的實際運行頻率為fnew；

3.2算法復雜度分析

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

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

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

4實驗結果與分析

4.1環境與樣本設定

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

與文獻[20,27,29]類似，實驗使用隨機DAG工作流來評估算法.通過隨機設定DAG工作流的任務數、處理器數、計算開銷、通信開銷等參數，來模擬各種可能的并行工作流.具體為：任務數值域為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}，該比值越小，表示工作流為計算密集型，反之則為通信密集型.處理器數值域為p={4,8,16,32,64,128}.處理器異構因子值域為ε={0.2,0.4,0.5,0.6,0.8,1.0}，該值越小，系統異構性越不明顯.約束時間Tdeadline與下界完成時間Tlowerbound的差值與T之比(時間差值因子)α={0.2,0.4,0.6,0.8,1.0}，系統精度ρ=2即保留2位小數.

同時，本文選取3個不同的具有DVFS功能的處理器作為實驗設定之一[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評價指標

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

能耗比ECR的計算為

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

節能比表示約束時間內算法節約的能耗(即HEFT算法產生的能耗Ebase與當前算法產生的能耗Etotal之差)與Ebase的比值，它能直觀地反應算法節能效率：

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

4.3實驗結果及分析

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

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

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

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

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

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

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

圖6中，隨著時間差值因子的增大即約束時間的增大，BFECS算法的節能優勢相對于EES算法逐步縮小.源于增大的盈余時間使得BFECS算法與EES算法同時給予各任務以更高的概率運行在處理器的低電壓位上，因此兩者能耗趨同明顯.盈余時間的增大雖然有助于DEWTS算法以更大概率遷移任務至同一處理器上運行，但在大規模并行工作流中，增大的盈余時間不足以抵消高并行度所帶來的影響，因此其節能效率逐漸被BFECS和EES拉開距離，與HEFT一起成為耗能較高的算法，并且當約束時間超過一定的范圍之后，DEWTS算法中空閑計算節點越來越多，它逐漸超越HEFT算法成為最不節能的算法.反之，當時間差值因子減小時，BFECS算法節能優勢較EES更為明顯，如當α=0.4時它的能耗為EES算法的94.8%，當α=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. 比較各個算法在不同處理器異構因子下的ECR值.具體步驟為：固定其他參數(任務數n=40，并行化因子β=2.0，處理器數p=32，通信計算比ccr=0.5，時間差值因子α=0.2)，改變處理器異構因子，每個算法各運行1 000遍，然后取其ECR平均值.

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

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

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

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

Fig. 8　Average ESR under different task numbers.圖8　不同任務數下各算法節能比

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

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

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

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

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

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

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

Fig. 11　Average ESR under different hetero factors of processors.圖11　不同異構因子下各算法節能比

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

5結束語

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

參考文獻

[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)(鄒福泰, 張亮, 陳曙東. 對等網絡、網格計算與云計算——原理與安全[M]. 北京: 清華大學出版社, 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)(苑迎春, 李小平, 王茜, 等. 成本約束的網格工作流時間優化方法[J]. 計算機研究與發展, 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)(劉燦燦, 張衛民, 駱志剛, 等. 基于改進優先級規則的工作流費用優化方法[J]. 計算機研究與發展, 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

基金項目：國家自然科學基金項目(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).