殷 越 隋麗娜

1(河南工業(yè)和信息化職業(yè)學(xué)院信息工程系 河南 焦作 454003) 2(河北民族師范學(xué)院數(shù)學(xué)與計算機科學(xué)學(xué)院 河北 承德 067000)

0 引 言

云計算[1]可以將分布于世界各地的互聯(lián)網(wǎng)上的各種IT資源(計算、存儲、帶寬等)進行有效的整合，然后通過虛擬化技術(shù)以實時按需的形式提供給用戶使用。云計算中的任務(wù)調(diào)度問題就是要實現(xiàn)任務(wù)與資源間的有效映射，在滿足用戶定義的時間或費用的約束下獲得滿足服務(wù)質(zhì)量要求的調(diào)度解[2]。尤其是將科學(xué)工作流模型應(yīng)用于云計算調(diào)度時，由于工作流結(jié)構(gòu)的復(fù)雜性以及工作流中任務(wù)頂點間的相互關(guān)聯(lián)性和依賴性，此時的調(diào)度算法將更為直接地影響任務(wù)調(diào)度的成功率[3]。

云計算環(huán)境中的科學(xué)工作流應(yīng)用通常表現(xiàn)為海量數(shù)據(jù)密集型任務(wù)處理，主要特點表現(xiàn)為[4]：1) 任務(wù)提交與計算過程動態(tài)多變，通常是一種有向無環(huán)圖DAG結(jié)構(gòu)；2) 對調(diào)度可靠性要求更高，需要有效地滿足調(diào)度可靠性機制，以提高調(diào)度成功率；3) 任務(wù)調(diào)度導(dǎo)致資源提供方的能耗加劇，任務(wù)調(diào)度過程中需要考慮能效調(diào)度機制。綜合以上三點考慮，在大規(guī)模云系統(tǒng)中，工作流調(diào)度還需要考慮能效和可靠性問題。同時，為了實現(xiàn)可靠性工作流調(diào)度，需要重點解決：1) 如何量化任力調(diào)度時可靠性；2) 如何尋找滿足最大化可靠性和最大能效的調(diào)度方案。

為了同步解決工作流調(diào)度的能效和可靠性問題，本文將設(shè)計一種新的工作流調(diào)度算法REEWS，將通過一種多階段式的調(diào)度求解過程，得到了最優(yōu)任務(wù)調(diào)度解。

1 相關(guān)工作

文獻(xiàn)[5]通過賦予任務(wù)不同優(yōu)先級，設(shè)計了異構(gòu)最快完成時間調(diào)度算法HEFT，從而實現(xiàn)了任務(wù)調(diào)度時間最小化。文獻(xiàn)[6]對HEFT算法進行了擴展，提出了一種基于失效約束的異構(gòu)最快完成時間算法RHEFT，該算法將失效率與單個指令執(zhí)行時間的乘積考慮至工作流調(diào)度中，以此作為映射任務(wù)的標(biāo)準(zhǔn)，并最大化系統(tǒng)的可靠性。文獻(xiàn)[7]提出一種異構(gòu)預(yù)算約束調(diào)度算法HBCS，通過定義代價因子調(diào)整可用預(yù)算與最低廉價格可能性的比例，實現(xiàn)調(diào)度優(yōu)化。HEFT、RHEFT和HBCS均是以調(diào)度長度為單目標(biāo)進行最優(yōu)化，忽略了調(diào)度可靠性問題。文獻(xiàn)[8]在考慮任務(wù)優(yōu)先序列并結(jié)合復(fù)制的思想，提出基于可靠性的工作流調(diào)度算法CRB，算法可以有效實現(xiàn)執(zhí)行時間與執(zhí)行失敗率的同步降低，提高整體可靠性。文獻(xiàn)[9]同步考慮工作流的安全需求問題，在滿足用戶時間和成本約束的基礎(chǔ)上，設(shè)計了安全約束算法PALS，并利用變近鄰PSO對工作流調(diào)度最優(yōu)化問題進行了求解，實現(xiàn)了尋優(yōu)能力較強的可靠性調(diào)度。遺傳算法GA是求解工作流調(diào)度多目標(biāo)優(yōu)化的另一種有效方法，文獻(xiàn)[10]提出的雙目標(biāo)調(diào)度算法BGA同樣是以執(zhí)行跨度和可靠性作為優(yōu)化目標(biāo)，但算法執(zhí)行過程中會違背任務(wù)依賴性并可能產(chǎn)生無效解。同時，傳統(tǒng)的遺傳算法對調(diào)度解的進化均是隨機進行的，這會導(dǎo)致遺傳尋優(yōu)收斂速度較慢。綜合分析，目前基于可靠性的云工作流調(diào)度算法的相關(guān)研究問題在于：1)從云資源方來看，工作流調(diào)度成功與否僅以任務(wù)成功率評估資源信譽度，忽略了資源在執(zhí)行任務(wù)時因為時鐘頻率帶來的任務(wù)執(zhí)行不穩(wěn)定性；2)對于任務(wù)本身而言，已有模型基于信譽度為任務(wù)分配相同可靠性，忽略了任務(wù)本身的差異性，以及在不可靠資源上執(zhí)行時間越長，其成功率就越低的情況。

