云环境中期限分割下工作流调度代价优化仿真

2018-11-16刘晓霞

实验室研究与探索 2018年10期

刘晓霞, 李芳

(1. 四川水利职业技术学院信息工程系，四川崇州 611231; 2. 重庆大学计算机学院，重庆 400044)

0 引言

工作流被广泛应用于大型复杂问题建模，云计算的工作过程调度问题是非常复杂的，故适合利用工作流来研究其过程调度问题[1]。不同于传统的独立任务调度问题，工作流任务的数据计算与通信代价更高更复杂，其本质是实现关联式任务与资源间的调度与分配，同时需满足规定的服务质量(Quality of Service, QoS)约束。求解工作流调度问题有两个重要阶段：选择被调度任务和选择提供的实例。两个阶段的决策对于调度方案的全局代价与是否可满足全局期限约束均具有重要影响。一种方法是将全局期限在工作流间进行分割得到子期限以确保约束满足问题，然后在实例提供时仅满足子期限即可。这其中需要解决两个关键问题：① 以何种方法将期限在工作流中进行分割？② 不同的分割策略对调度代价如何？

传统工作流调度方法仅注重于优化执行效率，即降低任务执行时间，但云资源的使用通常是有偿付费的，资源能力越高，价格越高，此时，使用不同资源及不同调度方案得到的执行代价和时间是不同的，必须更加注重资源利用代价的优化。进而，云环境中的工作流调度需要同步考虑用时间和代价问题。

1 云计算工作流研究现状

将工作流任务分配至资源划分为两个阶段：调度与提供[2]。给定资源集，工作流任务调度阶段目标是决定最优的任务执行序列和对应于用户和工作流约束的任务部署[3-4]。资源提供阶段目标是决定所要求的资源数量和类型，并为工作流执行预留该资源[5-6]。

国内外研究者们，对云计算工作流方面进行了相关研究。文献[7-8]中给出了自底向上算法(Deadline Bottom Level, DBL)和自顶向下算法(Deadline Top Level, DTL)，两种经典的期限分配启发式算法；DBL将任务以自底向上的方式进行分类，而DTL以自顶向下的方式进行。DBL中的任务被组织为不同的层次，每一层次中的任务不具有相关依赖性；DTL中任务被划分为不同路径作为同步任务或简单任务，同步任务定义为拥有一个以上父任务或子任务的任务；在期限分布阶段，全局期限被分割并以正比于每个层次的最小执行时间的方式进行分割；在DBL中，首先需要计算最快的实例，然后将用户定义的期限与估算值之差均匀分布方式在所有层次间。文献[9]中将工作流任务划分为两种类型：关键和非关键任务；在关键路径上的所有任务在给定期限下利用动态规划进行调度非关键任务则在关键任务间进行回填法进行调度且该算法在调度过程中忽略了任务间的通信时间。文献[10]中提出了正比例期限约束云工作流调度算法，算法将期限以正比于各层次中任务执行时间的方式在层次间进行分割。文献[11-12]中提出最迟完成时间算法将期限在各任务间进行分割，算法是在用户定义期限条件完成下确保工作流时任务可完成其执行的最早时间。文献[12]中提出局部关键路径算法根据任务在工作流中所处的局部关键路径对任务进行分类，期限根据定义的路径重分配，其缺点在于每个局部关键路径执行后，需要重新计算最迟完成时间。文献[11]中提出一种期限约束下的动态代价最小化算法，该算法尝试联合管道任务集为单个任务，以消除任务间的数据传输时间；但该算法并未为任务寻找最佳执行实际，不能实现最优化。这些研究，促进了云计算工作流的发展和进步，但未解决云计算中服务时间有限情况下的工作流调度与优化问题。

因此，本文针对现有在云计算工作流存在的不足，拟对云计算中即付即用服务中的期限约束下的工作流调度优化问题进行研究，提出提出一种期限分割的工作流调度代价优化算法(Workflow Scheduling Cost Optimization under Deadline Distribution,WSCO-DD)，并对算法进行仿真验证。

2 系统模型

