基于云環(huán)境的科學(xué)工作流均衡調(diào)度算法

朱亞東， 李 忠， 嚴(yán) 莉， 陳湘軍(.江蘇聯(lián)合職業(yè)技術(shù)學(xué)院 南京工程分院信息中心，南京 5；.常州輕工職業(yè)技術(shù)學(xué)院 信息工程系，江蘇 常州 000；.南京大學(xué) 電子工程學(xué)院，南京 0046)

0 引 言

科學(xué)工作流廣泛應(yīng)用于大型復(fù)雜科學(xué)應(yīng)用建模，云計(jì)算環(huán)境提供的即付即用計(jì)算能力及定制式硬件設(shè)施，是調(diào)度科學(xué)工作流應(yīng)用的一種有效方法[1]。與傳統(tǒng)工作流不同，科學(xué)工作流規(guī)模更大，任務(wù)的數(shù)據(jù)計(jì)算與通信代價(jià)更高，其本質(zhì)是實(shí)現(xiàn)相互依賴的任務(wù)至資源間的映射，同時(shí)要求滿足用戶定義的QoS約束(截止時(shí)間或預(yù)算)。傳統(tǒng)工作流調(diào)度算法僅側(cè)重于考慮優(yōu)化執(zhí)行效率(執(zhí)行時(shí)間)，未考慮資源代價(jià)，而云是商業(yè)化環(huán)境，其資源使用是有償付費(fèi)的，資源能力越高，價(jià)格越高，此時(shí)，使用不同資源及不同調(diào)度方案得到的執(zhí)行代價(jià)和時(shí)間是不同的。因此，云環(huán)境下的工作流調(diào)度需要同步考慮用時(shí)間和代價(jià)。

相關(guān)研究中，文獻(xiàn)[2]中提出一種預(yù)算約束異構(gòu)最早完成時(shí)間算法BHEFT，算法引入當(dāng)前任務(wù)預(yù)算因子到未調(diào)度任務(wù)的剩余預(yù)算分配中，與本文不同的是，其任務(wù)預(yù)算與剩余預(yù)算是逐個(gè)任務(wù)分配的。文獻(xiàn)[3,4]中則僅側(cè)重于截止時(shí)間的約束及截止時(shí)間在不同任務(wù)或不同分級間的分割，不適應(yīng)于云環(huán)境。文獻(xiàn)[5]中提出預(yù)算感知回溯調(diào)度算法實(shí)現(xiàn)了多任務(wù)工作流的優(yōu)化調(diào)度，文獻(xiàn)[6-7]中則提出一種預(yù)算約束的最小端到端延遲工作流調(diào)度算法，通過在關(guān)鍵路徑上應(yīng)用貪婪策略尋找調(diào)度方案，然而，以上3個(gè)文獻(xiàn)中的資源代價(jià)模型并不適應(yīng)于商業(yè)云特征。文獻(xiàn)[8]中提出基于自動(dòng)擴(kuò)展方法求解預(yù)算約束下的工作流調(diào)度，而本文將根據(jù)任務(wù)優(yōu)先級采用正比例方式進(jìn)行預(yù)算分割。

不同于以上工作，本文將重點(diǎn)關(guān)注于通過預(yù)算分割的方式優(yōu)化工作流的執(zhí)行代價(jià)與執(zhí)行時(shí)間，在工作流分級及在不同分級上賦予待調(diào)度任務(wù)優(yōu)先級的方式，實(shí)現(xiàn)最優(yōu)目標(biāo)實(shí)例資源的選擇，最終完成科學(xué)工作流的代價(jià)與時(shí)間同步最優(yōu)的均衡調(diào)度。

1 工作流與系統(tǒng)模型

1.1 工作流模型

以有向無循環(huán)圖(Directed Acyclic Graph,DAG)表示工作流模型[9]，定義為G=(T,E)，其中，T={t0,t1,…,tn}表示圖的頂點(diǎn)代表的任務(wù)集，E={ei,j|ti,tj∈T}表示圖的邊集，代表任務(wù)間的數(shù)據(jù)或控制依賴性。

