能耗約束下基于預算等級的調度長度最小化算法

劉丹彤，張龍信，楊 佳，暴子豪，艾明慧

（湖南工業大學 計算機學院，湖南 株洲 412007）

1 研究背景

異構云系統（heterogeneous cloud system，HCS）由多個計算單元連接組成，其可擴展性強，在分析處理海量數據和進行大規模科學計算時發揮著重要作用[1-2]。隨著人工智能、大數據和云計算等技術的飛速發展，計算的應用需求和系統性能都趨向多樣化和復雜化，系統架構集成度不斷提高，導致計算功耗顯著增加，產生了更高昂的電力成本，甚至對環境造成了污染[3]。降低計算系統的能耗已成為當前HCS 開發和使用所面臨的主要瓶頸，也是影響經濟和生態技術發展的重要因素。推進節能能夠提高計算設備的利用率，促進經濟可持續發展[4]。

近年來，在能耗約束下進行科學工作流調度已經引起了廣泛的研究。在電壓和頻率可變的虛擬機（virtual machine，VM）上進行能耗感知任務調度一直被學者們廣泛研究[5]。動態電壓和頻率縮放（dynamic voltage and frequency scaling，DVFS） 作為一種被廣泛使用的降低系統能源消耗的經典技術，主要通過調整VM 上的電源電壓和頻率來進行功率感知任務調度，提高能量效率比，從而實現對系統能耗的控制[6-7]。

HCS 中基于功率感知的任務調度長度最小化一直是一個研究熱點。Tang Z.等[8]提出了利用空閑時間的回收來合并效率較低的VM 以實現對空閑時間的有效利用，減少能量浪費。Song J.等[9]提出了一種有效的調度算法，在能耗受限的情況下，通過對松弛能量的相對平均分配以最小化應用程序的調度長度。王蘭等[10]將節點根據其通信開銷和計算開銷劃分為單獨的隊列，再將關鍵節點劃分到適合的隊列中，減少了工作流的完工時間并提高了處理器的調度效率。Li K.Q.[11]將關注重點放在靜態功耗上，通過解析方法建立了具有給定能耗約束的并行任務集的最小調度長度，同時建立了給定調度長度約束下任務集最小能耗的下界。該解析思想為具有動態和靜態功耗工作流調度提供了分析方法，以評估啟發式算法性能。A.K.Maurya 等[12]在基于能量感知服務的水平協議和不改變最大完工時間的前提下降低頻率，同時利用預測最早完成時間算法以計算工作流的完工時間。文獻[13]提出了兩種經典的算法，其中異構的最早完成時間優先算法（heterogeneous earliest-finish-time，HEFT）是一種基于插入思想的最小完成時間算法，而關鍵任務置于同一處理器算法（critical-path-on-a-processor，CPOP）則在任務優先級階段進行了改進，并最小化關鍵任務的執行時間。M.Sulaiman 等[14]將啟發式算法和元啟發式算法的思想相結合，利用列表和任務復制思想提出了兩種基于遺傳算法的任務調度算法，能夠實現較低的復雜度前提下優化調度長度和平均調度長度比等多項指標。

近年來，Xiao X.R.等[15]在異構系統上探究了能耗約束條件下并行應用的調度長度最小化問題，并提出了能耗約束下最小化調度長度（minimum schedule length with energy consumption constraint，MSLECC）算法。其主要思想是將工作流的總能耗約束傳遞給每個任務，從而使得調度過程中的關注點轉移到每個任務，然后以啟發式的調度方法最小化工作流的調度長度。MSLECC 算法具有良好的性能，但MSLECC 算法在能耗預分配階段直接為每個未調度任務分配了其最小能耗，這種預分配方法雖能滿足總能耗約束條件，但公平性欠佳，任務集的調度長度并不樂觀。因此，需要設計一種高效的調度算法以減少調度長度。