本文提出的算法目標(biāo)是在維持任務(wù)依賴約束以及用戶定義的截止時間期限約束的前提下，最小化工作流執(zhí)行能耗和最大化調(diào)度可靠性。由于云計算環(huán)境的復(fù)雜性，物理硬件上的缺陷和溫度過高的環(huán)境因素導(dǎo)致的系統(tǒng)失效是不可避免的，此時失效率極大地依賴于系統(tǒng)的運行頻率和電壓。然而，即使運行在最小頻率也不能帶來最小的失效到達(dá)率。因此，算法的目標(biāo)是為處理器分配合適的電壓/頻率等級用于就緒任務(wù)的執(zhí)行，使得任務(wù)執(zhí)行的可靠性達(dá)到最優(yōu)并耗能最少。

2 系統(tǒng)模型

2.1 云計算系統(tǒng)模型

云計算系統(tǒng)由m個異構(gòu)物理主機PM集合組成，主機CPU均配置有動態(tài)電壓/頻率調(diào)整DVFS功能。假設(shè)每個PM/處理器提供k個頻率等級(f1,f2,…,fk)，即可運行于不同的頻率和電壓等級，且忽略CPU進行頻率轉(zhuǎn)換的開銷。處理元素間通過通信鏈路相連，通信鏈路間的通信帶寬相同，且處理器之間的通信是完全可靠的。主機PM可通過虛擬化技術(shù)虛擬成若干臺虛擬機進行任務(wù)調(diào)度。每臺虛擬機也與主機一樣可運行于不同的頻率。對于這種由異構(gòu)物理主機構(gòu)成的云計算系統(tǒng)模型，每一個可用的物理主機在進行工作流任務(wù)調(diào)度時均可以作為任務(wù)調(diào)度的選擇目標(biāo)，并根據(jù)物理主機的CPU處理能力和資源分配狀態(tài)進行任務(wù)調(diào)度目標(biāo)的映射求解，比較適用于科學(xué)工作流場景下需滿足能效的任務(wù)調(diào)度環(huán)境。

2.2 應(yīng)用模型

通常，工作流應(yīng)用是一種任務(wù)間具有關(guān)聯(lián)性的并行應(yīng)用模型，可定義為有向無環(huán)圖DAG模型，表示為G(T,E)。該模型可以明確工作流結(jié)構(gòu)中所有任務(wù)間的偏序關(guān)系，即前驅(qū)與后繼關(guān)系，以此約束任務(wù)間的執(zhí)行次序。T代表n個任務(wù)集合，ti∈T，1≤i≤n，E代表有向邊集合，任務(wù)ti與任務(wù)tj之間的有向邊ei,j∈E，1≤i≤n，1≤j≤n，i≠j。此時，任務(wù)ti是任務(wù)tj的父任務(wù)parent，任務(wù)tj是任務(wù)ti的子任務(wù)child。兩個任務(wù)間的邊的權(quán)重w(eij)代表任務(wù)ti與任務(wù)tj之間的數(shù)據(jù)傳輸量(只考慮在兩個任務(wù)調(diào)度至不同物理主機上執(zhí)行時)，每個任務(wù)分配一個權(quán)重w(ti)，代表任務(wù)的計算代價，即執(zhí)行該特定任務(wù)時的指令數(shù)量，單位為百萬指令數(shù)MI。

