兼顾费用与公平的带通信开销的多有向无环图调度

摘要：针对云环境下多有向无环图（DAG）工作流的调度算法应考虑执行时间、费用开销、通信开销、公平性等多个指标的问题，在模型带通信开销的DAG（CADAG）的基础上结合公平性算法提出一种优化完成时间的后向求异（BD）原则与兼顾费用和公平的多DAG调度策略CAFS。CAFS调度策略分为两个阶段：预调度阶段利用带通信开销的工作流费用优化（CACO）算法在考虑通信开销的同时求解所有任务的最优服务并优化费用，采用fairness算法得到较公平的调度顺序；调度阶段采用BD原则，根据在预调度阶段得出的调度顺序进一步优化整体的完成时间并执行调度。实验结果表明，CAFS调度算法具有较好的公平性，在不提高费用的基础上时间减少19.82%。

关键词：多有向无环图调度；通信开销；费用；公平；工作流

中图分类号： TP393

文献标志码：A

0引言

云环境中用户对使用的服务付费已经成为一种趋势。云服务提供商在大型服务器上部署多种服务[1]，根据各个服务的服务质量（Quality of Service， QoS）制定收费标准。用户向服务商提交的工作流由这些服务完成，每个工作流中包含多个任务，每个任务可以由若干个服务完成。云环境下对多个用户提交的工作流及其中的任务调度应考虑执行时间、费用开销、通信开销、公平性等多个指标，通常是一个NPhard问题[2]。单个工作流通常使用有向无环图（Directed Acyclic Graph， DAG）描述。工作流调度是指从云环境中的众多服务中根据用户的特定需求确定最优服务并假定所有服务都能提供与承诺一致的服务质量。针对单DAG截止前约束的优化调度已有诸多学者作了研究，

苑迎春等[2-4]提出的DBL（Deadline Bottom Level）基于分层算法，在分层之后逐层进行局部优化；在此基础上又提出了BSRD（Backward Serial Reduction with Deadline）对分层算法中的时间窗口重新定义，能为一个串归约得到局部最优解。刘灿灿等[5-6]的截止期约束逆向分层（Temporal Consistency based Deadline Bottom Level， TCDBL）算法基于DBL，研究工作流的时序特征，进一步优化了工作流的执行费用。然而上述算法均没有考虑到任务间跨节点的数据传输带来的不可忽视的通信开销[7]。郭禾等[8]提出的带通信开销的工作流费用优化（Communication Aware Cost Optimization，CACO）基于分层算法，并提出FC（Forward Consistent）规则求解考虑通信开销情况下的最小完工时间，优化了执行费用。上述这些算法都是考虑单DAG在一组资源下的调度执行，而在云环境下往往需要同时调度多DAG。多个DAG共享一组分布式资源，由于不同DAG间的竞争，必然存在调度时间上的公平性问题[9]。Zhao等[10]提出了DAG滞后程度（Slowdown）的定义，并提出基于Slowdown的公平性算法，有效地解决了多个DAG的公平性问题。Hei等[9]提出了一种不折中公平性且能优化并行任务调度性能的方法。田国忠等[11]提出的PDTC（based on the Probe of the Total Cost Decrease）使用吞吐量最大化算法预调度工作流，若仍有冗余时间则具备优化的条件；但其目标均为单一优化最小完成时间，没有考虑到云环境中各任务的执行费用问题。

综上，本文提出CAFS（Communication Aware Fair Scheduling）将CACO应用于云环境下的考虑通信开销的多DAG调度以优化执行费用，使用公平性算法调度多个DAG以提高公平性，提出后向求异（Backward Difference， BD）原则用于优化CACO在公平性算法下的时间性能。实验表明，CACO运用于公平性算法比DBL、正向分层算法（Deadline Top Level， DTL）、TCDBL性能好，CAFS能够在不增加费用和不降低公平性的基础上优化工作流的完成时间。

1带通信开销的多工作流模型