基于此，本文提出預算等級（budget level，BL）分配機制這一全新的概念，將應用程序的能耗約束合理地傳遞給每個任務。BL 分配機制不再使用最小能量預分配方法分配任務的能耗約束，而是根據任務自身能耗水平作為一種智能權重分攤能耗，避免因任務優先級敏感而使能耗分配不公。本文基于這一分配策略提出了能耗約束下最小化調度長度算法（minimizing scheduling length under energy constraints based on budget level，BLMSL），能在能耗約束條件下取得較小的調度長度，減少任務優先級對能耗分配的影響。

2 基本模型

2.1 應用模型

本文應用的一個典型工作流圖如圖1所示。

圖1 一個典型的工作流圖Fig.1 A typical workflow diagram

本文的目標計算平臺由一組計算、存儲能力各異的VM組成，VM資源池用VM={vm1,vm2,…,vm|VM|}表示，其中|VM|為虛擬機的數量。并行應用任務集（directed acyclic graph，DAG）通常使用有向無循環圖G=(N,E,C,W)表示，其中N為G中任務τi集合，即τi∈N。E表示G中直接相連兩任務節點的通信邊集合，每條邊ei,j∈E表示連接任務τi和任務τj的通信邊。C為直接相連兩節點間通信邊的時間開銷集合。若τi和τj分配給不同VM，ci,j為τi和τj間的通信時間。W為任務在不同VM上執行的通信成本集合的矩陣，wi,k表示任務τi分配在vmk上執行時所需的計算開銷。

對于G中任意直接相連的兩個任務節點τi和τj，ei,j∈E表示只有當任務τi執行完畢，并且任務τj執行所依賴的所有數據準備就緒，τj才可被執行。在給定的DAG 中，沒有前置任務的任務為入口節點，記做τentry；沒有后續任務的任務為出口節點，記做τexit。表1 顯示圖1所示DAG 中各任務在不同VM上的計算開銷。

表1 任務的計算開銷Table 1 Task calculation cost

2.2 功率和能耗模型

DVFS 基于電源電壓與工作頻率的線性關系，依靠降低頻率減小電源電壓，達到節能的目的。本文假設一個支持DVFS 的系統，采用廣泛使用的系統級功率模型為HCS 建模，能耗表達式為

式中：φs為靜態功率，其主要包括維持電路工作的基本消耗及存儲器休眠狀態時的能量開銷，系統在打開或關閉時，相關的開銷較大，使得φs始終處于消耗狀態；φind+φd表示動態功率，其中φind為與頻率無關的動態功率，只有通過關閉整個系統的電源才能消除；h為系統狀態，指示當前系統是否消耗動態功率（系統處于激活狀態時，h=1；系統處于關閉狀態時，h=0）；φd為系統動態能量消耗，為與頻率相關的動態功耗，通常表示為

式中：Ceff為有效負載電容；Vdd為供應電壓；為時鐘頻率。

當系統以較小的頻率運行時，由于φind的存在，系統總能耗的減少并不明顯，因此存在最低節能頻率，其表達式為

由于系統中VM的異構性，本文定義以下集合：與頻率相關的動態功率φd集合，

與頻率無關的動態功率φind集合，

有效電容Ceff的集合，

實際有效頻率的集合，

其中，

3 BLMSL 算法

3.1 相關知識

為了便于理解，本文進行如下定義。

定義3調度長度（SL）是并行應用集從入口任務開始執行，到出口任務執行完畢所花費的總時間，即出口任務的實際完成時間與入口任務的實際開始時間的差值，可表示為

式中AST(τentry)為入口任務的實際開始時間。

3.2 問題描述

本文所研究的問題是在滿足用戶能耗約束的條件下，針對用戶提交的工作流任務圖，以最少的時間完成調度，提高用戶服務質量。即在不超過能耗約束的條件下，為每個任務分配具有適當頻率的可用VM，同時使得DAG 應用程序的調度長度最小。

