IaaS云滿足預(yù)算約束的工作流應(yīng)用調(diào)度算法

劉書倫 彭高輝 陳 平

1(濟(jì)源職業(yè)技術(shù)學(xué)院信息工程系 河南 濟(jì)源 459000) 2(華北水利水電大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 河南 鄭州 450046)

0 引 言

許多科學(xué)領(lǐng)域內(nèi)的應(yīng)用,如天文學(xué)領(lǐng)域、生物信息學(xué)領(lǐng)域、天體物理學(xué)領(lǐng)域、地震學(xué)領(lǐng)域等,均有著比一般應(yīng)用任務(wù)更加復(fù)雜的任務(wù)執(zhí)行需求,通?？山楣ぷ髁魅蝿?wù)模式[1]。這種工作流任務(wù)模式通常表達(dá)為有向無(wú)環(huán)圖模型DAG,圖節(jié)點(diǎn)代表任務(wù),有向邊代表節(jié)點(diǎn)間的數(shù)據(jù)傳輸關(guān)系?？茖W(xué)工作流應(yīng)用一般規(guī)模巨大,任務(wù)結(jié)構(gòu)更加復(fù)雜,因此在處理時(shí)需要更強(qiáng)大的計(jì)算能力和存儲(chǔ)空間的支持。云計(jì)算因?yàn)榭梢酝ㄟ^虛擬化技術(shù)提供無(wú)限制的強(qiáng)大資源,使其成為執(zhí)行大規(guī)?？茖W(xué)工作流應(yīng)用的有效平臺(tái),尤其基礎(chǔ)設(shè)施云計(jì)算環(huán)境中,眾多的軟硬件基礎(chǔ)設(shè)施均可以用于支撐科學(xué)工作流應(yīng)用的執(zhí)行環(huán)境[2-3]。具體來(lái)說(shuō),IaaS云計(jì)算中的工作流調(diào)度問題的目標(biāo)就是將每個(gè)任務(wù)節(jié)點(diǎn)映射至云設(shè)施中的虛擬機(jī)實(shí)例上,實(shí)現(xiàn)任務(wù)的調(diào)度與執(zhí)行。而這一問題本質(zhì)上是一個(gè)NP完全問題。

為了以更加貼合IaaS云環(huán)境的資源利用基本屬性,解決云工作流調(diào)度問題,提出一種滿足預(yù)算約束的工作流調(diào)度算法Normalization Budget-constraint Workflow Scheduling(NBWS)。在滿足預(yù)算約束前提下,以最小化工作流調(diào)度時(shí)長(zhǎng)為目標(biāo),算法分調(diào)度任務(wù)選擇和虛擬機(jī)實(shí)例選擇兩個(gè)階段進(jìn)行。第一階段將工作流任務(wù)依據(jù)依賴關(guān)系劃分為不同層次,同層次任務(wù)組成包任務(wù),然后以最小最大標(biāo)準(zhǔn)化方法對(duì)層次中任務(wù)估算時(shí)間作標(biāo)準(zhǔn)化處理,定義最遲完成時(shí)間與最早完成時(shí)間差值最大者為調(diào)度任務(wù);第二階段在期望預(yù)算下以最早完成時(shí)間最小為標(biāo)準(zhǔn)選擇調(diào)度資源,實(shí)現(xiàn)任務(wù)與資源間的映射。最后通過仿真實(shí)驗(yàn)驗(yàn)證新算法的有效性。

1 相關(guān)工作介紹

目前的任務(wù)調(diào)度算法主要分為三種類型,搜索式、啟發(fā)式和元啟發(fā)式。而待調(diào)度任務(wù)可以劃分為獨(dú)立任務(wù)(即包任務(wù))和混合型任務(wù)(即工作流任務(wù))[3-5]兩種類型。任務(wù)至資源間映射調(diào)度可以劃分為兩個(gè)階段:調(diào)度階段[6]和提供階段[7]。云任務(wù)調(diào)度則同時(shí)包含調(diào)度與提供,需要在待調(diào)度任務(wù)選擇和針對(duì)調(diào)度任務(wù)的資源實(shí)例選擇上均有所考慮。