邊ei,j∈E表示兩個(gè)任務(wù)ti與tj間的有向邊，ti,tj∈T，代表兩個(gè)任務(wù)間的優(yōu)先順序約束，其具體含義是：僅當(dāng)任務(wù)ti執(zhí)行完成后并收到ti的所有數(shù)據(jù)后，任務(wù)tj才可以開始執(zhí)行。換言之，任務(wù)ti是tj的父任務(wù)，tj是ti的后繼或子任務(wù)。單個(gè)任務(wù)可擁有一個(gè)或多個(gè)父任務(wù)和子任務(wù)。直到其所有父任務(wù)完成后，子任務(wù)ti才可以開始執(zhí)行。

1.2 系統(tǒng)模型

云資源提供者可提供多種類型的實(shí)例，擁有不同的CPU、內(nèi)存、存儲和帶寬能力，且配置不同的使用價(jià)格。本文使用基于彈性計(jì)算云Amazon EC2(Amazon Elastic Compute Cloud，Amazon)的資源模型，其實(shí)例類型按需提供，其定價(jià)利有即付即用的最小小時(shí)計(jì)費(fèi)模型，即：小于1 h的資源使用，均按1 h支付。表1是本文中所使用的資源代價(jià)與實(shí)例類型的相關(guān)參數(shù)配置，更新于2016年3月的Amazon EC2數(shù)據(jù)。

表1 資源實(shí)例類型

注：ECU：Elastic Compute Unit，彈性計(jì)算單元

假設(shè)云資源提供者可提供無限制異構(gòu)實(shí)例數(shù)量，表示為P={p0,p1,…,ph}，其中，h表示實(shí)例類型索引。假設(shè)所有實(shí)例類型和存儲服務(wù)處于同一云數(shù)據(jù)中心內(nèi)，則不同實(shí)例間的平均帶寬可視為基本相等的。

2 預(yù)算分割工作流均衡調(diào)度算法

基于預(yù)算分割的均衡工作流調(diào)度算法(Budget Division Workflow Trade-off Scheduling,BDWTS)劃分為以下4個(gè)階段：

(1) 工作流分級。基于工作流任務(wù)的同步需求，將工作流任務(wù)進(jìn)行分級(level)。

(2) 預(yù)算分割。將用戶定義的預(yù)算(Budget)按6種不同的策略在不同的任務(wù)分級間進(jìn)行分割。

(3) 任務(wù)選擇。在任務(wù)就緒隊(duì)列中基于優(yōu)先級原則選擇調(diào)度任務(wù)。

(4) 實(shí)例選擇。選擇最優(yōu)目標(biāo)實(shí)例執(zhí)行任務(wù)，滿足可用預(yù)算約束。

2.1 工作流分級

工作流分級的目標(biāo)是通過任務(wù)分級最大化任務(wù)執(zhí)行的并行程度，使得同一分級中的任務(wù)與其它分級中的任務(wù)不具有依賴性。因此，每個(gè)分級可視為包括獨(dú)立任務(wù)的批任務(wù)集(Bag of Tasks,BoTs)。

定義任務(wù)ti的分級為以自頂向下的方式，任務(wù)ti至工作流的出口任務(wù)間的所有路徑的邊的最大值，表示為NL(ti)。對于出口任務(wù)，分級為1，對于其他任務(wù)：

(1)

式中，succ(ti)表示任務(wù)ti的直接后繼子任務(wù)集合。然后，根據(jù)任務(wù)分級，將所有擁有相同分級的任務(wù)組成任務(wù)分級集合(Task Level Sets,TLS)，則：

TLS(l)={ti|NL(ti)=l}

(2)

式中,l表示分級數(shù)，且l∈[1,…,NL(tentry)]。

2.2 預(yù)算分割

基于工作流的分級結(jié)果，預(yù)算分割的目標(biāo)是將用戶定義的工作流預(yù)算在不同分級任務(wù)進(jìn)行子劃分。本文設(shè)計(jì)了以下6種預(yù)算分割算法：

(1) 隨機(jī)分割算法Random。預(yù)算隨機(jī)分配于工作流的不同分級上。

(2) 平均分割算法Uniform。每個(gè)工作流分級得到用戶預(yù)算的1/L，其中，L表示工作流總分級數(shù)。

(3) 高度正比例分割算法Height。每個(gè)工作流分級得到的預(yù)算分割正比于工作流分級與入口節(jié)點(diǎn)的距離，則該距離越小，預(yù)算分割越小。

(4) 寬度正比例分割算法Width。每個(gè)工作流分級得到的預(yù)算分割正比于該分級中任務(wù)的數(shù)量。