能耗約束下并行應用的調度長度最小化問題可以形式化表示如下：

式中：E(G)為工作流所消耗的實際能量；Ebdgt(G)為工作流的預算能耗約束。

由于工作流總能量是所有任務能量之和，工作流的最小能量值Emin(G)和最大能量值Emax(G)可表示為

任務τi的最小能耗Emin(τi)和最大能耗Emax(τi)分別以最小和最大頻率遍歷所有的VM獲得，其表達式如下：

3.3 任務優先級

在將任務分配給VM之前，首先需要確定任務調度的順序。

定義4向上優先等級。在任務的優先依賴關系條件下，并行應用任務集的向上優先等級自DAG 任務集的出口節點開始遞歸向上進行計算，記為ζ。任務τi的ζ值等于其后繼任務與τi之間的通信成本之和的最大值加上其在所有VMs上的平均計算成本，其計算表達式如下：

式中：wi為任務τi的平均執行時間，可通過式（17）計算：

同理，任務τi的向下優先等級(τi)的計算表達式如下：

3.4 能耗預分配

定義5可改進能量。在用戶給定能耗約束且當前工作流的最小能耗已知時，工作流的可改進能量Eadv(G)表達式如下：

定義6預算等級（BL）。工作流能耗的可支配部分將按照每個任務不同的BL等級進行分配，任務的BL計算如下：

工作流中任務τi初始給定的BL預算等級能耗EBL(τi)由其預算等級BL和最小能耗等因素決定，其計算式如下：

在極端情況下，任務的預分配能耗也始終不能超過其能耗上限，因此任務的預分配能耗Ebdgt(τi)應滿足：

設定一個等待調度的并行應用任務集Seq(G)，該任務集按照ζ值降序排列的調度序列為{τs(1),τs(2),…,τs(|N|)}，設定當前的待調度任務為τseq(j)，則{τs(1),τs(2),…,τs(j-1)}表示已調度完成的任務集合；{τs(j+1),τs(j+2),…,τs(|N|)}為未被調度的任務集合，此時任務集的總能耗為：

工作流的實際總能耗必須小于等于其能耗約束，即Eseq(j)(G)≤Ebdgt(G)。可以得到：

根據式（24）可得出將任務集總能耗約束分攤給每個單獨任務的方法，則序列中當前待調度任務的能耗約束為：

式（25）使任務集總能耗約束傳遞給每個任務，并降低了算法時間及復雜度。

3.5 調度長度最小化算法

具有能耗約束的工作流調度長度最小化算法（BLMSL）的偽代碼如算法1所示。

步驟1 計算任務集中所有任務的ζ值和值，這是BL預分配策略的基礎，并根據ζ值降序排列得到任務的調度隊列。步驟3 計算每個任務的BL值和所能消耗的最小和最大能量。步驟4～5 計算工作流的最小最大能耗以及可改進能耗Eadv(G)，并根據可改進能耗計算出任務的Ebdgt(τi)。步驟10～27 將任務依次出隊進行調度，確定每個任務的能耗約束Egiven(τi)，并選擇該能耗約束下具有最小調度長度的VM和頻率組合。其中步驟13～26 為隊列中的任務選擇合適的VM與頻率，直至隊列中所有任務均完成調度。步驟29 和30 分別統計工作流的實際總消耗能量Eact(G)和調度長度SL(G)。

遍歷任務隊列中的所有任務的時間消耗為O(N)，對于就緒任務隊列中的每個任務，遍歷所有VM和頻率組合為其選擇滿足能耗約束且具有最小EFT的VM的時間復雜度為O(|N|×|VM|×|F|)，其中|F|表示從k,low 到k,max的離散頻率數量。因此，可以得出BLMSL 算法的時間復雜度為O(|N|2×|VM|×|F|)。

算法1BLMSL 調度算法

輸入：G=(N,E,C,W)，VM，Egiven(G)；

輸出：E(G)，SL(G)。