目前,工作流調(diào)度算法主要有兩種類型:盡力服務(wù)調(diào)度算法Best-effort與服務(wù)質(zhì)量Quality of Service(QoS)約束調(diào)度算法[8]。通常,前一類算法會(huì)忽略一些重要的參考因素,比如執(zhí)行代價(jià),再以最小化執(zhí)行跨度Makespan為目標(biāo)進(jìn)行任務(wù)調(diào)度。類似于啟發(fā)式算法,最小最小算法Min-Min、最大最小算法Max-Min及Suffrage算法[9]等均是以最小化執(zhí)行跨度Makespan作為工作流調(diào)度目標(biāo)的。此外,文獻(xiàn)[10]提出一種異構(gòu)最快完成時(shí)間調(diào)度算法Heterogeneous Ealiest Finish Time(HEFT),通過賦予任務(wù)不同優(yōu)先級(jí),最小化任務(wù)調(diào)度時(shí)間。后一類算法則會(huì)更加全面地考慮一些重要的約束因素,更加貼合實(shí)際的任務(wù)調(diào)度應(yīng)用環(huán)境。文獻(xiàn)[11]提出了一種基于重調(diào)度算法IC-LOSS,算法試圖將所有任務(wù)重調(diào)度至更低價(jià)的機(jī)器資源上。與本文不同,該算法以一個(gè)初始調(diào)度解為起點(diǎn),然后迭代修正調(diào)度解直到滿足預(yù)算約束。本文算法未考慮初始調(diào)度解,且不是迭代式算法,對(duì)于給定的工作流結(jié)構(gòu),可以常量時(shí)間求解工作流調(diào)度解。文獻(xiàn)[12]提出了基于預(yù)算的異構(gòu)最早完成時(shí)間算法Budget Heterogeneous Ealiest Finish Time(BHEFT)進(jìn)行工作流調(diào)度,算法在用戶定義的截止時(shí)間和預(yù)算約束下以最小化執(zhí)行時(shí)間為目標(biāo)建立調(diào)度計(jì)劃,然后將子預(yù)算分配至每個(gè)任務(wù),并根據(jù)分配的子預(yù)算為任務(wù)選擇合適的服務(wù)提供者。本文算法與BHEFT有以下兩點(diǎn)不同之處:(1) 所考慮的資源實(shí)例屬性更加異構(gòu)性,可選擇的范圍更大;(2) 聯(lián)合了時(shí)間和代價(jià)因素決定當(dāng)前調(diào)度任務(wù)的資源選取。文獻(xiàn)[13]提出預(yù)算和截止時(shí)間約束的異構(gòu)最早完成時(shí)間算法Budget-Deadline Heterogeneous Ealiest Finish Time(BDHEFT),是對(duì)HEFT和BHEFT的擴(kuò)展算法。算法具有服務(wù)層次和任務(wù)層次的兩級(jí)調(diào)度機(jī)制,在服務(wù)層次調(diào)度階段,任務(wù)根據(jù)秩值進(jìn)行降序排列。對(duì)于每個(gè)選擇的任務(wù),分配一個(gè)最優(yōu)可能的資源集合;在任務(wù)層次調(diào)度階段,根據(jù)相應(yīng)規(guī)則為單個(gè)任務(wù)選擇最佳資源。

2 模型描述

2.1 應(yīng)用模型

將工作流W表示為DAG模型,表示為二元組W(T,E),T={t1,t2,…,tn}表示n個(gè)任務(wù)的有限集合,E={ejk|1≤j≤n,1≤k≤n,j≠k}表示有向邊集合,描述任務(wù)tj與tk間的執(zhí)行順序約束,表明tj(稱為父任務(wù))完成并接收所有傳輸數(shù)據(jù)后,tk(稱為子任務(wù))才可以執(zhí)行。不存在父任務(wù)稱為入口任務(wù),命名為tentry,不存在子任務(wù)稱為出口任務(wù),命名為texit。當(dāng)有多個(gè)入口或出口任務(wù)時(shí),可添加一個(gè)傀儡入口/出口任務(wù),并令其計(jì)算時(shí)間和通信時(shí)間為0。任務(wù)tj的層次level表示從入口任務(wù)tentry至tj的有向邊的最大數(shù)量。令pred(tj)表示tj的所有直接前驅(qū)父任務(wù)集合,定義為pred(tj)={ti|(ti,tj)∈T}。令succ(tj)表示tj的所有直接后繼子任務(wù)集合,定義為succ(tj)={ti|(tj,ti)∈T}。

2.2 資源模型

IaaS云資源模型由云服務(wù)提供者Cloud Service Provider(CSP)構(gòu)成,可向用戶提供多重類型的虛擬機(jī)Virtual Machine(VM)。令CS={CS1,CS2,…,CSM}表示M個(gè)云服務(wù)提供者集合,可用于部署m個(gè)VM。每個(gè)CSP中的資源數(shù)量不同,故所能提供的服務(wù)能力也不相同。令VT={vt1,vt2,…,vtn}表示虛擬機(jī)VM類型,每種類型表示為二元組vt(pc,c),pc表示處理能力,c表示VM單位時(shí)間的利用代價(jià)。

2.3 調(diào)度目標(biāo)

算法目標(biāo)是將每個(gè)工作流任務(wù)調(diào)度至云資源實(shí)例上執(zhí)行,在滿足用戶的預(yù)算約束的前提下,最小化工作流的調(diào)度時(shí)長(zhǎng)makespan?？尚问交癁?