若任務(wù)滿足parent(ti)=?，即任務(wù)沒有父任務(wù)，則該任務(wù)為工作流的入口任務(wù)；若任務(wù)滿足child(ti)=?，即任務(wù)沒有子任務(wù)，則該任務(wù)為工作流的出口任務(wù)。工作流結(jié)構(gòu)中的入口任務(wù)與出口任務(wù)在有向無環(huán)圖中可以被明確表示，并且根據(jù)有向無環(huán)圖模型，工作流調(diào)度算法設(shè)計中對于任務(wù)的調(diào)度選擇也更加明確。本文相關(guān)符號說明如表1所示。計算代價w(ti)給出任務(wù)在任一主機上的執(zhí)行時間ET，即ETi=w(ti)×CPI/fr,max，其中：fr,max表示任務(wù)執(zhí)行時間處理元素的最大頻率；CPI表示特定主機每個指令的CPU執(zhí)行周期。兩個關(guān)聯(lián)任務(wù)間的通信時間CTij=w(eij)/bw(pmr,pms)，其中，bw(pmr,pms)代表通信鏈路的帶寬，單位為Mbit/s。當(dāng)兩個任務(wù)執(zhí)行于同一主機時，通信時間為0。此外，還有兩個重要屬性如下：

估計開始時間ESTi：代表任務(wù)ti在任一主機pmr上的開始時間，定義為：

(1)

式中：tp表示任務(wù)ti的父任務(wù)。

估計完成時間EFTi：代表任務(wù)ti在任一主機pmr上的完成時間，定義為：

EFTi=ESTi+ETi

(2)

表1 符號說明

2.3 功耗模型

云數(shù)據(jù)中心中，服務(wù)器的功耗主要由CPU、內(nèi)存、磁盤存儲器和網(wǎng)絡(luò)接口構(gòu)成。比較其他的系統(tǒng)資源，CPU消耗了最多的能源。本文將采用以下的功耗等式模型：

P=Ps+h(Pind+Pd)

(3)

式中：Ps表示靜態(tài)功耗；Pind表示與頻率無關(guān)的功耗部分；Pd表示動態(tài)功耗，與運行頻率相關(guān)。

靜態(tài)功耗Ps當(dāng)系統(tǒng)處于開啟狀態(tài)時就會存在。該功耗維持時鐘為活躍狀態(tài)和內(nèi)存處于休眠狀態(tài)。參數(shù)Pind為常量功耗，在維持系統(tǒng)備用的情況下可降低至最小值。對于計算密集型任務(wù)類型，常量功耗為固定值，此時僅需要考慮動態(tài)功耗Pd，其與運行頻率間的關(guān)系為：

Pd=CeffV2f=Cefff3

(4)

式中：Ceff表示有效負(fù)載電容；V表示供電電壓；f表示運行時鐘頻率。時鐘頻率f與V成正比，若應(yīng)用任務(wù)運行于低頻率，則供電電壓會線性降低。式(3)中，h的取值決定了系統(tǒng)狀態(tài)。若h=1，則系統(tǒng)是活動狀態(tài)；否則，系統(tǒng)處于休眠狀態(tài)。由式(4)可知，頻率相關(guān)的動態(tài)功耗取決于頻率，且在滿足條件fee=3(Pind/2Ceff)-3時可得到其最小值，即能效最優(yōu)。因此，對于特定任務(wù)ti的能耗可計算為：

(5)

式中：ETi表示運行最大頻率/電壓時任務(wù)ti的執(zhí)行時間。本文所有頻率值均是根據(jù)等級設(shè)備的標(biāo)準(zhǔn)值，可對等地調(diào)整至最大值。最后，系統(tǒng)能耗為所有任務(wù)執(zhí)行能耗之和，定義為：

(6)

該功耗模型同時考慮了服務(wù)器的動態(tài)和靜態(tài)功耗，使服務(wù)器在任務(wù)調(diào)度過程中可以進行忙閑狀態(tài)切換，最大限度地節(jié)省服務(wù)器能耗。同時，主要由CPU頻率決定的能耗計算方式也可以更加準(zhǔn)確地描述計算密集型工作流任務(wù)類型的能耗狀況。

2.4 可靠性模型

應(yīng)用任務(wù)執(zhí)行過程中，硬件崩潰、軟件缺陷、機器運行的高溫等均可以導(dǎo)致系統(tǒng)永久或短暫失效。通常，短暫失效的概率遠(yuǎn)大于永久性失效。因此，本文在工作流調(diào)度過程中將考慮系統(tǒng)的短暫失效影響。通常，系統(tǒng)短暫失效服從泊松分布，而失效到達(dá)率λ則與計算節(jié)點的運行頻率相關(guān)。由于計算節(jié)點的可靠性直接關(guān)系著計算密集型任務(wù)的計算可靠性，本文將忽略存儲和網(wǎng)絡(luò)接口的影響。失效率的關(guān)系式為：

(7)