2:fori←1 to|N|do；

3:計算Emin(τi) 、Emax(τi)和BL(τi)；

4:計算工作流圖的Emin(G)、Emax(G)；

5:計算工作流圖的Eadv(G)；

6:end for

7:fori←1 to|N|do

8:計算EBL(τi)和Ebdgt(τi)；

9:工作流圖G根據節點的ζ值降序排列得到任務優先隊列Seq(G)

10:while 隊列Seq(G)非空

11:τtmp= 隊頭節點

12:計算Egiven(τi)；

13:for eachvmk∈VMdo

15:計算Eact(τi,vmk,k,h)；

16:ifEact(τi,vmk,k,h) ＞Egiven(τi) then

17:continue；

18:end if

19:計算Eact(τi,vmk,k,h)；

20:ifEFT(τi,vmk,k,h)＜AFT(τi)

21:vmpr(i)←vmkandpr(i),hz(i)←k,h

22:Eact(τi,vmpr(i),pr(i),hz(i)) ←E(τi,vmk,k,h)

23:AFT(τi) ←EFT(τi,vmk,k,h)

24:end if

25:end for

26:end for

27:end while

28:end for

29:計算Eact(G)；

30:計算SL(G) ←AFT(τexit)；

31:returnE(G)，SL(G)

3.6 調度實例分析

本節使用圖1 中的DAG 圖來進行本文實驗，表2 列出了VM的相關參數，如動態功率、有效開關電容和動態功率指數等。能耗約束值Ebdgt(G)設置為Emax(G)×λ，λ的取值為0.5。當MSLECC 算法使用表2所示參數的VM調度圖1 中的任務集時，其總調度長度是129.525 6。

表2 VM 的功率參數Table 2 VM power parameters

在相同配置的情況下，表3 顯示了BLMSL 算法在圖1所示的任務集中總調度長度為85.852 4，所消耗能耗為71.739 2。相比MSLECC 算法，BLMSL 算法的調度長度減少了33.73%，能量消耗減少了9.04%，使得工作流的調度長度和能耗都得到優化。

表3 使用BLMSL 算法在圖1所示的并行應用分配結果Table 3 Parallel application allocation results as shown in Fig.1 using BLMSL algorithm

使用BLMSL 算法調度圖1 中任務集的結果如圖2所示，調度長度為85.852 4。

圖2 BLMSL 算法的調度效果圖Fig.2 Scheduling effect diagram of BLMSL algorithm

4 實驗結果及分析

本節進行了多組實驗來對比觀察BLMSL 算法相較于其它先進算法的性能。首先介紹實驗設置，然后給出實驗結果及分析。

4.1 實驗設置

實驗中工作站配置了Intel Core(TM) i5-9300H@2.40GHz 八核處理器，16 GB 內存，系統運行版本為Windows10，采用Python 作為實驗的編程語言。模擬的HCS 具有64 個計算能力和單價各異的VM。VM的主要參數如下：10 ms ≤wi,k≤100 ms，10 ms ≤ci,j≤100 ms，0.03 ≤Pk,ind≤0.07，2.5 ≤mk≤3.0，k,max=1.0 GHz。所有的頻率均為離散值，精度為0.01 GHz。

HEFT 算法是異構系統上以減少調度長度為目標的經典算法，MSLECC 算法與本文的工作均為在考慮能耗約束的前提下最小化調度長度，因此選擇這兩種算法作為實驗中的對比算法。這3 種算法的研究目標均是最小化工作流的調度長度。

本文的實驗使用實際的能耗E(G)和最終的調度長度SL(G)作為算法性能的評價指標，使用高性能計算領域中廣泛使用的真實應用并行任務集進行測試，通過改變應用規模的大小和能耗約束的大小來更直觀地說明BLMSL 算法的有效性。

4.2 Epigenomics 工作流應用