定义工作流为有向无循环图(Directed Acyclic Graph, DAG)G=(T,E)，T={t0,t1,…,tn}为图顶点集，即待调度的任务集合，E={ei,j|ti,tj∈T}为图边集，代表两个任务间的数据传递性。有向边ei,j∈E(ti,tj∈T)代表两个任务间的执行顺序，即：仅当任务ti执行完成并接收ti的所有数据后，任务tj才开始执行。即：任务ti是tj的父任务，tj是ti的子任务。任务间的父子关系为多对多关系，即一个任务可拥有多个子任务，也可作为多个任务的父任务。并且，只有所有父任务完成，子任务ti才可以开始执行。

在实例pj上执行任务ti的代价为：

TaskCostpjti=wpjti/Nt×cj

(1)

执行工作流的所有任务的总代价为：

(2)

云可以提供不同定价和类型的实例，实例在CPU、内存、存储和带宽上具有不同的能力。工作流结构中的任务根据其需求可执行于不同类型的实例上，每种实例类型可认为是一个资源集合。本文的云资源以Amazon EC2为实例进行建模(由于Amazon EC2是当前最普遍的资源实例类型)，使用方式为按需提供。支付模型以最小账单时间的即付即用方式建立，即账单时间内少于帐单时间的实例使用均以一个账单时间支付费用。假设云供应商可提供无上限的异构实例数量，表示为：P={p0,p1,…,pn}，h为实例类型的索引；且假设所有实例均位于同一区域内，则实例间的平均带宽也视为相同的。

3 期限分割的工作流调度代价优化算法WSCO-DD

WSCO-DD算法分为4个阶段：

(1) 工作流分层。根据工作流结构中任务间的关联次序，对任务进行层次划分。

(2) 期限分割。将用户定义的期限Deadline在每个层次间进行分割，每个层次得到其子期限，同一层次中的所有任务拥有相同的层次期限。

(3) 任务选择。赋予任务优先级，得到任务调度序列。

(4) 实例选择。选择任务执行的最优实例，在满足可用期限的同时最小化执行代价。

3.1 工作流分层

对工作流结构中的任务进行层次划分可以区分独立任务与关联任务，从而实现任务的最大并行化执行，且假设处于同一层次中的任务与其它层次的任务间相互独立。令任务ti的层次为该任务与工作流出口间的所有路径边的最大值，表示为NL(ti)。出口任务的层次始终为1，其他任务为：

NL(ti)=maxtj∈succ(ti){NL(tj)+1}

(3)

其中：succ(ti)表示任务ti的子任务集。那么，以l表示层次，相同层次的任务可组成一个集合，定义为TL，则：

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

(4)

3.2 期限分割

3.2.1初始值估算

对于每个层次的初始估算期限计算为：

InitialTsd(l)=maxti∈TLS(l){ECT(ti)}

(5)

式中:ECT(ti)为ti在所有资源上的最早完成时间，定义为：

(6)

式中:EST(ti)定义为式(9);pred(ti)为任务ti的父任务集;wti为任务ti的最小执行时间;l为父任务ti所处的分层。若任务tentry不存在前驱，则有ECT(tentry)=0。

式(5)表明，一个分层的所有任务的最大ECT可视为该层的全局完成时间估算，该时间可作为所处分层中所有任务并行执行时要求的绝对最小完成时间。

3.2.2期限分割方法

期限分割的目标是工作流总体期限在不同层次间进行子划分，使得各层次在其分配的子期限内完成，并确保工作流执行满足全局期限。本文设计以下几种基准期限分割算法：

(1) 随机法Random，简称R。以随机方式将期限在工作流各层次上进行分割。

(2) 平均法Uniform，简称U。将期限平均分割至每个层次，各层次期限分割相等。

(3) 高度法Height，简称H。层次得到的期限分割和层次与工作流入口的距离成正比。则距离越近，期限分割越小。

(4) 宽度法Width，简称W。层次得到的期限分割与该层次包含的任务数量成正比。任务越多，期限分割越大。

(5) 区域法Area，简称A。联立H与W法进行期限分割。

(6) 长度正比例分割算法Length，简称L。每个层次根据与其长度正比的方式以非均匀方式得到期限分割，任务越长的层次得到的期限分割也越长。

