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

（湖南工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，湖南 株洲 412007）

1 研究背景

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

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

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

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

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

2 基本模型

2.1 應(yīng)用模型

本文應(yīng)用的一個(gè)典型工作流圖如圖1所示。

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

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

對(duì)于G中任意直接相連的兩個(gè)任務(wù)節(jié)點(diǎn)τi和τj，ei,j∈E表示只有當(dāng)任務(wù)τi執(zhí)行完畢，并且任務(wù)τj執(zhí)行所依賴的所有數(shù)據(jù)準(zhǔn)備就緒，τj才可被執(zhí)行。在給定的DAG 中，沒有前置任務(wù)的任務(wù)為入口節(jié)點(diǎn)，記做τentry；沒有后續(xù)任務(wù)的任務(wù)為出口節(jié)點(diǎn)，記做τexit。表1 顯示圖1所示DAG 中各任務(wù)在不同VM上的計(jì)算開銷。

表1 任務(wù)的計(jì)算開銷Table 1 Task calculation cost

2.2 功率和能耗模型

DVFS 基于電源電壓與工作頻率的線性關(guān)系，依靠降低頻率減小電源電壓，達(dá)到節(jié)能的目的。本文假設(shè)一個(gè)支持DVFS 的系統(tǒng)，采用廣泛使用的系統(tǒng)級(jí)功率模型為HCS 建模，能耗表達(dá)式為

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

式中：Ceff為有效負(fù)載電容；Vdd為供應(yīng)電壓；為時(shí)鐘頻率。

當(dāng)系統(tǒng)以較小的頻率運(yùn)行時(shí)，由于φind的存在，系統(tǒng)總能耗的減少并不明顯，因此存在最低節(jié)能頻率，其表達(dá)式為

由于系統(tǒng)中VM的異構(gòu)性，本文定義以下集合：與頻率相關(guān)的動(dòng)態(tài)功率φd集合，

與頻率無關(guān)的動(dòng)態(tài)功率φind集合，

有效電容Ceff的集合，

實(shí)際有效頻率的集合，

其中，

3 BLMSL 算法

3.1 相關(guān)知識(shí)

為了便于理解，本文進(jìn)行如下定義。

定義3調(diào)度長度（SL）是并行應(yīng)用集從入口任務(wù)開始執(zhí)行，到出口任務(wù)執(zhí)行完畢所花費(fèi)的總時(shí)間，即出口任務(wù)的實(shí)際完成時(shí)間與入口任務(wù)的實(shí)際開始時(shí)間的差值，可表示為

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

3.2 問題描述

本文所研究的問題是在滿足用戶能耗約束的條件下，針對(duì)用戶提交的工作流任務(wù)圖，以最少的時(shí)間完成調(diào)度，提高用戶服務(wù)質(zhì)量。即在不超過能耗約束的條件下，為每個(gè)任務(wù)分配具有適當(dāng)頻率的可用VM，同時(shí)使得DAG 應(yīng)用程序的調(diào)度長度最小。

能耗約束下并行應(yīng)用的調(diào)度長度最小化問題可以形式化表示如下：

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

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

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

3.3 任務(wù)優(yōu)先級(jí)

在將任務(wù)分配給VM之前，首先需要確定任務(wù)調(diào)度的順序。

定義4向上優(yōu)先等級(jí)。在任務(wù)的優(yōu)先依賴關(guān)系條件下，并行應(yīng)用任務(wù)集的向上優(yōu)先等級(jí)自DAG 任務(wù)集的出口節(jié)點(diǎn)開始遞歸向上進(jìn)行計(jì)算，記為ζ。任務(wù)τi的ζ值等于其后繼任務(wù)與τi之間的通信成本之和的最大值加上其在所有VMs上的平均計(jì)算成本，其計(jì)算表達(dá)式如下：

式中：wi為任務(wù)τi的平均執(zhí)行時(shí)間，可通過式（17）計(jì)算：

同理，任務(wù)τi的向下優(yōu)先等級(jí)(τi)的計(jì)算表達(dá)式如下：

3.4 能耗預(yù)分配

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

