基于云环境的科学工作流均衡调度算法

朱亚东， 李 忠， 严 莉， 陈湘军(.江苏联合职业技术学院 南京工程分院信息中心，南京 5；.常州轻工职业技术学院 信息工程系，江苏 常州 000；.南京大学 电子工程学院，南京 0046)

0 引 言

科学工作流广泛应用于大型复杂科学应用建模，云计算环境提供的即付即用计算能力及定制式硬件设施，是调度科学工作流应用的一种有效方法[1]。与传统工作流不同，科学工作流规模更大，任务的数据计算与通信代价更高，其本质是实现相互依赖的任务至资源间的映射，同时要求满足用户定义的QoS约束(截止时间或预算)。传统工作流调度算法仅侧重于考虑优化执行效率(执行时间)，未考虑资源代价，而云是商业化环境，其资源使用是有偿付费的，资源能力越高，价格越高，此时，使用不同资源及不同调度方案得到的执行代价和时间是不同的。因此，云环境下的工作流调度需要同步考虑用时间和代价。

相关研究中，文献[2]中提出一种预算约束异构最早完成时间算法BHEFT，算法引入当前任务预算因子到未调度任务的剩余预算分配中，与本文不同的是，其任务预算与剩余预算是逐个任务分配的。文献[3,4]中则仅侧重于截止时间的约束及截止时间在不同任务或不同分级间的分割，不适应于云环境。文献[5]中提出预算感知回溯调度算法实现了多任务工作流的优化调度，文献[6-7]中则提出一种预算约束的最小端到端延迟工作流调度算法，通过在关键路径上应用贪婪策略寻找调度方案，然而，以上3个文献中的资源代价模型并不适应于商业云特征。文献[8]中提出基于自动扩展方法求解预算约束下的工作流调度，而本文将根据任务优先级采用正比例方式进行预算分割。

不同于以上工作，本文将重点关注于通过预算分割的方式优化工作流的执行代价与执行时间，在工作流分级及在不同分级上赋予待调度任务优先级的方式，实现最优目标实例资源的选择，最终完成科学工作流的代价与时间同步最优的均衡调度。

1 工作流与系统模型

1.1 工作流模型

以有向无循环图(Directed Acyclic Graph,DAG)表示工作流模型[9]，定义为G=(T,E)，其中，T={t0,t1,…,tn}表示图的顶点代表的任务集，E={ei,j|ti,tj∈T}表示图的边集，代表任务间的数据或控制依赖性。

边ei,j∈E表示两个任务ti与tj间的有向边，ti,tj∈T，代表两个任务间的优先顺序约束，其具体含义是：仅当任务ti执行完成后并收到ti的所有数据后，任务tj才可以开始执行。换言之，任务ti是tj的父任务，tj是ti的后继或子任务。单个任务可拥有一个或多个父任务和子任务。直到其所有父任务完成后，子任务ti才可以开始执行。

1.2 系统模型

云资源提供者可提供多种类型的实例，拥有不同的CPU、内存、存储和带宽能力，且配置不同的使用价格。本文使用基于弹性计算云Amazon EC2(Amazon Elastic Compute Cloud，Amazon)的资源模型，其实例类型按需提供，其定价利有即付即用的最小小时计费模型，即：小于1 h的资源使用，均按1 h支付。表1是本文中所使用的资源代价与实例类型的相关参数配置，更新于2016年3月的Amazon EC2数据。

表1 资源实例类型

注：ECU：Elastic Compute Unit，弹性计算单元

假设云资源提供者可提供无限制异构实例数量，表示为P={p0,p1,…,ph}，其中，h表示实例类型索引。假设所有实例类型和存储服务处于同一云数据中心内，则不同实例间的平均带宽可视为基本相等的。

2 预算分割工作流均衡调度算法

基于预算分割的均衡工作流调度算法(Budget Division Workflow Trade-off Scheduling,BDWTS)划分为以下4个阶段：

(1) 工作流分级。基于工作流任务的同步需求，将工作流任务进行分级(level)。

(2) 预算分割。将用户定义的预算(Budget)按6种不同的策略在不同的任务分级间进行分割。