minmakespan

s.t. TotalCost(C)≤Budget(Buser)

2.4 基本定義

表1給出算法設(shè)計(jì)中主要涉及的符號(hào)定義。

表1 符號(hào)說(shuō)明

定義1ti在VMj上的估算計(jì)算時(shí)間ECTti,VMj定義為:

(1)

式中:Size(ti)為任務(wù)大小,以浮點(diǎn)運(yùn)算數(shù)FLOP度量;pcVMj為ECTti,VMj的處理能力,以每秒百萬(wàn)浮點(diǎn)運(yùn)算量MFLOPS度量;PerDegVMj為VM類型j的CPU性能變量。

定義2不同虛擬機(jī)上的兩個(gè)任務(wù)ti與tj間的數(shù)據(jù)傳輸時(shí)間定義為:

(2)

式中:dti為輸出數(shù)據(jù)量,以MB度量;bVM為VM的平均帶寬,以Mbit/s度量。當(dāng)兩個(gè)任務(wù)執(zhí)行于同一VM時(shí),數(shù)據(jù)傳輸時(shí)間為0。

定義3ti在VMj上的處理時(shí)間PTti,VMj定義為:

(3)

式中:e為ti的出邊,若兩個(gè)任務(wù)運(yùn)行在同一資源上,則ISSame=0,否則為1;dp為IaaS云中VM的獲取延時(shí)。依據(jù)式(3)可知,任務(wù)在虛擬機(jī)上的處理時(shí)間由三部分構(gòu)成:估算計(jì)算時(shí)間(定義1)、數(shù)據(jù)傳輸時(shí)間(定義2)、虛擬機(jī)的獲取延時(shí)。

定義4ti在VMj上的最早開始時(shí)間ESTti,VMj定義為:

(4)

式中:AvailVMj為VMj的最小訪問時(shí)間;AFTtk為前驅(qū)任務(wù)的實(shí)際完成時(shí)間,tk∈pred(ti);DTtk,i為從前驅(qū)任務(wù)至當(dāng)前任務(wù)的數(shù)據(jù)傳輸時(shí)間。對(duì)于入口任務(wù)tentry,ESTtentry,VMj=0。

定義5ti在VMj上的最早完成時(shí)間EFTti,VMj定義為最早開始時(shí)間與估算計(jì)算機(jī)間之和:

EFTti,VMj=ESTti,VMj+ECTti,VMj

(5)

依據(jù)式(5)可知,計(jì)算任務(wù)的最早完成時(shí)間分別需要計(jì)算任務(wù)的最早開始時(shí)間(定義4)和任務(wù)的估算時(shí)間(定義1)。

定義6任務(wù)tj的層次levellv(tj)表示從入口任務(wù)至tj的有向邊的最大數(shù),定義為:

(6)

處于同一level的所有任務(wù)可劃分為包任務(wù)BoT。入口任務(wù)tentry的level為0。

定義7標(biāo)準(zhǔn)化估算計(jì)算時(shí)間定義為:

(7)

式中:MinETC和MaxETC分別為估算計(jì)算時(shí)間矩陣的最小值與最大值。該方法的目標(biāo)是通過Min-Max標(biāo)準(zhǔn)化方法將ECTi,j映射為NECTi,j中的[0,1]間的值。由定義1得到任務(wù)的估算時(shí)間后,即可計(jì)算標(biāo)準(zhǔn)化估算時(shí)間。

定義8ti在VMj上的執(zhí)行代價(jià)ECti,VMj定義為:

(8)

任務(wù)執(zhí)行代價(jià)依據(jù)任務(wù)的處理時(shí)間(定義3)及虛擬機(jī)的賬單間隔及賬單代價(jià)計(jì)算獲取。

3 算法設(shè)計(jì)

將本文命名為基于標(biāo)準(zhǔn)化預(yù)算約束的工作流調(diào)度算法NBWS,算法目標(biāo)是在滿足預(yù)算約束的同時(shí)尋找最優(yōu)化執(zhí)行效率的工作流調(diào)度解。算法分為兩個(gè)步驟進(jìn)行:任務(wù)選擇和資源選擇。

3.1 任務(wù)選擇