式中：fr,op表示運行頻率；λ0表示在最大頻率/電壓下的初始失效率；F(fr,op)表示頻率的嚴(yán)格遞減函數(shù)；d>0表示一個常量。由式(7)可知，當(dāng)f=fmin時失效率λ最大，即處于最小運行頻率(能耗節(jié)省最合適的頻率)時失效率最大(可靠性最小)。d值越大表明失效率更容易受到頻率/電壓擴展的影響。因此，最大化可靠性和最大化能耗節(jié)省兩個目標(biāo)本質(zhì)上是相關(guān)沖突的目標(biāo)。

最后，系統(tǒng)可靠性為未失效狀態(tài)下任務(wù)執(zhí)行的概率?？紤]在泊松分布下的失效率，任務(wù)ti(計算代價為ETi)運行于頻率fr,op下執(zhí)行的可靠性計算為：

(8)

所有工作流中n個任務(wù)的執(zhí)行可靠性為：

(9)

該可靠性模型根據(jù)泊松分布將計算節(jié)點的可靠性建立為服務(wù)器處理頻率的函數(shù)，同時結(jié)合前文的功耗模型，服務(wù)器功耗也主要由頻率決定。如此，工作流調(diào)度的可靠性和能耗的最優(yōu)化均與服務(wù)器頻率相關(guān)，即可以將最優(yōu)化模型描述為同一參數(shù)影響下的沖突式的多目標(biāo)優(yōu)化問題進行均衡求解。

2.5 問題描述

本文的目標(biāo)是將n個工作流任務(wù)調(diào)度至m個異構(gòu)主機上，在滿足任務(wù)間的執(zhí)行先后次序的基礎(chǔ)上實現(xiàn)：1) 最大化系統(tǒng)可靠性；2) 最小化系統(tǒng)能耗；3) 滿足用戶定義的截止時間QoS約束。

3 基于可靠性和能效感知的工作流調(diào)度算法

3.1 算法思想

本文提出一種基于可靠性和能效感知的工作流調(diào)度算法REEWS，實現(xiàn)云計算環(huán)境中工作流調(diào)度時的系統(tǒng)可靠性和能耗最小化。算法的主要工作由以下四個階段組成：

1) 計算任務(wù)優(yōu)先級：尋找有效的工作流任務(wù)的拓?fù)渑判?，同時滿足任務(wù)間的執(zhí)行次序。

2) 任務(wù)聚簇：將任務(wù)劃分為集合，從而最小化任務(wù)間的通信代價，進而最小化系統(tǒng)的能耗。

3) 截止時間分配：將用戶定義的截止時間QoS約束在各任務(wù)間進行子劃分。

4) 任務(wù)調(diào)度：將聚簇后的任務(wù)集調(diào)度至運行于合適頻率/電壓等級的處理器上執(zhí)行，使得系統(tǒng)的全局可靠性最大化，且最小化系統(tǒng)能耗。

3.2 REEWS算法

REEWS算法過程如算法1所示。步驟2計算任務(wù)ti的平均執(zhí)行時間ETi,avg和平均通信時間CTij,avg，步驟3計算系統(tǒng)中每個任務(wù)的最早開始時間EST和最早完成時間EFT，步驟5調(diào)用calculate_Priority(tentry)計算系統(tǒng)中每個任務(wù)的優(yōu)先級，優(yōu)先級采用自頂向下的方式從入口任務(wù)開始計算，直到出口任務(wù)。步驟6中Clustering()用于生成滿足任務(wù)間先后執(zhí)行次序的任務(wù)聚簇集，步驟7將全局截止時間分配至工作流的最后一個任務(wù)(出口任務(wù))，步驟8中Allocate(texit)設(shè)置為真以確保最后一個任務(wù)已被分配子截止時間。步驟9調(diào)用Distribute_Time(texit)進行截止時間分配，步驟10-步驟16用于調(diào)度聚簇中的任務(wù)至提供最大化可靠性的處理元素上。對于在每個處理器上的每個聚簇，步驟12檢測是否處理元素滿足該聚簇的截止時間分配值，若滿足則計算執(zhí)行頻率。步驟13計算在處理元素上聚簇中每個任務(wù)的執(zhí)行可靠性。步驟15將聚簇調(diào)度至得到最大可靠性的處理元素上執(zhí)行。

算法1REEWS-Reliability and Energy-Efficient Workflow Scheduling

Input:G(T,E) with a deadlineDand set of physical machines/processorsPM.

Output:Reliability and energy efficient schedule of workflow.