(5) 區(qū)域正比例分割算法Area。聯(lián)合Width算法和Height算法設(shè)置每個(gè)分級的預(yù)算分割。

(6) 全進(jìn)分割算法All in。將用戶預(yù)算全部分配至入口任務(wù)，然后將剩余預(yù)算依次傳遞至下一分級。該算法可視為Height算法的精煉算法。

以下通過一個(gè)算例說明以上6種算法所描述的預(yù)算在不同分級間的分割方法。Random算法是隨機(jī)產(chǎn)生預(yù)算分割，因此不作額外說明。圖1所示是一個(gè)擁有10個(gè)任務(wù)的工作流結(jié)構(gòu)，圖中左側(cè)一欄是通過式(1)計(jì)算得到的工作流分級值，右側(cè)一欄是從出口任務(wù)開始對每一級任務(wù)的標(biāo)記。該工作流中，最大分級Nmax=5。同時(shí)，設(shè)置用戶預(yù)算Budget=165。

圖1 工作流示例

每種算法得到的預(yù)算分割如下所示(表2給出預(yù)算分割的完整情況)：

Uniform算法由于工作流共有5個(gè)分級，故每個(gè)分級獲得165/5的預(yù)算分割。

Height算法每個(gè)分級分配一個(gè)相對于工作流分級的預(yù)算加權(quán)值，表示為：

預(yù)算因子(Budget Factor,BF)為：

例如：level 4包括任務(wù)B和C，則所分配的預(yù)算為

表2 算法的預(yù)算分割情況

4×BF=4×11=44。

Width算法每個(gè)分級得到的預(yù)算分割取決于對應(yīng)分級中的任務(wù)數(shù)量，此時(shí)的預(yù)算因子為：

例如：level 4包括兩個(gè)任務(wù)，則所分配的預(yù)算為2×BF=2×16.5=33。

Area算法該算法的預(yù)算分割為Height和Width算法的聯(lián)合，計(jì)算為：

預(yù)算因子BF為：

然后，預(yù)算根據(jù)圖1中右欄中的數(shù)值之和進(jìn)行分割。例如：level 3的預(yù)算分割為(4+5+6+7)×BF=22×3=66。

Allin算法總預(yù)算分配至level 5。調(diào)度該分級上的所有任務(wù)后，剩余預(yù)算傳遞至下一分級中。

2.3 任務(wù)選擇

由于任務(wù)的分級特征，這表明只有前一分級中的所有任務(wù)調(diào)度之后，該任務(wù)才能開始執(zhí)行。而同一分級中的任務(wù)間不存在依賴性，因此，均可以準(zhǔn)備執(zhí)行，置入就緒任務(wù)隊(duì)列中。為了從中選擇調(diào)度任務(wù)，需要為就緒隊(duì)列中的任務(wù)分配優(yōu)先級。本文設(shè)計(jì)一種基于最早開始時(shí)間(Earliest Start Time,EST)的優(yōu)先級任務(wù)選擇算法。

如圖2所示的工作流示例，邊上的數(shù)值表示任務(wù)間的數(shù)據(jù)傳輸時(shí)間。根據(jù)任務(wù)A、B、C的執(zhí)行，所有子任務(wù)置入就緒隊(duì)列中。由于任務(wù)A和C在相同實(shí)例上執(zhí)行，兩個(gè)任務(wù)間的數(shù)據(jù)傳輸時(shí)間為0。而任務(wù)B必須等待接收其父任務(wù)的數(shù)據(jù)才能開始。任務(wù)D可以分別在時(shí)間13和9時(shí)在實(shí)例p0和p1上開始執(zhí)行。

(a) 工作流示例(b) 調(diào)度圖

任務(wù)E在實(shí)例p0上的最早開始時(shí)間為13，在實(shí)例p1上為14。因此，任務(wù)D賦予更高優(yōu)先級。

任務(wù)ti在執(zhí)行時(shí)間最短的實(shí)例上的最早開始時(shí)間(EST)定義為：

EST(ti)=

(3)

式中:wtj為任務(wù)tj在最快實(shí)例上的執(zhí)行時(shí)間，pred(ti)為任務(wù)ti的父任務(wù)集合，Ci,j為任務(wù)ti與tj間的傳輸數(shù)據(jù)的通信時(shí)間。