通過劃分工作流任務(wù)層次,可以使得不具備依賴約束性的任務(wù)劃分在相同的level中,從而最大化任務(wù)的并行化程度。因此,包含著獨(dú)立任務(wù)集合的每個(gè)level可視為包任務(wù)BoT。對(duì)于任務(wù)選擇階段,工作流任務(wù)根據(jù)其優(yōu)先級(jí)和依賴約束關(guān)系劃分為不同的level。針對(duì)工作流W的每個(gè)levelli,其中的每個(gè)任務(wù)ti的ECTi,j利用Min-Max標(biāo)準(zhǔn)化方法進(jìn)行標(biāo)準(zhǔn)化處理,將其值鎖定在具體范圍內(nèi)。然后,針對(duì)每個(gè)任務(wù)ti,尋找在可用VM上最遲完成時(shí)間與最早完成時(shí)間之間的差值。具有最大時(shí)間差值的任務(wù)選擇為調(diào)度任務(wù),調(diào)度資源見第二階段的資源選擇。再將該任務(wù)從包任務(wù)BoT中移除,更新ECTi,j矩陣中所有其他任務(wù)的完成時(shí)間。重復(fù)這一過程直到所有任務(wù)調(diào)度至合適虛擬機(jī)上。

3.2 資源選擇

資源選擇階段由時(shí)間和代價(jià)變量主導(dǎo)。

定義9剩余預(yù)算rb為可用于調(diào)度剩余未調(diào)度任務(wù)的預(yù)算,定義為:

rb=rb-cij

(9)

初始值rb=Buser,cij為ti在VMj上的執(zhí)行代價(jià)。

定義10ti的期望合理預(yù)算erb定義為:

(10)

式中:tunshed表示未調(diào)度任務(wù)數(shù)。

期望合理預(yù)算可視為定義9中的剩余預(yù)算值與未調(diào)度任務(wù)數(shù)的比值。

基于以上定義可知,某些代價(jià)較高的虛擬機(jī)VM可能被刪除。僅考慮代價(jià)滿足ECti,VM≤erbti的VM。

wti={wx,VM|wx,VM,ECti,VM≤erbti}

(11)

以下的選擇規(guī)則可用于選擇最優(yōu)VM:

1) 若wti=null,則選擇代價(jià)最低的VM;

2) 若wti≠null,則選擇最早完成時(shí)間的VM。

3.3 算法詳細(xì)設(shè)計(jì)

算法1給出NBWS算法的完整執(zhí)行過程。步驟1根據(jù)式(6)計(jì)算每個(gè)任務(wù)的level,并根據(jù)任務(wù)level將任務(wù)劃分為包任務(wù)BoT,步驟2根據(jù)式(1)計(jì)算估算時(shí)間ECT,根據(jù)式(2)計(jì)算DAG的數(shù)據(jù)傳輸時(shí)間DT,步驟3對(duì)任務(wù)可用的剩余預(yù)算和未調(diào)度任務(wù)進(jìn)行初始化,正式調(diào)度前,剩余預(yù)算為全部預(yù)算Buser,未調(diào)度任務(wù)為全部任務(wù)n。步驟4通過將工作流任務(wù)執(zhí)行于代價(jià)最低的資源上得到最低代價(jià)的工作流調(diào)度代價(jià)costlow。步驟5判斷若用戶預(yù)算小于最低調(diào)度代價(jià),表明此時(shí)無(wú)法在滿足預(yù)算的條件下進(jìn)行工作流調(diào)度,需要在步驟6重新申請(qǐng)高于最低代價(jià)costlow的預(yù)算。若預(yù)算大于等于costlow,即步驟7以下過程,表明可執(zhí)行。步驟8-步驟16按不同level分別對(duì)同一level中的任務(wù)進(jìn)行調(diào)度選擇。若一個(gè)層次level中的任務(wù)數(shù)大于1個(gè)(步驟9),首先在步驟10計(jì)算任務(wù)的最早完成時(shí)間,再在步驟11調(diào)用算法2的標(biāo)準(zhǔn)化處理函數(shù)同一層次的任務(wù)在不同虛擬機(jī)類型上的標(biāo)準(zhǔn)化執(zhí)行時(shí)間,最后在步驟12中調(diào)用算法3從該層次level中選擇調(diào)度任務(wù)。若一個(gè)層次level中的任務(wù)數(shù)不大于1,即僅等于1(步驟14),則在步驟15直接選擇該任務(wù)為調(diào)度任務(wù)。遍歷完所有層次上的任務(wù)后,在步驟17中返回最后的工作流調(diào)度映射方案。NBWS算法分調(diào)度任務(wù)選擇和虛擬機(jī)實(shí)例選擇兩階段進(jìn)行。第一階段作任務(wù)層次劃分,以最小最大方法對(duì)包任務(wù)的估算時(shí)間作標(biāo)準(zhǔn)化處理,并將最遲完成時(shí)間與最早完成時(shí)間差值最大者定義為調(diào)度任務(wù);第二階段在期望預(yù)算約束下以調(diào)度效率為優(yōu)為標(biāo)準(zhǔn)選擇實(shí)例資源。算法聯(lián)合了時(shí)間和代價(jià)因素決定當(dāng)前調(diào)度任務(wù)的資源選取。且不是迭代求解,對(duì)于給定的工作流結(jié)構(gòu),調(diào)度解求解是常量級(jí)時(shí)間。