1.foreach tasktiinT

2. calculateETi,avgandCTij,avgon all processors

3. calculateESTiandEFTiby Equ.(1-2)

4.endfor

5.callcalculate_Priority(tentry)

6.cl←call Clustering(T)

7. SubD(texit) ←D

8. Allocate(texit) ←true

9.callDistribute_Time(texit)

10.foreach clustercli

11.foreach processor/physical machinepmrinPM

12. calculate energy efficient frequencyfkonpmrfortc(tc∈cli) by Equ.(5) such that it meets the SubD ofcli

13. calculate reliability oftconpmr(tc∈cli) by Equ.(8)

14.endfor

15. assignclito processing element providing maximum reliability

16.endfor

17.endprocedure

3.3 計算任務(wù)優(yōu)先級

計算任務(wù)優(yōu)先級次序可以確保關(guān)鍵任務(wù)被優(yōu)先執(zhí)行。任務(wù)優(yōu)先級即是尋找調(diào)度任務(wù)的拓?fù)渑判?，同時需要滿足任務(wù)間的先后次序。這樣，遵守任務(wù)優(yōu)先級的任務(wù)調(diào)度次序?qū)⒖隙M足不同任務(wù)間的執(zhí)行順序關(guān)系。

首先考慮出口任務(wù)texit，由于沒有任一父任務(wù)，其優(yōu)先級為平均執(zhí)行時間，進而利用該值遞推其他任務(wù)優(yōu)先級，定義為：

(10)

基于任務(wù)優(yōu)先級，任務(wù)被置入任務(wù)隊列task-list，該隊列描述了任務(wù)在分配資源時所考慮的排序，進而可以獲得滿足執(zhí)行次序的最小化調(diào)度時間。算法2是優(yōu)先級計算過程。

算法2calculate_Priority(T)

1. initialize priority of exit task,prexit←ETexit,avg

2.foreachtiin reverse order

3. calculate the priorityPrifor each task as per Equ.(10)

4.endfor

5.endprocedure

3.4 任務(wù)聚簇

當(dāng)任務(wù)被調(diào)度至不同的處理器上執(zhí)行時任務(wù)間的數(shù)據(jù)傳輸將消耗大量能量。因此，算法3可用于任務(wù)聚簇,其主要目標(biāo)是使得無相互關(guān)聯(lián)關(guān)系的任務(wù)聚成一個簇，進而消除任務(wù)的通信開銷，降低通信能耗。經(jīng)過步驟3-步驟16，系統(tǒng)中的每個任務(wù)被分配至一個聚簇中。步驟4檢測當(dāng)前任務(wù)ti是否已被分配至一個聚簇中，若沒有分配，則在步驟5中創(chuàng)建一個新的聚簇，并在步驟7中將任務(wù)添加至該新聚簇中。步驟8對任務(wù)ti的子任務(wù)進行排序，步驟9-步驟14尋找ti的一個已被添加相同聚簇的子任務(wù)。然而，僅在滿足以下兩個條件的情況下，ti的一個子任務(wù)tj才會被添加于相同聚簇中：首先，該任務(wù)必須仍未分配給任意聚簇，其次，tj的所有父任務(wù)已被分配至一個聚簇。步驟10的目標(biāo)即是檢測以上兩個條件。若檢測結(jié)果為真，則該子任務(wù)不被加至相同聚簇中。當(dāng)不再有任務(wù)被添加至先前聚簇中時，控制過程進入循環(huán)外層的迭代中創(chuàng)建新聚簇。該過程重復(fù)至所有任務(wù)均被分配至一個聚簇中為止。

算法3Clustering(T)

1. add all taskstifromTintotask_list

2.k=0

3.foreach tasktiintask_list

4.iftihas not been assigned to any clusterthen

5.k=k+1

//make a new clusterclk

6.label:

7. add tasktito clusterclk

8. sort children of taskti

9.foreach chiletjof taskti

10.iftjhas not been assigned any cluster and parent(tj) has been assigned a cluster

11.ti←tjandgotolabel

12.break

13.endif

14.endfor

15.endif

16.endfor

17.endprocedure

3.5 截止時間分配

算法4用于將截止時間在所有任務(wù)間進行子分配。截止時間子分配與任務(wù)的完成時間成比例增長，可以用來降低處理器的執(zhí)行頻率，進而降低執(zhí)行能耗。算法開始于已分配任務(wù)，即已分配截止時間D的出口任務(wù)開始執(zhí)行。然后，所有未分配的關(guān)鍵父任務(wù)被逐步分配子截止時間。在此過程中，需要定義關(guān)鍵路徑和關(guān)鍵父任務(wù)。