定義6預(yù)算等級(jí)（BL）。工作流能耗的可支配部分將按照每個(gè)任務(wù)不同的BL等級(jí)進(jìn)行分配，任務(wù)的BL計(jì)算如下：

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

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

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

工作流的實(shí)際總能耗必須小于等于其能耗約束，即Eseq(j)(G)≤Ebdgt(G)?？梢缘玫剑?/p>

根據(jù)式（24）可得出將任務(wù)集總能耗約束分?jǐn)偨o每個(gè)單獨(dú)任務(wù)的方法，則序列中當(dāng)前待調(diào)度任務(wù)的能耗約束為：

式（25）使任務(wù)集總能耗約束傳遞給每個(gè)任務(wù)，并降低了算法時(shí)間及復(fù)雜度。

3.5 調(diào)度長度最小化算法

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

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

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

算法1BLMSL 調(diào)度算法

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

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

2:fori←1 to|N|do；

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

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

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

6:end for

7:fori←1 to|N|do

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

9:工作流圖G根據(jù)節(jié)點(diǎn)的ζ值降序排列得到任務(wù)優(yōu)先隊(duì)列Seq(G)

10:while 隊(duì)列Seq(G)非空

11:τtmp= 隊(duì)頭節(jié)點(diǎn)

12:計(jì)算Egiven(τi)；

13:for eachvmk∈VMdo

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

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

17:continue；

18:end if

19:計(jì)算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:計(jì)算Eact(G)；

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

31:returnE(G)，SL(G)

3.6 調(diào)度實(shí)例分析

本節(jié)使用圖1 中的DAG 圖來進(jìn)行本文實(shí)驗(yàn)，表2 列出了VM的相關(guān)參數(shù)，如動(dòng)態(tài)功率、有效開關(guān)電容和動(dòng)態(tài)功率指數(shù)等。能耗約束值Ebdgt(G)設(shè)置為Emax(G)×λ，λ的取值為0.5。當(dāng)MSLECC 算法使用表2所示參數(shù)的VM調(diào)度圖1 中的任務(wù)集時(shí)，其總調(diào)度長度是129.525 6。

表2 VM 的功率參數(shù)Table 2 VM power parameters

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

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

使用BLMSL 算法調(diào)度圖1 中任務(wù)集的結(jié)果如圖2所示，調(diào)度長度為85.852 4。

圖2 BLMSL 算法的調(diào)度效果圖Fig.2 Scheduling effect diagram of BLMSL algorithm

4 實(shí)驗(yàn)結(jié)果及分析

本節(jié)進(jìn)行了多組實(shí)驗(yàn)來對(duì)比觀察BLMSL 算法相較于其它先進(jìn)算法的性能。首先介紹實(shí)驗(yàn)設(shè)置，然后給出實(shí)驗(yàn)結(jié)果及分析。

4.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)中工作站配置了Intel Core(TM) i5-9300H@2.40GHz 八核處理器，16 GB 內(nèi)存，系統(tǒng)運(yùn)行版本為Windows10，采用Python 作為實(shí)驗(yàn)的編程語言。模擬的HCS 具有64 個(gè)計(jì)算能力和單價(jià)各異的VM。VM的主要參數(shù)如下：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 算法是異構(gòu)系統(tǒng)上以減少調(diào)度長度為目標(biāo)的經(jīng)典算法，MSLECC 算法與本文的工作均為在考慮能耗約束的前提下最小化調(diào)度長度，因此選擇這兩種算法作為實(shí)驗(yàn)中的對(duì)比算法。這3 種算法的研究目標(biāo)均是最小化工作流的調(diào)度長度。

本文的實(shí)驗(yàn)使用實(shí)際的能耗E(G)和最終的調(diào)度長度SL(G)作為算法性能的評(píng)價(jià)指標(biāo)，使用高性能計(jì)算領(lǐng)域中廣泛使用的真實(shí)應(yīng)用并行任務(wù)集進(jìn)行測試，通過改變應(yīng)用規(guī)模的大小和能耗約束的大小來更直觀地說明BLMSL 算法的有效性。

4.2 Epigenomics 工作流應(yīng)用

