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

0 引 言

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

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

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

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

1.1 工作流模型

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

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

1.2 系統(tǒng)模型

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

表1 資源實例類型

注：ECU：Elastic Compute Unit，彈性計算單元

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

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

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

(1) 工作流分級?；诠ぷ髁魅蝿?wù)的同步需求，將工作流任務(wù)進行分級(level)。

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

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

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

2.1 工作流分級

工作流分級的目標(biāo)是通過任務(wù)分級最大化任務(wù)執(zhí)行的并行程度，使得同一分級中的任務(wù)與其它分級中的任務(wù)不具有依賴性。因此，每個分級可視為包括獨立任務(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ù)進行子劃分。本文設(shè)計了以下6種預(yù)算分割算法：

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

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

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

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

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

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

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

圖1 工作流示例

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

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

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

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

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

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

4×BF=4×11=44。

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

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

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

預(yù)算因子BF為：

然后，預(yù)算根據(jù)圖1中右欄中的數(shù)值之和進行分割。例如：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í)行，置入就緒任務(wù)隊列中。為了從中選擇調(diào)度任務(wù)，需要為就緒隊列中的任務(wù)分配優(yōu)先級。本文設(shè)計一種基于最早開始時間(Earliest Start Time,EST)的優(yōu)先級任務(wù)選擇算法。

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

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

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

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

EST(ti)=

(3)

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

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

2.4 實例選擇

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

(4)

(5)

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

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

(6)

3 仿真實驗

3.1 實驗配置

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

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

Lowsetcost=∑?ti∈GCosttipj

(7)

式中，pj為價格最低的實例。通過將所有任務(wù)調(diào)度至最低代價的實例上執(zhí)行即可獲得該值。該方式可以得到執(zhí)行代價最低的調(diào)度方式。利用該最低代價，可以計算最小預(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個任務(wù)LIGO工作流，每一分級中的任務(wù)數(shù)量、預(yù)算分割與剩余預(yù)算如表3所示。例如：利用Height算法調(diào)度第一分級中的所有任務(wù)后，剩余預(yù)算0.15被增加至下一分級的預(yù)算中，導(dǎo)致該分級預(yù)算為1.69。表最后一行表示每種策略的執(zhí)行時間。

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

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

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

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

圖4 執(zhí)行時間

圖5 執(zhí)行代價

4 結(jié) 語

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

參考文獻(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] 馬俊波,殷建平,云計算環(huán)境下帶安全約束的工作流調(diào)度問題的研究[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] 鄭 敏，曹 健，姚 艷，面向價格動態(tài)變化的云工作流調(diào)度算法[J]，計算機集成制造系統(tǒng)，2013，19(8):1849-1858.