算法4Distribute_time(t)

1.whilethas unallocated parentdo

2.path←null,tk←t

3.whiletkhas unallocated parentdo

4.path←deciding_parent oftk+path

5.tk←deciding_parent oftk

6.endwhile

7.callallocate_SubD(path)

8.foreach tasktiinpath

9. allocate(ti)←true

10.endfor

11.foreach tasktiinpath

12. updateESTjwheretj∈chile(ti)

13. updateLFTjwheretj∈parent(ti)

14.callDistribute_time(ti)

15.endfor

16.endwhile

17.endprocedure

定義1從tentry至任務(wù)ti的最長路徑為任務(wù)ti的關(guān)鍵路徑。

定義2對于任務(wù)ti的未分配父任務(wù)tp，若滿足EST(tp)+ETp,avg+CTpi,avg達(dá)到最大值，則該任務(wù)為關(guān)鍵父任務(wù)。

對于輸入的有向無環(huán)圖DAG，必須存在一條從入口至出口的關(guān)鍵路徑。首先，所有DAG中關(guān)鍵路徑上的關(guān)鍵任務(wù)根據(jù)其平均執(zhí)行時間分配子截止時間。再根據(jù)任務(wù)的子截止時間向其所有未分配的關(guān)鍵父任務(wù)分配子截止時間。該遞歸過程將關(guān)鍵路徑上的任務(wù)和其子截止時間作為輸入，逐步向其未分配的關(guān)鍵父任務(wù)進行子截止時間分配。

算法4中，出口任務(wù)是輸入任務(wù)，步驟2-步驟6從出口任務(wù)開始初始化，并遞歸向關(guān)鍵父任務(wù)迭代，直到?jīng)]有未分配父任務(wù)留下為止。步驟7中，allocate_subD(path)被調(diào)用來向關(guān)鍵路徑上的每個任務(wù)分配子截止時間。步驟8-步驟10中，在關(guān)鍵路徑上的所有任務(wù)的allocate(task)變量設(shè)置為真。然后，步驟12更新子任務(wù)的最早開始時間EST的值，步驟13更新父任務(wù)的最晚完成時間LFT的值。步驟14中，再次遞歸調(diào)用本文算法將子截止時間分配至關(guān)鍵路徑的所有未分配的父任務(wù)上。

3.6 任務(wù)調(diào)度

算法5用于向從起點任務(wù)至終止任務(wù)間的關(guān)鍵路徑上的所有任務(wù)分配子截止時間。為了均勻地在路徑上的所有任務(wù)間進行截止時間分配，計算關(guān)鍵路徑的路徑長度pl后，引入一個標(biāo)準(zhǔn)因子N：

(11)

步驟4-步驟7用于計算任務(wù)ti所在的關(guān)鍵路徑的路徑長度pl，步驟10中考慮任務(wù)的最終執(zhí)行時間FET，利用標(biāo)準(zhǔn)因子N計算子截止時間分配值：

FET(ti)=ETi,avg+ETi,avg×N

(12)

步驟11中，在關(guān)鍵路徑上的每個任務(wù)的子截止時間計算為：

SubD(ti)=EST(ti)+FET(ti)

(13)

算法5allocate_subD(path)

1.tstart←start task ofpath

2.tend←end task ofpath

3.pl=0

4.foreach tasktiinpath

5.pl=pl+ETi+CTij,tjis successor oftiin path

6.ti←tj

7.endfor

8. calculate normalized factor by Equ.(11)

9.foreach tasktiinpath

10. calculateFET(ti) by Equ.(12)

11. calculate SubD(ti) by Equ.(13)

12.endfor

13.endprocedure

任務(wù)調(diào)度將聚簇后的任務(wù)集調(diào)度至選擇了合適頻率/電壓等級的處理器上執(zhí)行，使得系統(tǒng)的全局可靠性達(dá)到最大化，且系統(tǒng)能耗被最小化。

4 實 驗

為了驗證REEWS算法的性能，通過仿真實驗的手段分析工作流調(diào)度的結(jié)果，并與以下三種經(jīng)典工作流調(diào)度算法進行性能比較：HEFT算法[5]，RHEFT算法[6]，PALS算法[9]。HEFT算法按照任務(wù)的秩值進行排序，然后按序選擇任務(wù)，將其調(diào)度至執(zhí)行時間最小的處理器上執(zhí)行。RHEFT算法將失效率與單個指令執(zhí)行時間的乘積考慮至工作流調(diào)度中，以此作為映射任務(wù)的標(biāo)準(zhǔn)，并最大化系統(tǒng)的可靠性。PALS算法則在非關(guān)鍵任務(wù)上利用DVFS技術(shù)降低了工作流調(diào)度的總體能耗。