本節選擇生物遺傳學領域的表觀基因組學Epigenomics作為測試的工作流結構，下文中簡稱EP，其科學工作流應用程序的結構如圖3所示。

圖3 Epigenomics工作流結構圖Fig.3 Epigenomics workflow structure diagram

實驗一。本組實驗工作流的能耗約束固定為0.5（即Egiven(G)=Emax(G)×0.5）， 將EP 應用的規模分別設置為19,51,103,523,1 003，隨后比較在不同任務數量時不同算法的實際能量消耗和調度長度。MSLECC 算法和BLMSL 算法在所有的實驗案例中都能在滿足能耗約束的前提下成功進行調度，而由于HEFT 算法不考慮功耗約束，雖然實現了較小的調度長度，但其能耗未能滿足能量約束條件。

表4 展示了3 種算法在不同任務數量下的實際能耗和調度長度。隨著工作流應用程序規模擴大，能耗和調度長度隨之增大。相比HEFT 和MSLECC 算法，BLMSL 能夠保證在滿足能耗約束的條件下，獲得較小的調度長度，在應用規模為N=1 003 且消耗能量基本相同的情況下，BLMSL 算法相比MSLECC 算法調度長度減少了約63.22%，體現了其在調度長度最小化方面的巨大優越性。

表4 不同應用規模下的EP 工作流調度結果Table 4 EP workflow scheduling results under different application scales

圖4 展示了3 種算法在不同任務數量的EP 應用下的調度長度結果，發現BLMSL 算法在滿足能耗約束條件下，實現了較其他算法更小的調度長度。

圖4 不同任務數的SL 對比Fig.4 SL comparison of with different task numbers

4.3 Inspiral 工作流應用

本組實驗采用重力物理學領域的LIGO 科學工作流，其結構如圖5所示。

圖5 Inspiral 工作流結構圖Fig.5 Inspiral workflow structure digram

實驗二。將實驗的應用規模固定為94，能耗約束值Egiven(G)計算為Emin(G)×λ，λ的取值從2 到4，取值間隔為0.5。

詳細調度結果見表5，當給定能耗較寬松時，工作流中任務能利用更寬松能量實現更小調度長度，λ=4.0，BLMSL 算法在滿足能耗約束條件下，實際調度長度和HEFT 算法僅相差3.72%，而能量消耗卻比HEFT 算法節省13.47%。當并行應用任務集給定能耗較小時，BLMSL 算法的優越性更突出，如λ=2 時，BLMSL算法實際調度長度比MSLECC 算法提升了76.49%。

表5 不同能耗約束條件下的LIGO 工作流調度結果Table 5 LIGO workflow scheduling results under different energy consumption constraints

圖6 顯示了不同能耗約束的LIGO 應用下3 種算法的調度長度結果。從圖中可以觀察出，BLMSL算法在給定能耗條件變化較大的環境下依然能保持調度長度的相對穩定。且在不同能耗約束條件下，BLMSL 算法的最終調度長度值始終小于MSLECC算法的調度長度值。

圖6 不同能耗約束LIGO 的SL 對比Fig.6 SL comparison of LIGO with different energy consumption constraints

由以上結果可看出，BLMSL 算法能夠同時兼顧工作流的能耗和調度長度兩方面，實現性能平衡。通過觀察在LIGO 和EP 并行應用科學工作流上進行的諸多實驗，充分說明BLMSL 算法在兩個科學工作流上的實驗中始終保持著優越的性能。

5 結語

針對HCS 中能量受限并行應用的調度長度最小化問題，本文設計了BL等級預分配機制，并基于BL等級預分配策略提出了BLMSL 算法來實現算法的調度長度最小化，提升了能耗預分配階段的合理性和科學性，避免了因對任務優先級敏感而影響調度長度問題。在多個科學工作流上進行實驗的結果表明，BLMSL 算法能在能耗約束的條件下實現更小的調度長度。未來，課題組將致力于探索云環境中工作流集在預算約束下的高可靠性研究方法。