带通信开销的DAG工作流模型CADAG（Communication AwareDAG）[8]假设n个用户提交的DAG（G1，G2，…，Gi，…，Gn）在云环境下的q个服务资源（M1，M2，…，Mi，…，Mq）上同时进行调度[11]。如图1所示的带通信开销的DAG模型可以表达为G=〈V，E，S〉，其中V={0，1，…，v}表示DAG中的任务；E={eij}（i、 j∈V）为有向边的集合，eij为节点i、 j的通信开销；S表示服务集，任务i的一个候选服务集合表示为S（i）={Sik|Sik∈S}，k∈[1，S（i）]，S（i）为服务集合的规模。Sik=〈t，c，m〉表示可以完成任务i的一个服务，Sik.t为使用此服务执行i的执行时间；Sik.c为执行费用（模型中的时间与费用均是相对的，没有具体单位）；Sik.m为此服务所在的服务资源编号。多工作流模型由多个CADAG构成。通信开销是任务之间进行数据传输所需的时间，当两个具有数据依赖的任务所选的服务位于不同的服务资源时，就会产生通信开销。i， j∈V且i∈pre（j），若任务i、 j选定服务Sip∈S（i）与Sjq∈S（j），此时两个任务间的通信开销可由式（1）确定：

Trans（i， j）=0，Sip.m=Sjq.meij，其他 （1

2CAFS调度算法

2.1CACO算法

本课题组在文献[8]中提出CADAG与一种基于CADAG的费用优化算法CACO。CACO第一步利用FC原则在考虑通信开销的基础上确定最小完工时间，FC原则是指：采用递归的方法确定每个任务的最快服务（使任务最早完成的服务）及最早完成时间，仅当此任务的所有前驱任务的最快服务都确定下来才能确定此任务的最快服务。CACO调度分为两个阶段：分层阶段和调度阶段。分层阶段按照DBL的逆向分层方法，求解每一层的时间窗口，进一步求得最小完工时间TBLmin。当给定截止期δ>TBLmin存在冗余时间时，可以进一步对其进行费用优化。CACO调度阶段采用动态规划的方法调整所有任务的最终最早开始时间和最晚结束时间，这样可以利用任务在其时间窗口内的“时间碎片”以得到截止期内的费用最优服务，任务i的最优服务Sbest-i表示若任务i选择该任务能得到当前局部最优解。CACO的时间复杂度是O（v2），v为DAG的任务数量，又知先前基于分层算法的时间复杂度也为O（v2），可得CACO没有增加时间复杂度。

2.2公平性算法

Zhao等[10]提出的fairness算法目前已被广泛接受，其定义的平均不公平度Unfairness已成为衡量多DAG调度算法公平性的重要指标。该算法的主要思想是：在每个任务调度完成后更新当前所有DAG的滞后程度并调度滞后程度最高的DAG。本文在此不作详述，仅给出相关定义。

Slowdown（a）=Mown（a）/Mmulti（a）（2

式（2）中的Slowndown定义了一组DAG中的一个DAG a的滞后程度，定义为a单独在这组资源上调度的完成时间与混合调度时完成时间的比值。一个多DAG调度算法S的时间不公平程度由如式（3）、（4）定义：

Unfairness（S）=∑a∈|A|Slowdown（a）-AvgSD（3

AvgSD=1A∑a∈ASlowdown（a）（4）

其中：A是表示多个DAG的集合，AvgSD是所有DAG的滞后程度的平均值，A是这组DAG的规模。Unfairness值越小表明该算法的公平性越好。

2.3CAFS算法

2.3.1BD原则

CAFS采用fairness算法调度多用户提交的工作流，考虑到CACO能显著优化工作流的执行费用，将CACO算法应用于fairness算法。然而CACO虽然在执行费用方面相较于DBL、DTL等有显著降低（如图2），但实验表明其时间性能不如DBL等算法（如图3）。用户所提交的DAG往往有一个截止期，执行时间的缩短不仅有助于提高各个DAG间的公平性，也能提高用户对云服务的满意度。对于一组DAG和一组给定的资源，公平性算法中单DAG的调度算法影响Mown（a）的值，因此有必要进一步优化完成时间。

提出后向求异（BD）原则，以提高执行任务时的并行度，进而改善时间性能。其机制为在CAFS调度过程中考虑通信开销，从当前要调度的任务i开始向后遍历直到一个任务j， j与i至j间的某个任务来自相同的DAG（即前后存在依赖关系）或选择的最优服务Sbest相同，则i至j间的任务（不包括j）均可同时调度，下一次调度从j开始，一次调度多个任务。