(3) 任务选择。在任务就绪队列中基于优先级原则选择调度任务。

(4) 实例选择。选择最优目标实例执行任务，满足可用预算约束。

2.1 工作流分级

工作流分级的目标是通过任务分级最大化任务执行的并行程度，使得同一分级中的任务与其它分级中的任务不具有依赖性。因此，每个分级可视为包括独立任务的批任务集(Bag of Tasks,BoTs)。

定义任务ti的分级为以自顶向下的方式，任务ti至工作流的出口任务间的所有路径的边的最大值，表示为NL(ti)。对于出口任务，分级为1，对于其他任务：

(1)

式中，succ(ti)表示任务ti的直接后继子任务集合。然后，根据任务分级，将所有拥有相同分级的任务组成任务分级集合(Task Level Sets,TLS)，则：

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

(2)

式中,l表示分级数，且l∈[1,…,NL(tentry)]。

2.2 预算分割

基于工作流的分级结果，预算分割的目标是将用户定义的工作流预算在不同分级任务进行子划分。本文设计了以下6种预算分割算法：

(1) 随机分割算法Random。预算随机分配于工作流的不同分级上。

(2) 平均分割算法Uniform。每个工作流分级得到用户预算的1/L，其中，L表示工作流总分级数。

(3) 高度正比例分割算法Height。每个工作流分级得到的预算分割正比于工作流分级与入口节点的距离，则该距离越小，预算分割越小。

(4) 宽度正比例分割算法Width。每个工作流分级得到的预算分割正比于该分级中任务的数量。

(5) 区域正比例分割算法Area。联合Width算法和Height算法设置每个分级的预算分割。

(6) 全进分割算法All in。将用户预算全部分配至入口任务，然后将剩余预算依次传递至下一分级。该算法可视为Height算法的精炼算法。

以下通过一个算例说明以上6种算法所描述的预算在不同分级间的分割方法。Random算法是随机产生预算分割，因此不作额外说明。图1所示是一个拥有10个任务的工作流结构，图中左侧一栏是通过式(1)计算得到的工作流分级值，右侧一栏是从出口任务开始对每一级任务的标记。该工作流中，最大分级Nmax=5。同时，设置用户预算Budget=165。

图1 工作流示例

每种算法得到的预算分割如下所示(表2给出预算分割的完整情况)：

Uniform算法由于工作流共有5个分级，故每个分级获得165/5的预算分割。

Height算法每个分级分配一个相对于工作流分级的预算加权值，表示为：

预算因子(Budget Factor,BF)为：

例如：level 4包括任务B和C，则所分配的预算为

表2 算法的预算分割情况

4×BF=4×11=44。

Width算法每个分级得到的预算分割取决于对应分级中的任务数量，此时的预算因子为：

例如：level 4包括两个任务，则所分配的预算为2×BF=2×16.5=33。

Area算法该算法的预算分割为Height和Width算法的联合，计算为：

预算因子BF为：

然后，预算根据图1中右栏中的数值之和进行分割。例如：level 3的预算分割为(4+5+6+7)×BF=22×3=66。

Allin算法总预算分配至level 5。调度该分级上的所有任务后，剩余预算传递至下一分级中。

2.3 任务选择

由于任务的分级特征，这表明只有前一分级中的所有任务调度之后，该任务才能开始执行。而同一分级中的任务间不存在依赖性，因此，均可以准备执行，置入就绪任务队列中。为了从中选择调度任务，需要为就绪队列中的任务分配优先级。本文设计一种基于最早开始时间(Earliest Start Time,EST)的优先级任务选择算法。

如图2所示的工作流示例，边上的数值表示任务间的数据传输时间。根据任务A、B、C的执行，所有子任务置入就绪队列中。由于任务A和C在相同实例上执行，两个任务间的数据传输时间为0。而任务B必须等待接收其父任务的数据才能开始。任务D可以分别在时间13和9时在实例p0和p1上开始执行。

(a) 工作流示例(b) 调度图

任务E在实例p0上的最早开始时间为13，在实例p1上为14。因此，任务D赋予更高优先级。

任务ti在执行时间最短的实例上的最早开始时间(EST)定义为：