4.1 實驗配置

為了模擬云計算環(huán)境，利用CloudSim[11]平臺構(gòu)建IaaS云環(huán)境，該平臺中已經(jīng)擴展了內(nèi)核，加入了能效感知調(diào)度方法。對于計算節(jié)點能耗模型，應(yīng)用2.3節(jié)中介紹的功能模型。隨機選擇若干計算節(jié)點進行算法模擬，具體分布于4、8、16和32臺計算節(jié)點。表2給出每個計算節(jié)點的相關(guān)參數(shù)，節(jié)點的最大運行頻率處于1.6 GHz至2.8 GHz之間，對應(yīng)于每個可執(zhí)行的指令數(shù)MIPS為1 500至3 000之間。每個計算節(jié)點支持4個等級的動態(tài)頻率/電壓調(diào)整，分布于fmin至fmax之間，同時約定fmin=40%fmax。

表2 相關(guān)參數(shù)

仿真實驗中引入兩種工作流結(jié)構(gòu)進行測試，包括隨機生成任務(wù)圖和高斯消除任務(wù)圖兩種結(jié)構(gòu)。任務(wù)數(shù)量分布于20、40、60、80和100，任務(wù)中計算型和通信型任務(wù)的比例CCR值設(shè)置為0.2、0.5、1.0和1.2。

4.2 工作流結(jié)構(gòu)

仿真實驗中，隨機任務(wù)圖根據(jù)以上參數(shù)的不同組合進行生成。任務(wù)的計算代價MI均勻地分布在4 000 000～10 000 000之間，遞增步長為7 000 000，形狀參數(shù)分布于0.2、0.5、1和2之間。通信代價隨機生成于計算代價與CCR值的乘積間，通過不同的CCR取值，工作流應(yīng)用的結(jié)構(gòu)類型也將有所不同。

2) 高斯消除任務(wù)圖。高斯消除任務(wù)圖可以通過改變計算代價與CCR取值決定。此外，矩陣大小m用于計算任務(wù)圖中任務(wù)的數(shù)量。高斯消除任務(wù)圖的結(jié)構(gòu)是固定的，因此不需要任務(wù)數(shù)量和形狀參數(shù)。對于高斯消除任務(wù)圖，實驗中將任務(wù)數(shù)量分布于9、20、35和65之間。

4.3 評價指標(biāo)

1) 能耗：執(zhí)行所有工作流任務(wù)帶來的總體能耗，由式(6)定義。

2) 可靠性：在沒有失效的情況下所有n個任務(wù)執(zhí)行時系統(tǒng)的可靠性，由式(9)定義。

4.4 實驗結(jié)果

1) 不同任務(wù)規(guī)模下的性能。比較工作流DAG中任務(wù)數(shù)量分別為20、40、60、80和100時的算法性能，如圖1所示。REEWS算法比其他算法消耗了最少的能耗，隨著工作流規(guī)模(任務(wù)數(shù)量)的增加，本文算法較HEFT和RHEFT在能量節(jié)省比例上分別增加了25%～31%和38%～44%，原因在于工作流任務(wù)間的相關(guān)性導(dǎo)致有空閑時槽的存在。HEFT和RHEFT的能耗較高，原因是兩種算法僅分別關(guān)注了執(zhí)行時間和調(diào)度可靠性問題。對于PALS，能耗僅是通過在非關(guān)鍵任務(wù)上利用DVFS進行能源節(jié)省，而本文算法則同時在關(guān)鍵和非關(guān)鍵任務(wù)應(yīng)用DVFS進行降能，同時可以滿足截止時間約束條件。因此，REEWS算法對PALS節(jié)省的能耗范圍為10%～21%。觀察可靠性情況，REEWS算法仍是所有算法中最優(yōu)的。這是因為該算法在選擇目標(biāo)資源時考慮了調(diào)度失效率問題。進一步，算法選擇了合適的運行頻率/電壓等級從而在任務(wù)執(zhí)行過程中的可靠性達(dá)到最優(yōu)。然而，在PALS中，可靠性被最小化，原因是它僅關(guān)注了能耗和執(zhí)行時間的最優(yōu)。HEFT和RHEFT的可靠性又優(yōu)于PALS，原因是它們在執(zhí)行任務(wù)時均采用了正常的處理器頻率，雖然沒有降低能耗，但沒有犧牲可靠性。