2.3.2 CAFS调度策略

CAFS算法分为两个阶段。预调度阶段将CACO算法运用于fairness算法，在调度过程中根据当前调度结果更新所有DAG的当前Slowdown值以决定下一个要调度的DAG。预调度的目的是公平地决定各个DAG任务之间的调度顺序，并采用CACO算法解决带有通信开销的费用优化问题。在CAFS调度阶段利用预调度阶段求得的任务调度顺序依次调度并利用BD原则优化完成时间。下面是完整的CAFS算法的伪码。

算法1预调度阶段。

程序前

输入：每个DAG的任务数量以及截止期；

输出：存储任务调度顺序的容器Sequence。

1

将所有DAG加入未调度完成集合U，并将所有任务标记为未调度；

2）

分别用CACO算法调度每个DAG，并将完成时间结果存在Result中；

3）选择U中MakeSpan最大的DAG；

4）执行上述DAG的第一个任务，并将该任务顺序写入容器Sequence中用于算法2的调度；在其执行完后更新所有DAG的当前滞后程度Slowdown；

5）将表示混合调度结果的集合S置空。表示当前时间的变量Now置为0；

6）While（！U.Empty（）） do

7）从所有未调度的DAG中选择滞后程度最高的DAG执行；

8）按顺序执行一个上述DAG的任务b，将b写入容器Sequence；

9）S←b的调度结果；m←用CACO单独调度该DAG时调度完b的完成时间；

10）If （b是该DAG的最后一个任务）

11）Then 从U中删除该DAG，并将其置为已调度；

12）Else 根据计算公式更新所有DAG的Slowdown，并对U中DAG按Slowdown升序排列；

13）End if

14）End While

15）Return S

程序后

算法2CAFS调度。

程序前

1

currentNode=0；currentTime=0；

2）

While（true） do

3）

按照BD原则从当前调度的任务向后遍历，寻找可以同时调度的一组任务；

4）

将该组任务同时调度并修改currentTime+=该组DAG执行时间的最大者，修改各自的完成时间为currentTime+自身的执行时间；

5）

If （currentNode>=总的任务数-1） break；

6）

End While

程序后

2.4时间复杂度分析

假设有n个DAG，每个DAG有v个任务，每个任务的服务规模为m。首先进行预调度，遍历每一个DAG的每一个任务并运用CACO调度每一个DAG，此阶段的时间复杂度为O（nv2m）；在CAFS调度阶段遍历了所有任务，此阶段的时间复杂度为O（nv）。由于任务的服务规模m往往远小于其任务数v，可近似认为算法的时间复杂度为O（nv2）。可以得出，CAFS利用CACO调度n个DAG而没有增加额外的时间复杂度。

3实验方法

在Eclipse环境下用Java语言设计并实现了一个工作流仿真器作为实验平台。该仿真器目前实现了CACO、DBL、DTL、TCDBL等调度算法，能够根据由外部文件给定的参数生成有向无环图，并在界面上显示应用某种调度算法调度的结果。本文在此仿真器的基础上，对CAFS的时间性能、执行费用优化结果及公平性进行了评估，时间性能采用每个DAG的完成时间进行评价。

3.1实验设计

DAG采用随机方式生成，可以调整每个DAG的任务数量，其他诸如各任务之间边的生成、边上的权值、每个任务的服务池规模均在给定参数范围内随机生成。DAG的节点数量对算法各方面性能影响较大，因此在本实验中，设定工作流的规模V∈[20，40，60，80]以探究不同工作流规模下算法的各方面性能；每个任务的服务池规模S（i）设置为3～8的随机数；任务的执行时间设置为1～30的随机数。实验在3个随机生成的DAG上进行，实验结果取100次重复执行的平均值，其中每次生成的DAG除任务数量外其余参数均不同以保证实验的随机性。

3.2CACO费用优化结果

本实验首先引用文献[8]中CACO对于单DAG的费用优化评估结果，再给出CACO与DBL、DTL、TCDBL时间性能上的对比。图2给出了CACO与其他算法在不同工作流规模下的费用优化效果的对比。可以看出，随着DAG规模的增长，由各个算法计算而得的执行费用都有所增加，但CACO总保持在最低水平；TCDBL优于其余两种算法，因为它在选择服务时依据宽松的时间约束规则从而减少了“时间碎片”，而CACO也在调度中做到了这一点。DBL与DTL没有考虑到各分层之间任务数量的差异而将冗余时间平均分配，但显然为任务数较多的层提供更多的冗余时间有利于进一步优化费用。对比可得，CACO相较于DBL、DTL、TCDBL的费用优化效果有明显改进。