通过一个实例说明不同期限分割方法的实现原理。图1所示为一种工作流结构示例，该工作流的任务总数为10，图中给出了工作流的分层结构及各层次中的任务。可以看出，该工作流结构最大层次Nmax=5。假设此时期限为150。

图1 工作流示例

R算法该算法对期限进行随机分割，不作说明。

U算法工作流层次数为5，则每个层次的期限分割为150/5=30。

H算法定义工作流层次的高度权值：

则期限因子DF=deadline/Lweight=150/15=10。对于层次3(包含4个任务)而言，期限分割为3×DF=3×10=30。其他层次同理。

W算法层次的期限分割取决于包含的任务数量，则期限因子DF=deadline/n=150/10=15。则对于层次3(包含4个任务)而言，期限分割为4×DF=4×15=60。其他层次同理。

A算法联立H和W算法，此时权值为：

期限因子DF=deadline/Lweight=150/55=2.73。

然后，期限根据TL中的数值之和进行分割。如：层次3 的期限分割为(4+5+6+7)×DF=22×2.73=60。其他层次同理。

L算法计算所有层次的期限估算值后，需要以正比于πdeadline的方式，将用户定义的执行期限在所有任务上进行非均匀重分配，πdeadline定义为：

(7)

其中，InitialTsd(1)表示包含出口任务texit的分层值， sd(sub-deadline,sd)表示子期限。

然后，每个层次期限长度为正比于该层次期限的函数：

Tsd(l)=InitialTsd(l)+

(πdeadline×|InitialTsd(l)|)

(8)

显然，分层中的任务越长，该分层得到子期限也越长。表1给出各个算法的期限分割的详细情况。对应于每一个层次，第1行为每一层次得到的期限分割值，第2行为分配子期限至每一层次后的期限剩余值，该值基于先前层次中的分割值进行累积计算。显然，第一个层次的子期限值应为总体期限值。例如，层次4的H策略中，期限分割为40，而待分配的子期限为90。表1中未给出L策略得到的期限分割，原因在于该方法需计算每个任务的执行时间，需结合具体参数进行。

表1 预算分割情况

本文还利用基准期限分割方法的不同组合，进一步得到不同的分割方法。例如：联合E、W和L 3种方法，产生新的期限分割方法EWL，其中，E表示每个层次的初始估算期限，由式(5)表示。该策略中，首先，为所有层次计算期限估算值，然后，剩余期限基于W和L方法的联合进行分配。通过组合不同方法，可产生14种期限分割方法，如图2所示。

图2 不同策略组合

3.3 任务选择

WSCO-DD算法中，待执行的就绪任务放入就绪任务列表中。当所有父任务执行完成并接收所有数据后，任务可视为就绪任务。因此，在同一工作流层次中，其任务间无依赖性。为了选择合适的任务执行，就绪任务列表中的所有任务以最早开始时间EST赋予任务优先级。EST为任务可开始执行的最早可能时间，取决于其父任务的完成时间。任务ti的最早开始时间EST计算为在拥有最短执行时间的实例上得到的执行时间：

(9)

式中：wtj为任务tj在最快实例上的执行时间;Ci,j为任务ti与tj间的传输数据的通信时间;pred(ti)为任务ti的父任务集合。对于每个任务，计算其在所有实例上的EST，最先开始执行的任务即被选择为执行侯选任务。

3.4 实例选择

该阶段的目标是选择最优的任务执行实例，选择标准是在满足任务的子期限的同时，最小化工作流执行总代价。引入涉及实例比率ICR的目标函数：

(10)

云服务提供商，如Amazon EC2，均以1 h时间周期向用户收取费用。云实例提供后，用户需要支付整个帐单周期费用，即使其任务在帐单时间结束前完成。那么，如果其他任务能执行于还剩余帐单时间的同一实例上，则其调度代价即为0。因此，当分配实例时，算法优先选择仍剩余帐单时间的实例。算法的第一步即选择执行当前任务无代价的实例，同时需要确保任务的最早完成时间不超过该层次的分割期限。然后选择拥有最小ECT的实例，即最快实例。