EST(ti)=

(3)

式中:wtj为任务tj在最快实例上的执行时间，pred(ti)为任务ti的父任务集合，Ci,j为任务ti与tj间的传输数据的通信时间。

任务选择从入口任务tentry所在的分级开始执行，第一分级执行之后，下一分级中的所有任务被置入待调度的就绪队列中。

2.4 实例选择

BDWTS的目标是在满足用户截止时间的同时最小化工作流执行时间。每一分级获得的预算分割为该分级上任务所能花费的最大预算。为了选择执行任务的最优目标实例，算法通过以下公式计算每个任务在各个实例上的执行代价Cost集和执行时间Time集:

(4)

(5)

式中:subBudget为该分级的预算分割;Ci为当前任务ti调度至实例pj上的代价;Cbest为所有实例中执行当前任务的最小代价;ECT(ti,pj)为当前任务ti在实例pj上的执行时间;ECT(max)和ECT(min)分别为在所有实例上执行当前任务的最大和最小时间。

为了寻找最优实例，利用时间/代价均衡因子TCTF(Time Cost Trade-off Factor)进行度量，则

(6)

3 仿真实验

3.1 实验配置

利用CloudSim[10-11]对算法进行仿真分析，云环境配置为一个数据中心，6种不同实例类型，具体配置见表1所示。实例带宽固定设置为20 MB/s，EC2的处理能力以每秒百万浮点操作数(Million Floating Point Operations Per Second,MFLOPS)度量[12-13]。

为了评估BDWTS算法中预算分割策略对性能的影响，设置不同的预算范围，调度工作流的最小可能预算通过下式计算：

Lowsetcost=∑∀ti∈GCosttipj

(7)

式中，pj为价格最低的实例。通过将所有任务调度至最低代价的实例上执行即可获得该值。该方式可以得到执行代价最低的调度方式。利用该最低代价，可以计算最小预算为：

budget=α×Lowsetcost, 1<α<10

(8)

设置工作流任务数量为1 000，利用Pegasus工作流产生器[14]创建与科学工作流LIGO相似的合成工作流结构[15]作为测试数据源，其结构如图3所示。

图3 LIGO工作流结构图

3.2 结果分析

对于拥有1 000个任务LIGO工作流，每一分级中的任务数量、预算分割与剩余预算如表3所示。例如：利用Height算法调度第一分级中的所有任务后，剩余预算0.15被增加至下一分级的预算中，导致该分级预算为1.69。表最后一行表示每种策略的执行时间。

表4为不同预算分割策略的实例使用数量情况。可以看出，All in算法分配了更小数量的高性能实例，降低了数据传输代价，得到了最少的执行时间(见表3)。对于用户而言，更倾向于寻找满足预算且执行时间更少的调度方案，而对于资源提供方而言，更倾向于最大化资源利用率。尽管不同的预算分割方法下的BDWTS算法均可以得到可行解，但所使用的实例类型和数量是各不相同的。开启更多实例并不一定会带来更低的执行时间，相反，会导致更高的调度开销和低利用率。因此，预算分割策略对资源利用率是有直接影响的。

表3 算法的预算分割情况

表4 不同预算分割策略的实例使用情况

图4给出了LIGO工作流的执行时间。可以看出，All in策略在两种性能指标均优于其他算法，而Random策略则是性能最差的。图5是本文算法与BHEFT算法在代价上的比较结果，此时BDWTS的预算分割采取All in策略，显然，通过不同分级上的预算分割的BDWTS获得了更低的代价。

图4 执行时间

图5 执行代价

4 结 语

为了解决云环境中科学工作流的调度优化问题，提出一种工作流均衡调度算法。算法集中于解决工作流预算约束下的代价与时间优化问题，算法通过将寻找最优调度方案划分为工作流分级、预算分割、任务选择和实例选择4个阶段，实现了预算约束下的时间与代价均衡调度。实验结果证明了算法的有效性。

参考文献(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],计算机工程与科学,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] 郑 敏，曹 健，姚 艳，面向价格动态变化的云工作流调度算法[J]，计算机集成制造系统，2013，19(8):1849-1858.