由图3可得，在不同工作流规模下CACO的平均执行时间最长，这是由于在CACO调度阶段充分利用了冗余时间以选择最优服务；DBL与DTL采用严格的时间约束策略，若某个服务时间略有超出给定的截止期但费用能有较大优化时，无法选择此服务而进一步优化执行费用，这是DBL、DTL执行时间少于CACO、TCDBL的原因。

3.3BD原则对算法性能优化效果的验证与评估

为了评估BD原则结合CACO在多DAG调度上时间性能的优化程度，本文在仿真器环境下对比了采用BD原则的CAFS与单纯地将CACO运用于fairness算法。图4比较了两者在不同工作流规模下的平均时间性能。显然，BD原则的运用优化了时间性能。这种优化是由于BD原则增加了任务间的并行度，在不降低费用性能的基础上进一步降低了工作流的完成时间。BD原则的运用，时间性能平均改进了19.82%。

如前所述，CACO相较于DBL、DTL、TCDBL在带通信开销的云环境下费用优化效果更好，而DBL等其他算法并没有考虑到云环境中各个任务间可能存在的通信开销，因而BD原则并不适用。基于此，有必要比较DBL、DTL、TCDBL基于fairness算法与CAFS的时间性能与费用性能。由图5可以看出，经过BD原则优化后的CAFS的平均时间性能虽然不是四者中最优的，但对比图4可知其时间性能有较大改进；图6分别比较了将CAFS、DBL、DTL、TCDBL运用于多工作流中的平均执行费用。由于CACO在单工作流调度中执行费用方面的优越表现，基于CACO的CAFS的执行费用也明显优于其余三者。

3.4公平性评估

调度算法的公平性对于用户来说是不可忽视的重要指标，不公平的调度算法甚至可能导致用户提交的工作流“饿死”。Honig等[12]提出加入虚入节点与虚出节点将多个DAG合并为一个DAG，进而运用单DAG算法进行调度的工作流合成算法（Composition算法）。这种方法在资源利用率和吞吐量方面有所改进，但未能考虑到多个DAG之间的公平问题。本文比较了DAG合并算法与CAFS在不同工作流规模下的公平性，同时考虑不加入BD原则的算法作为对比来说明CAFS的公平性。由图7可得，最初的DAG合并算法的公平性较差，而加入了BD原则的CAFS相较于原始的fairness算法公平性略有降低，但其公平性依然较好，说明BD原则基本不会影响调度算法的公平性，这与本文的初衷一致。CAFS调度算法的Unfairness值在当前实验环境下始终低于0.1，说明CAFS具有良好的公平性，适用于云环境下调度多DAG。

从本章的实验结果分析来看，本文提出的CAFS算法对多个带有通信开销的DAG的优化，不但能够使得每个DAG的执行费用得到优化，而且在不降低多个DAG之间公平性的基础上进一步地降低了每个DAG的完成时间。

4结语

本文通过分析多DAG调度的研究现状，在文献[8]的基础上设计并实现了基于fairness算法的带通信开销的多DAG混合调度策略CAFS，提出BD原则并验证了其有效性。通过在仿真器上与相关算法的模拟对比实验，证明了在考虑通信开销的前提下，CAFS能够兼顾费用与公平，同时较好地优化了时间性能，从而能够适用于真实的云环境。

参考文献：

[1]GONZALEZ L M V， RODEROMERINO L， CACERES J， et al. A break in the clouds： towards a cloud definition[J]. ACM SIGCOMM Computer Communication Review， 2009， 39（1）：50-55.

[2]YUAN Y， LI X， WANG Q，et al. Bottom level based heuristic for workflow scheduling in grids [J]. Chinese Journal of Computers， 2008， 31（2）： 283-290. （苑迎春，李小平，王茜，等. 基于逆向分层的网格工作流调度算法[J]. 计算机学报，2008，31（2）： 282-290.）