算法1NBWS

輸入:工作流任務(wù)集合,云服務(wù)提供者集合及相關(guān)參數(shù)。

輸出:任務(wù)與虛擬機(jī)間的映射關(guān)系。

1. compute the level of each task, group the tasks as BOTs based on their level

2. computeECT,DTof DAG

3.rb=Buser,tunshed=n

4. compute cheapest schedule cost (costlow) by executing workflow tasks on cheapest resources

5.ifBuser

6. prompt user to specify a budget abovecostlow(DAG)

7.else

8.foreachbotq∈BoTsdo

9.if(botq.count(tasks)>1)then

10. computeEFTforbotq

11.NECTli=callNormalization(botq,ECT,VMType)

12.callgetTask(NECTbotq)

13.endif

14.else

15.callgetTask()

16.endfor

17.returnschedule map

18.endif

算法2用于計(jì)算各層次level中包任務(wù)在不同資源實(shí)例上的標(biāo)準(zhǔn)化執(zhí)行時(shí)間。算法需要輸入的參數(shù)包括每個(gè)層次level的任務(wù)集合、估算執(zhí)行時(shí)間矩陣ECT和虛擬機(jī)資源類型集合,即步驟1。步驟2-步驟9遍歷所有包任務(wù)及虛擬機(jī)資源類型,用于尋找估算時(shí)間矩陣的最小值MinETC與最大值MaxETC,在滿足步驟3或步驟6的情況下,分別對(duì)估算時(shí)間矩陣的最小值和最大值進(jìn)行更新,即步驟4和步驟7。步驟10-步驟14則在每個(gè)包任務(wù)和每個(gè)虛擬機(jī)資源類型下,計(jì)算標(biāo)準(zhǔn)化估算時(shí)間ECT,即步驟12。該算法主要利用最小最大法的標(biāo)準(zhǔn)化數(shù)據(jù)處理機(jī)制,可將數(shù)據(jù)按比例綻放,使其落入特定區(qū)間,成為無(wú)量綱的純數(shù)值進(jìn)行比較。

算法2Normalization(botq,ECT,VMType)

輸入:任務(wù)層次,ECT及虛擬機(jī)類型。

輸出:任務(wù)在資源上的標(biāo)準(zhǔn)化執(zhí)行時(shí)間。

1.Require:group of tasks at levelli,ECTmatrix and VM TypeVMType

2.foreach tasktiinbotqandVMjinVMTypedo

3.ifETCi,j

4.MinETC=ETCi,j

5.endif

6.ifETCi,j>MaxETCthen

7.MaxETC=ETCi,j

8.endif

9.endfor

10. for each tasktiinbotqdo

11. for eachVMjinVMTypedo

12. find NormalizedECTasNECTi,j

13. end for

14. end for

算法3在獲得每個(gè)層次level的任務(wù)的標(biāo)準(zhǔn)化估計(jì)執(zhí)行時(shí)間的前提下,確定調(diào)度任務(wù)。步驟1將包任務(wù)的標(biāo)準(zhǔn)化估算執(zhí)行時(shí)間作為臨時(shí)估算時(shí)間矩陣。步驟2-步驟4遍歷層次level上所有任務(wù)在所有虛擬機(jī)類型上得到的臨時(shí)標(biāo)準(zhǔn)化估算時(shí)間,并將其臨時(shí)存儲(chǔ),即步驟5。步驟9在每一種可能虛擬機(jī)類型上尋找最早完成時(shí)間,步驟12尋找最遲完成時(shí)間,最后在步驟15計(jì)算最遲完成時(shí)間與最早完成時(shí)間的差值,所選擇調(diào)度的任務(wù)為具有最大差值的任務(wù),即步驟16。得到調(diào)度任務(wù)后,在步驟17調(diào)用算法4選擇最優(yōu)的虛擬機(jī)類型進(jìn)行任務(wù)執(zhí)行。該算法能夠在劃定層次關(guān)系的包任務(wù)和標(biāo)準(zhǔn)化的估算執(zhí)行時(shí)間基礎(chǔ)上,尋找最遲完成時(shí)間與最早完成時(shí)間差值最大者作為最優(yōu)的待調(diào)度任務(wù)。

算法3getTask(NECTbotq,li,VMType)

輸入:任務(wù)的標(biāo)準(zhǔn)化任務(wù)執(zhí)行時(shí)間。

輸出:待調(diào)度任務(wù)及執(zhí)行的最優(yōu)虛擬機(jī)類型。

1. Temp_NECTbotq=NECTbotq

2.foreach tasktiinlido

3.foreach tasktjinlido

4.foreachVMkinVMTypedo