圖1 任務(wù)規(guī)模對能耗與可靠性的影響

2) 不同處理器數(shù)量下的性能。本節(jié)觀察處理器數(shù)量分別為4、8、16和32，任務(wù)規(guī)模固定為60時的性能表現(xiàn)如圖2所示。隨著處理器數(shù)量的增加，REEWS算法的能耗節(jié)省幅度也在增加。REEWS較HEFT的能量節(jié)省為16%～27%，較RHEFT的能量節(jié)省為22%～34%，較PALS的能量節(jié)省為7%～13%。這是因為更多的處理器可用時，單個處理器上的任務(wù)量會變少，改變其運行頻率的概率將變高，進而可以降低總體執(zhí)行能耗。然而，到達(dá)某一極限后，處理器數(shù)量的增加則無法進一步降低總體能耗，這是由于此時空閑處理器的能量開銷有所增加。此外，REEWS的可靠性也是所有算法中最優(yōu)的，這是由于更多的處理器可用時，該算法選擇最優(yōu)的處理資源的概率也將增加。

圖2 資源規(guī)模對能耗與可靠性的影響

3) 不同CCR值下的性能。圖3是不同CCR取值下，60個任務(wù)和8個處理器資源在隨機任務(wù)圖中得到的結(jié)果。對于CCR<1的情況，即計算密集型任務(wù)圖，由于在計算密集型任務(wù)上使用了DVFS，因而得到了最小的能耗。REEWS比較HEFT節(jié)省了23%～30%的能耗，比較RHEFT節(jié)省了30%～34%的能耗，比較PALS節(jié)省了15%～20%的能耗。然而，當(dāng)CCR>1時，本文算法相較三種算法仍可以分別節(jié)省約21%、28%和14%的能耗，原因是在數(shù)據(jù)通信階段，本文算法能夠使得處理器的運行頻率達(dá)到最小。同時，還可以看到，REEWS的可靠性也是所有算法中最好的。

圖3 CCR對能耗與可靠性的影響

高斯消除任務(wù)圖的測試結(jié)果可見圖4-圖6，其結(jié)果與隨機任務(wù)圖的結(jié)果是相似的，綜合說明本文算法在處理不同類型的工作流結(jié)構(gòu)、規(guī)模時具有較好的適應(yīng)性，可以在不同類型的工作流結(jié)構(gòu)中進行高可靠性和高能效的工作流調(diào)度任務(wù)。

圖4 高斯消除任務(wù)圖下任務(wù)數(shù)量對性能的影響

圖5 高斯消除任務(wù)圖下處理器數(shù)量對性能的影響

圖6 高斯消除任務(wù)圖下CCR取值對性能的影響

由以上實驗結(jié)果可以看出，在不同的CCR取值下，即工作流中包含不同計算型和通信型任務(wù)比例的條件下，本文算法得到的能耗與可靠性并沒有出現(xiàn)反轉(zhuǎn)變化，說明本文算法可以適應(yīng)于處理不同類型工作流任務(wù)的調(diào)度場景，具有較好的適應(yīng)性。而在同步優(yōu)化工作流調(diào)度能耗與可靠性上，本文算法也具有較好的可行性和魯棒性。

5 結(jié) 語

為了同步解決云工作流調(diào)度時的失效和高能耗問題，本文提出一種工作流調(diào)度算法。為了在截止時間的QoS約束下最大化系統(tǒng)可靠性并最小化調(diào)度能耗，將工作流調(diào)度過程劃分為四個階段。第一階段尋找有效的工作流任務(wù)的拓?fù)渑判?，同時滿足任務(wù)間的執(zhí)行次序；第二階段將任務(wù)劃分為集合，從而最小化任務(wù)間的通信代價，進而最小化系統(tǒng)的能耗；第三階段將用戶定義的截止時間QoS約束在各任務(wù)間進行子劃分；第四階段將任務(wù)調(diào)度至運行于合適頻率/電壓等級的處理器上執(zhí)行，使得系統(tǒng)的全局可靠性最大化，且最小化系統(tǒng)能耗。隨機生成任務(wù)圖和高斯消除任務(wù)圖的綜合仿真測試結(jié)果表明，本文算法在降低總體能耗和提高工作流調(diào)度可靠性方面均優(yōu)于對比算法。