任務(wù)選擇從入口任務(wù)tentry所在的分級開始執(zhí)行，第一分級執(zhí)行之后，下一分級中的所有任務(wù)被置入待調(diào)度的就緒隊(duì)列中。

2.4 實(shí)例選擇

BDWTS的目標(biāo)是在滿足用戶截止時(shí)間的同時(shí)最小化工作流執(zhí)行時(shí)間。每一分級獲得的預(yù)算分割為該分級上任務(wù)所能花費(fèi)的最大預(yù)算。為了選擇執(zhí)行任務(wù)的最優(yōu)目標(biāo)實(shí)例，算法通過以下公式計(jì)算每個(gè)任務(wù)在各個(gè)實(shí)例上的執(zhí)行代價(jià)Cost集和執(zhí)行時(shí)間Time集:

(4)

(5)

式中:subBudget為該分級的預(yù)算分割;Ci為當(dāng)前任務(wù)ti調(diào)度至實(shí)例pj上的代價(jià);Cbest為所有實(shí)例中執(zhí)行當(dāng)前任務(wù)的最小代價(jià);ECT(ti,pj)為當(dāng)前任務(wù)ti在實(shí)例pj上的執(zhí)行時(shí)間;ECT(max)和ECT(min)分別為在所有實(shí)例上執(zhí)行當(dāng)前任務(wù)的最大和最小時(shí)間。

為了尋找最優(yōu)實(shí)例，利用時(shí)間/代價(jià)均衡因子TCTF(Time Cost Trade-off Factor)進(jìn)行度量，則

(6)

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)配置

利用CloudSim[10-11]對算法進(jìn)行仿真分析，云環(huán)境配置為一個(gè)數(shù)據(jù)中心，6種不同實(shí)例類型，具體配置見表1所示。實(shí)例帶寬固定設(shè)置為20 MB/s，EC2的處理能力以每秒百萬浮點(diǎn)操作數(shù)(Million Floating Point Operations Per Second,MFLOPS)度量[12-13]。

為了評估BDWTS算法中預(yù)算分割策略對性能的影響，設(shè)置不同的預(yù)算范圍，調(diào)度工作流的最小可能預(yù)算通過下式計(jì)算：

Lowsetcost=∑?ti∈GCosttipj

(7)

式中，pj為價(jià)格最低的實(shí)例。通過將所有任務(wù)調(diào)度至最低代價(jià)的實(shí)例上執(zhí)行即可獲得該值。該方式可以得到執(zhí)行代價(jià)最低的調(diào)度方式。利用該最低代價(jià)，可以計(jì)算最小預(yù)算為：

budget=α×Lowsetcost, 1<α<10

(8)

設(shè)置工作流任務(wù)數(shù)量為1 000，利用Pegasus工作流產(chǎn)生器[14]創(chuàng)建與科學(xué)工作流LIGO相似的合成工作流結(jié)構(gòu)[15]作為測試數(shù)據(jù)源，其結(jié)構(gòu)如圖3所示。

圖3 LIGO工作流結(jié)構(gòu)圖

3.2 結(jié)果分析

對于擁有1 000個(gè)任務(wù)LIGO工作流，每一分級中的任務(wù)數(shù)量、預(yù)算分割與剩余預(yù)算如表3所示。例如：利用Height算法調(diào)度第一分級中的所有任務(wù)后，剩余預(yù)算0.15被增加至下一分級的預(yù)算中，導(dǎo)致該分級預(yù)算為1.69。表最后一行表示每種策略的執(zhí)行時(shí)間。

表4為不同預(yù)算分割策略的實(shí)例使用數(shù)量情況。可以看出，All in算法分配了更小數(shù)量的高性能實(shí)例，降低了數(shù)據(jù)傳輸代價(jià)，得到了最少的執(zhí)行時(shí)間(見表3)。對于用戶而言，更傾向于尋找滿足預(yù)算且執(zhí)行時(shí)間更少的調(diào)度方案，而對于資源提供方而言，更傾向于最大化資源利用率。盡管不同的預(yù)算分割方法下的BDWTS算法均可以得到可行解，但所使用的實(shí)例類型和數(shù)量是各不相同的。開啟更多實(shí)例并不一定會帶來更低的執(zhí)行時(shí)間，相反，會導(dǎo)致更高的調(diào)度開銷和低利用率。因此，預(yù)算分割策略對資源利用率是有直接影響的。

表3 算法的預(yù)算分割情況