5.Tempk=Temp_NECTj,k

6.endfor

7.fork=1 toVMTypedo

8.ifTempk

9.ERFT=Tempk

10.endif

11.ifTempk

12.LTFT=Tempk

13.endif

14.endfor

15.Diffj=LTFT-ERFT

16.endfor

17. TaskSelected=MAX_DIFF(DIFF)

18.callgetOptimalVM(TaskSelected)

19.endfor

算法4用于計(jì)算針對(duì)已確定調(diào)度任務(wù)的最優(yōu)虛擬機(jī)類型。步驟1根據(jù)式(10)計(jì)算任務(wù)的期望合理預(yù)算;步驟2為任務(wù)設(shè)置滿足代價(jià)約束下執(zhí)行ti的可用VM列表wk;步驟3計(jì)算任務(wù)ti在列表wk中VM上的最早完成時(shí)間;步驟4基于兩條選擇規(guī)則選擇最優(yōu)VM;最后在步驟5更新剩余預(yù)算和未調(diào)度任務(wù)。該算法在期望預(yù)算約束下以調(diào)度效率為優(yōu)為標(biāo)準(zhǔn)選擇實(shí)例資源,可使任務(wù)在滿足現(xiàn)有預(yù)算條件下得到最佳的調(diào)度效率。

算法4getOptimalVM(taskt)

輸入:執(zhí)行預(yù)算。

輸出:待調(diào)度的最優(yōu)虛擬機(jī)類型。

1. computeerbfor taskti

2. setwkfor taskti

3. calculate EFT oftion the processing element inwk

4. select a processor for tasktibased on the selection rules

5. update remaining budgetrb,updatetunshed=tunshed-1

4 算例分析

以一個(gè)算例詳細(xì)說(shuō)明NBWS算法的實(shí)現(xiàn)過程。以圖1所示的Montage工作流結(jié)構(gòu)進(jìn)行分析說(shuō)明,該工作流共包含15個(gè)任務(wù)、7個(gè)層次level、24條有向邊,有向邊上的權(quán)值為數(shù)據(jù)傳輸時(shí)間。表2給出每個(gè)任務(wù)在兩個(gè)CSP上所有虛擬機(jī)的執(zhí)行時(shí)間,表格列為任務(wù)、行為資源,元素(i,j)代表任務(wù)ti在資源VMj上的執(zhí)行時(shí)間。假設(shè)VM的單位時(shí)間執(zhí)行代價(jià)為R={0.7,0.4,0.3,0.6}。表3給出每個(gè)任務(wù)在不同虛擬機(jī)VM上的執(zhí)行代價(jià)。假設(shè)用戶預(yù)算為180,代表所有工作流任務(wù)須在該預(yù)算內(nèi)完成。

圖1 Montage工作流示例

表2 估算計(jì)算時(shí)間

表3 執(zhí)行代價(jià)

圖1中,工作流在level1中有3個(gè)任務(wù),這些任務(wù)可能映射至所有可用VM上。因此,對(duì)于level1,t1、t2和t3的TempECT矩陣為:

TempECT通過式(7)作標(biāo)準(zhǔn)化處理為:

對(duì)于t1,最遲和最早完成時(shí)間差值為1-0.1=0.9。對(duì)于t2和t3,差值分別為0.3和0.7。因此,t1擁有最大差值,則t1優(yōu)先被調(diào)度至合適VM上。通過得到任務(wù)調(diào)度優(yōu)先級(jí),可利用式(10)為每個(gè)任務(wù)計(jì)算erb,且可利用式(4)和式(5)分別計(jì)算EST和EFT。

t1第一個(gè)被調(diào)度,erb(t1)=180/15=12。虛擬機(jī)VM1、VM2和VM3滿足條件EC1,j<12。t1在所有VM上的EST均為0,在VM1、VM2和VM3上的EFT分別為17、14和13。那么,尋找最小EFT(為13),選擇虛擬機(jī)VM3?，F(xiàn)在更新t2和t3的TempECT為:

相應(yīng)的N_TempECT為:

類似地,對(duì)于t2和t3,其最遲和最早完成時(shí)間之差分別為0.882 4-0.117 6=0.764 8和1-0=1。因此,t3優(yōu)先被調(diào)度,并利用式(4)和式(5)分別計(jì)算EST和EFT。

t3擁有第二高優(yōu)先級(jí),erb(t3)=(180-3.9)/14=12.578 5。虛擬機(jī)VM2、VM3和VM4滿足條件EC3,j<12.578 5。t3在VM2、VM3和VM4上的EFT分別為17、29和12。那么,最小EFT為12,選擇VM4。更新t2的TempECT為:

相應(yīng)的N_TempECT為:

最后,通過計(jì)算EST和EFT,t2調(diào)度至VM1。