如果不存在以上条件的实例，算法基于最高ICR值的原则开启一个新的实例。对于严格期限约束而言，可能更低价的实例无法满足任务层次的子期限约束。因此，式(10)的分子为负值，导致ICR也为负值。如果出现该情况，则需要为当前任务选择价格更高的实例。可以看出，ICR可以调整任务在所有实例上的执行代价和时间。为了最小化执行代价，文献[20]中试图将任务调度至价格最低的实例上，同时满足其分配的子期限。然而，该方法中，如果资源过慢，会导致任务的子任务的EST出现延迟，进而导致任务的执行时间变长。为了避免此情况，本文设置ICR=20以均衡执行时间和代价。

4 仿真实验

4.1 实验配置

基于WorkFloSim[13]仿真平台对算法进行仿真实验，平台中配置为一个云数据中心，由6种不同的实例类型组成，具体配置见表2。实例带宽固定设置为20 MB/s，EC2的处理能力以1 m/s浮点操作数MFLOPS度量。同时，在定价模型方面，本文使用基于Amazon EC2弹性计算云的资源模型，其实例类型按需提供，其定价使用即付即用的1 h帐单机制，所有小于1 h的资源使用，均按1 h支付。

表1 资源实例类型

利用两种科学工作流作为现实负载评估算法性能。相似的合成工作流结构作为测试数据源，其结构如图3所示。将期限约束在严格与宽松间进行动态设置，令FS表示最快调度，作为基准调度方案。该基准值为忽略执行代价时得到的执行时间，表示为：

(11)

定义工作流期限为最快调度的函数，表示为：期限=α×FS，这样使得期限值在相对的严格-适中-宽松中变化，其中α为期限因子，α∈[0,20]，α可以按某步长进行递增，其值越小，期限约束越严格，其值越大，期限约束越宽松。

同时，Amazon EC2的云实例以1 h作为帐单服务时间，仿真中应用该价格模型。设置工作流的任务总数为1 000。仿真结果以10次实验的平均值作为标准。

(a) 基因工作流结构(b) 网络空间工作流结构

图3 工作流结构图

4.2 实验分析

实验1观察不同期限分割方法的性能，性能指标为满足期限时的失效代价。令k为成功满足调度期限的仿真集合，分配于算法的权重代价计算为：

Costw=∑kCosto(k)/SR

(12)

式中:Costo(k)为满足期限时得到的代价;SR为调度成功率。

如图4所示，可得到不同策略具有不同的变化趋势。如：W策略在网络空间工作流中性能最差，而在基因工作流中则拥有最低的代价； EL策略在网络空间工作流和基因工作流中的趋势相似。这主要是源于工作流在结构、规模、计算和通信需要等方面的特征均有所不同。综合来看，EWL策略在不同的工作流结构中均具有较好的性能，源于该策略同步考虑了层次中任务的数量和层次的长度。因此，下文实验中算法WSCO-DD的期限分割方法将应用EWL策略。同时，部分策略间的代价差异虽然较小，但可以看出期限分割方法仍对工作流的执行代价会产生实质影响[15]。

实验2观察算法执行代价和调度成功率。选择基础设施即服务云关键路径算法(Infrastructure as a Service, IaaS) Cloud Partial Critical Paths, IC-PCP)、联合诱导传输算法(Joint Induce Transmission, JIT)和比例截止日期约束算法(Proportion Deadline Constraint,

(a) 基因工作流

(b) 网络空间工作流

PDC)3种算法作为比较算法，结果如图5～6所示。可以看出，在所有工作流中，JIT的代价是最高的，而WSCO-DD算法几乎在所有工作流中拥有最低代价和最高的调度成功率。只有少数情况下，如极严格期限约束时的CyberShake和Epigenomics工作流，WSCO-DD算法才出现无法调度部分工作流的情形。IC-PCP算法在严格期限下拥有最差的调度成功率，期限的宽松会增加所有算法的调度成功率，这是由于任务的执行拥有了更长的时间限制。在Epigenomics中即使较宽松的期限，IC-PCP仍拥有最高的失效率，满足期限的调度仅占25%。JIT在多数期限条件下性能均较好，调度成功率接近100%。然而，JIT的执行代价过高，未均衡考虑代价与调度成功率间的平衡，这主要是由于该算法并未优化实例目标选择。