本節(jié)選擇生物遺傳學(xué)領(lǐng)域的表觀基因組學(xué)Epigenomics作為測試的工作流結(jié)構(gòu)，下文中簡稱EP，其科學(xué)工作流應(yīng)用程序的結(jié)構(gòu)如圖3所示。

圖3 Epigenomics工作流結(jié)構(gòu)圖Fig.3 Epigenomics workflow structure diagram

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

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

表4 不同應(yīng)用規(guī)模下的EP 工作流調(diào)度結(jié)果Table 4 EP workflow scheduling results under different application scales

圖4 展示了3 種算法在不同任務(wù)數(shù)量的EP 應(yīng)用下的調(diào)度長度結(jié)果，發(fā)現(xiàn)BLMSL 算法在滿足能耗約束條件下，實(shí)現(xiàn)了較其他算法更小的調(diào)度長度。

圖4 不同任務(wù)數(shù)的SL 對(duì)比Fig.4 SL comparison of with different task numbers

4.3 Inspiral 工作流應(yīng)用

本組實(shí)驗(yàn)采用重力物理學(xué)領(lǐng)域的LIGO 科學(xué)工作流，其結(jié)構(gòu)如圖5所示。

圖5 Inspiral 工作流結(jié)構(gòu)圖Fig.5 Inspiral workflow structure digram

實(shí)驗(yàn)二。將實(shí)驗(yàn)的應(yīng)用規(guī)模固定為94，能耗約束值Egiven(G)計(jì)算為Emin(G)×λ，λ的取值從2 到4，取值間隔為0.5。

詳細(xì)調(diào)度結(jié)果見表5，當(dāng)給定能耗較寬松時(shí)，工作流中任務(wù)能利用更寬松能量實(shí)現(xiàn)更小調(diào)度長度，λ=4.0，BLMSL 算法在滿足能耗約束條件下，實(shí)際調(diào)度長度和HEFT 算法僅相差3.72%，而能量消耗卻比HEFT 算法節(jié)省13.47%。當(dāng)并行應(yīng)用任務(wù)集給定能耗較小時(shí)，BLMSL 算法的優(yōu)越性更突出，如λ=2 時(shí)，BLMSL算法實(shí)際調(diào)度長度比MSLECC 算法提升了76.49%。

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

圖6 顯示了不同能耗約束的LIGO 應(yīng)用下3 種算法的調(diào)度長度結(jié)果。從圖中可以觀察出，BLMSL算法在給定能耗條件變化較大的環(huán)境下依然能保持調(diào)度長度的相對(duì)穩(wěn)定。且在不同能耗約束條件下，BLMSL 算法的最終調(diào)度長度值始終小于MSLECC算法的調(diào)度長度值。

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

由以上結(jié)果可看出，BLMSL 算法能夠同時(shí)兼顧工作流的能耗和調(diào)度長度兩方面，實(shí)現(xiàn)性能平衡。通過觀察在LIGO 和EP 并行應(yīng)用科學(xué)工作流上進(jìn)行的諸多實(shí)驗(yàn)，充分說明BLMSL 算法在兩個(gè)科學(xué)工作流上的實(shí)驗(yàn)中始終保持著優(yōu)越的性能。

5 結(jié)語

針對(duì)HCS 中能量受限并行應(yīng)用的調(diào)度長度最小化問題，本文設(shè)計(jì)了BL等級(jí)預(yù)分配機(jī)制，并基于BL等級(jí)預(yù)分配策略提出了BLMSL 算法來實(shí)現(xiàn)算法的調(diào)度長度最小化，提升了能耗預(yù)分配階段的合理性和科學(xué)性，避免了因?qū)θ蝿?wù)優(yōu)先級(jí)敏感而影響調(diào)度長度問題。在多個(gè)科學(xué)工作流上進(jìn)行實(shí)驗(yàn)的結(jié)果表明，BLMSL 算法能在能耗約束的條件下實(shí)現(xiàn)更小的調(diào)度長度。未來，課題組將致力于探索云環(huán)境中工作流集在預(yù)算約束下的高可靠性研究方法。