對(duì)于level1,t1、t2和t3分別調(diào)度至VM3、VM1和VM4。VM1、VM2、VM3和VM4的可用時(shí)間Availj分別為14、0、13和12。

對(duì)于level2,有5個(gè)任務(wù)t4、t5、t6、t7和t8,t4擁有兩個(gè)前驅(qū)任務(wù)t1和t2,數(shù)據(jù)傳輸時(shí)間分別為13和15。t4、t5、t6、t7和t8的TempECT矩陣更新為:

對(duì)TempTCT標(biāo)準(zhǔn)化處理后,與level1中的t1、t2和t3類似,level2中的任務(wù)被調(diào)度至相應(yīng)VM。表4給出了全部工作流任務(wù)與虛擬機(jī)之間的調(diào)度映射結(jié)果。表格中,行代表各個(gè)工作流任務(wù),列包含任務(wù)的分配預(yù)算erb、可匹配的VMwi、選擇調(diào)度的VM、EST、EFT、ACT、VM序號(hào)VMID、執(zhí)行代價(jià)Cost。表4表明,總執(zhí)行代價(jià)為125.8,小于用戶預(yù)算180,滿足預(yù)算約束條件。

表4 完整的工作流調(diào)度結(jié)果及各分量結(jié)果

5 仿真實(shí)驗(yàn)分析

5.1 實(shí)驗(yàn)環(huán)境

利用云計(jì)算環(huán)境仿真實(shí)驗(yàn)平臺(tái)CloudSim[14]進(jìn)行仿真實(shí)驗(yàn),在該平臺(tái)中構(gòu)建由6種不同類型的虛擬機(jī)組成的單個(gè)數(shù)據(jù)中心,VM配置參考EC2云服務(wù)的配置,如表5所示。VM實(shí)例間的平均帶寬設(shè)為20 Mbit/s。實(shí)際的云數(shù)據(jù)中心中,諸如數(shù)據(jù)中心所處的地理位置、VM實(shí)例類型以及實(shí)例數(shù)量均會(huì)導(dǎo)致VM請(qǐng)求出現(xiàn)延時(shí),因此,設(shè)置97 s作為VM的啟動(dòng)時(shí)間,依據(jù)Amazon EC2的VM實(shí)例的收費(fèi)周期1 h配置VM實(shí)例利用代價(jià)。

表5 VM實(shí)例配置

利用不同領(lǐng)域中的科學(xué)工作流結(jié)構(gòu)對(duì)算法進(jìn)行測(cè)試,包括:LIGO工作流、Epigenomics工作流、CyberShake工作流、Montage工作流和SPIHT工作流,以上工作流結(jié)構(gòu)的任務(wù)組成和特征可以參考文獻(xiàn)[15]。利用不同的預(yù)算取值對(duì)算法進(jìn)行測(cè)試。對(duì)于一個(gè)基準(zhǔn)調(diào)度方案,工作流的最小預(yù)算定義為:

(12)

式中:VMj為代價(jià)最低的VM。即所有工作流任務(wù)均執(zhí)行于該VM上的代價(jià)為最小預(yù)算值?；谑?12),預(yù)算可在嚴(yán)格與寬松間進(jìn)行松弛計(jì)算:

Budget=β×MB0<β<20

(13)

式中:β為預(yù)算因子,以步長(zhǎng)1遞增至20,用于定義預(yù)算的松緊程度。

利用不同規(guī)模的任務(wù)量進(jìn)行算法測(cè)試,包括small規(guī)模為25個(gè)任務(wù),中等規(guī)模為100個(gè)任務(wù),large規(guī)模為1 000個(gè)任務(wù)。利用Pegasus工作流生成器產(chǎn)生相應(yīng)科學(xué)工作流結(jié)構(gòu)。選取IC-LOSS算法[11]、BHEFT算法[12]和BDHEFT算法[13]進(jìn)行性能對(duì)比分析。

5.2 性能指標(biāo)

引入調(diào)度成功率SR和標(biāo)準(zhǔn)調(diào)度時(shí)間NT度量算法性能。

調(diào)度成功率SR:定義為滿足預(yù)算約束的成功仿真次數(shù)與總的仿真次數(shù)之比。SR表示為:

(14)

標(biāo)準(zhǔn)調(diào)度時(shí)間NT:用于衡量算法效率。NT表示為:

(15)

式中:MSFt表示在滿足執(zhí)行次序約束前提下,工作流執(zhí)行于最快的虛擬機(jī)實(shí)例上得到的調(diào)度時(shí)間。

5.3 實(shí)驗(yàn)結(jié)果