表4 不同預(yù)算分割策略的實(shí)例使用情況

圖4給出了LIGO工作流的執(zhí)行時(shí)間。可以看出，All in策略在兩種性能指標(biāo)均優(yōu)于其他算法，而Random策略則是性能最差的。圖5是本文算法與BHEFT算法在代價(jià)上的比較結(jié)果，此時(shí)BDWTS的預(yù)算分割采取All in策略，顯然，通過不同分級上的預(yù)算分割的BDWTS獲得了更低的代價(jià)。

圖4 執(zhí)行時(shí)間

圖5 執(zhí)行代價(jià)

4 結(jié) 語

為了解決云環(huán)境中科學(xué)工作流的調(diào)度優(yōu)化問題，提出一種工作流均衡調(diào)度算法。算法集中于解決工作流預(yù)算約束下的代價(jià)與時(shí)間優(yōu)化問題，算法通過將尋找最優(yōu)調(diào)度方案劃分為工作流分級、預(yù)算分割、任務(wù)選擇和實(shí)例選擇4個(gè)階段，實(shí)現(xiàn)了預(yù)算約束下的時(shí)間與代價(jià)均衡調(diào)度。實(shí)驗(yàn)結(jié)果證明了算法的有效性。

參考文獻(xiàn)(References)：

[1] WU F, WU Q, TAN Y. Workflow scheduling in cloud: a survey[J]. Journal of Supercomputing, 2015,71(9):1-46.

[2] ZHENG W, SAKELLARIOU R. Budget-Deadline Constrained Workflow Planning for Admission Control[J].Journal of Grid Computing,2013,11(4):633-651.

[3] ARABNEJAD V, BUBENDORFER K. Cost effective and deadline constrained scientific workflow scheduling for commercial clouds[C]//In International Symposium on Network Computing and Applications. IEEE, 2016:106-113.

[4] ARABNEJAD V, BUBENDORFER K, Ng B,etal. A deadline constrained critical path heuristic for cost-effectively scheduling workflows[C]//In 2015 IEEE/ACM 8th International Conference on Utility and Cloud Computing.IEEE,2015:242-250.

[5] ZENG L, VEERAVALLI B, LI X. Scalestar: Budget conscious scheduling precedence-constrained many-task workflow applications in cloud[C]//In 2012 IEEE 26th International Conference on Advanced Information Networking and Applications,2012:534-541.

[6] LIN X, WU C Q. On scientific workflow scheduling in clouds under budget constraint[C]//International Conference on Parallel Processing. IEEE, 2013:90-99.

[7] WU C Q, LIN X, YU D,etal. End-to-End Delay Minimization for Scientific Workflows in Clouds under Budget Constraint[J]. IEEE Transactions on Cloud Computing, 2015, 3(2):169-181.

[8] MAO M, HUMPHREY M. Scaling and scheduling to maximize application performance within budget constraints in cloud workflows[C]//In International Symposium on Parallel & Distributed Processing. IEEE, 2013:67-78.

[9] 馬俊波,殷建平,云計(jì)算環(huán)境下帶安全約束的工作流調(diào)度問題的研究[J],計(jì)算機(jī)工程與科學(xué),2014,36(4):607-614.

[10] GOYAL T, SINGH A, AGRAWAL A. Cloudsim: Simulator for cloud computing infrastructure and modeling[J]. Procedia Engineering, 2012, 38(4):3566-3572.

[11] RODRIGO C, RAJIV R, ANTON B,etal. CloudSim: A toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J]. Software: Practice and Experience, 2011, 41(1): 23-50.

[12] YI S, ANDRZEJAK A, KONDO AND D. Monetary cost-aware checkpointing and migration on amazon cloud spot instances[J], IEEE Transactions on Services Computing, 2012,5(4):512-524.

[13] CHARD R, CHARD K, KRIS B,etal. Cost-aware cloud provisioning[C]//in the IEEE 11th International Conference on E-Science, August 2015.136-144.

[14] JUVE G, CHERVENAK A, Deelman E,etal. Characterizing and profiling scientific workflows[J]. Future Generation Computer Systems, 2013, 29(3):682-692.

[15] 鄭 敏，曹 健，姚 艷，面向價(jià)格動(dòng)態(tài)變化的云工作流調(diào)度算法[J]，計(jì)算機(jī)集成制造系統(tǒng)，2013，19(8):1849-1858.