圖2是CyberShake工作流在不同的預(yù)算因子β取值下得到的調(diào)度成功率表現(xiàn)。當(dāng)預(yù)算因子相對(duì)較小時(shí),表明預(yù)算相對(duì)比較有限,本文的NBWS算法依然獲得了較好的調(diào)度成功率。隨著預(yù)算因子的增加,預(yù)算變得寬松,所有算法的調(diào)度成功率均有所提升。相比而言,IC-LOSS算法的調(diào)度成功率是最低的。圖3-圖6是另外四種工作流的測(cè)試結(jié)果?？梢钥闯?NBWS算法在五種測(cè)試工作流結(jié)構(gòu)中在所有不同的預(yù)算緊密程度下均擁有最高的調(diào)度成功率,相對(duì)而言,不同的工作流應(yīng)用類型在不同預(yù)算因子的取值下會(huì)有所起伏,但絕對(duì)性能表現(xiàn)是比較穩(wěn)定的。通過增加預(yù)算因子,更多的預(yù)算可用于執(zhí)行工作流任務(wù),自然會(huì)帶來(lái)更高的調(diào)度成功率。而NBWS算法的優(yōu)勢(shì)在于:該算法在執(zhí)行任務(wù)時(shí)選擇了擁有最小最早完成時(shí)間EFT的虛擬機(jī)實(shí)例資源,其調(diào)度時(shí)長(zhǎng)也會(huì)相應(yīng)降低。因此,它所得到的調(diào)度解是在定義預(yù)算約束之內(nèi)調(diào)度時(shí)長(zhǎng)更小的工作流調(diào)度方案。同時(shí),NBWS算法在進(jìn)行選定任務(wù)調(diào)度后,會(huì)更新剩余預(yù)算值和未調(diào)度任務(wù)列表,并在當(dāng)前預(yù)算約束條件下計(jì)算代價(jià)最小的映射實(shí)例,以此可以確保更高的約束滿足率及調(diào)度成功率。

圖2 CyberShake工作流

圖3 Epigenomics工作流

圖4 LIGO工作流

圖5 Montage工作流

圖6 SPIHT工作流

圖7是在不同類型的工作流結(jié)構(gòu)中得到的NM指標(biāo)結(jié)果,圖8是算法的資源利用率情況。可以看到,NBWS在所有工作流類型中提供了最小的執(zhí)行跨度,執(zhí)行效率更高,同時(shí)說(shuō)明了本文算法針對(duì)不同任務(wù)結(jié)構(gòu)下的適應(yīng)性和魯棒性,主要原因在于:NBWS算法不僅根據(jù)任務(wù)在工作流結(jié)構(gòu)的位置和層次進(jìn)行了類型劃分,還可以在資源實(shí)例選擇階段選取了滿足最優(yōu)需求的資源對(duì)待調(diào)度任務(wù)進(jìn)行執(zhí)行,不僅執(zhí)行效率更高,還可以確保資源實(shí)例被更好地利用。

圖7 NT指標(biāo)

圖8 資源利用率

6 結(jié) 語(yǔ)

本文提出一種新的工作流調(diào)度算法NBWS,算法以工作流調(diào)度時(shí)長(zhǎng)最小化為目標(biāo),將工作流調(diào)度過程劃分為調(diào)度任務(wù)選擇和虛擬機(jī)實(shí)例選擇兩階段進(jìn)行。第一階段旨在首先對(duì)工作流任務(wù)分層,同層組成包任務(wù),并以最小最大方法對(duì)同層任務(wù)的估算時(shí)間作標(biāo)準(zhǔn)化處理,以最遲完成時(shí)間與最早完成時(shí)間差值最大為標(biāo)準(zhǔn)選擇調(diào)度任務(wù)。第二階段以在期望預(yù)算下的最早完成時(shí)間最小為標(biāo)準(zhǔn)選擇調(diào)度資源,實(shí)現(xiàn)任務(wù)調(diào)度。實(shí)驗(yàn)結(jié)果表明,在不同類型工作流結(jié)構(gòu)和不同預(yù)算約束嚴(yán)格程度下,NBWS算法的執(zhí)行效率與調(diào)度成功率要優(yōu)于同類型算法,具有較好的可行性。不足之處在于,算法僅考慮了在預(yù)算約束下工作流調(diào)度效率的優(yōu)化,這僅僅是面向用戶服務(wù)質(zhì)量與服務(wù)體驗(yàn)的優(yōu)化,沒有考慮云資源提供方執(zhí)行任務(wù)的代價(jià),如執(zhí)行能耗問題。進(jìn)一步的研究可將服務(wù)資源的能耗因子考慮到工作流調(diào)度算法中,設(shè)計(jì)融合能效指標(biāo)的多約束多目標(biāo)優(yōu)化的工作流調(diào)度算法,并設(shè)計(jì)相應(yīng)實(shí)驗(yàn)方案,驗(yàn)證算法可行性。