基于图割的云环境中工作流调度改进算法

邓碧林，王云岚

(西北工业大学计算机学院，陕西 西安 710072)

0 引言

随着人们对计算能力需求的不断提升，在继分布式计算、网格计算后，云计算模型首先由商业界提出。云计算使用虚拟化技术将大规模的计算和存储资源虚拟成一个资源池。用户可以在需要的时候通过服务的方式获取这些资源，并为所使用的资源支付费用。

相对于传统的计算模型，云计算有以下两点优势:(1)使用云计算的成本低。通过使用云计算，用户避开了高昂的数据中心建设和维护费用，并且由于云计算按需获取资源的方式，用户不用担心因为业务量的增长或者数据量的增长带来的升级费用。(2)使用方便快捷。在云计算环境中，用户的程序、数据的管理都由云端来完成。数据中心的负载均衡、安全等因素由提供云计算服务企业的IT人员负责。用户只需要有较快的互联网接入就可以通过PC方便快捷地处理数据和享受服务。

云计算的兴起也给科学计算提供了一种与传统的高性能科学计算不同的计算平台。在科学计算领域，复杂的计算过程通常使用工作流来组织。这些工作流通常涉及大量的数据和计算，被部署在超级计算机、分布式集群系统或者网格系统。然而，构造和维护这样的系统需要大量的资金。云计算出现后，研究人员对科学工作流部署在云端进行了研究，肯定了在云端部署科学工作流的可行性［1］。

虽然云计算的出现解决了科学工作流执行所需的计算资源问题，但同时也引入了一些新问题。云计算平台通常由地理上分布的数据中心组成，或者由几个组织的私有云通过互联网连接成一个更大的云计算平台。工作流引擎在执行工作流的时候通常需要将数据分配到不同的数据中心或者私有云中。同时，工作流中不同阶段的任务之间也需要交换数据。不合理的任务调度方法不仅会增加各数据中心间的通信量，而且会导致各数据中心的负载不平衡，从而影响整个云平台的资源利用率，降低工作流的执行效率，增加用户开销。

本文提出了一种基于图割的科学工作流调度策略MCGRP(Multi Constraint Graph Ratio Partitioning)，其过程如下:科学工作流管理系统在运行时会维护一张云平台数据中心的拓扑图，图中的顶点表示某个数据中心在某一时刻的空闲slot数目，图中的边表示各数据中心的通信能力;当调度新的工作流时，工作流的调度器首先对工作流的DAG使用MCGRP算法进行分割，然后根据分割结果将DAG中的任务调度到对应的数据中心。

1 相关研究

虽然云平台中的调度算法已有了大量研究，但仍然存在不少问题。文献［2］提出了一种基于图割的调度算法，该算法充分考虑了减少各个数据中心间数据的传输量，却并没有考虑各个数据中心的计算能力和负载情况。在实际情况中，即使各个数据中心的计算能力是相同的，由于工作流中任务的不同，系统运行一段时间后，各个数据中心的负载情况也有可能出现较大的差别。文献［3-4］将MCGP(Multi-Constraint Graph Partitioning)算法应用到了科学工作流的调度中。与普通的图割算法只给图中顶点赋一个权值不同，MCGP算法中图的顶点的权值使用向量表示，分割后的结果不仅可以使被切割的边的权值和较小，同时各个子图中顶点的权值向量中各分量和尽量相似(equi-partition)。实验结果表明，相对于传统的RR(Round Robin)算法，MCGP算法平均减少了31%的工作流执行时间。然而，MCGP算法中的equi-partition并不适用于由计算能力不同的数据中心组成的云平台的情况或者各个数据中心负载不平衡的情况。文献［5］提出了一种云工作流中间数据的存放策略以降低工作流的执行开销。该文中的算法首先根据中间数据的起源生成一个中间数据关系图(IDG)，IDG记录了云工作流系统中所有存在过的数据的信息。系统可以通过IDG知道中间数据的生成代价，再将生成代价和存储代价进行比较来决定是否存储该中间数据。

2 问题阐述

在调度问题中，工作流一般使用有向非循环图DAG=(V，E)表示。图中的顶点 V=(v1，v2，…，vn)表示工作流中的任务。图中的边E=(e1，e2，…，em)表示各个任务间的关系，图中的某一条边Eij表示vi是vj的父任务。每个子任务可以开始执行当且仅当它所有的父任务已经执行完毕。每个顶点都有一个相应的权值来表示任务的属性(如执行任务所需的计算量或者任务所需的存储量)。

运行工作流的云平台也可以使用图G表示，图中的顶点表示构成云平台的数据中心。图中的边表示各个数据中心间的通信开销。图中的每个顶点也都有一个权值，表示当前该数据中心的空闲计算资源。工作流运行时，假设同一个数据中心中任务间的通信开销为零，工作流管理系统需要不断对图G进行更新以反映当前各数据中心的负载情况。

根据以上假设，云环境中工作流的调度问题可以简化为图割(Graph Cut)问题:使用图割算法对工作流的DAG图进行分割，分割到同一子图中的任务将被调度到同一数据中心执行。因此，图割的目标就是使被切割的图中边的权值和最小(对应工作流执行过程中各数据中心间的通信量最小)，并且各个子图中顶点的权值和与云平台构成的图尽量相似(对应于各数据中心都不会因为任务分配的不平衡而造成该数据中心的负载过重)。可以使用各个数据中心的slot数目和对应的子图中虚拟机的数目之差的绝对值的和SUM来表示两个图的相似度。SUM越小表示两个图的相似度越高。在下文中，将使用 M(DAG，G)来表示两个图的相似度。

3 MCGRP算法

MCGRP算法是对MCGP算法的改进。MCGP算法包含3个阶段:(1)收缩阶段;(2)初始划分阶段;(3)优化阶段。MCGRP算法主要在优化阶段对MCGP算法进行改进。下文中只简要阐述MCGRP使用的第1、第2阶段的算法，具体过程见文献［6］。

3.1 收缩阶段

在收缩阶段将由图G生成一系列子图。该阶段可以使用两种算法:RM(Random Matching)、HEM(Heavy Edge Matching)。RM算法:以随机的方式对图G中的顶点进行访问，对于访问到的某一顶点V，如果该顶点在该轮收缩中没有被访问过，则将该顶点随机地和一个与其有边相连并在该轮未被访问过的顶点收缩。HEM算法:考虑图Gi=(Vi，Ei)和对其收缩后的图Gi+1，使用W(Ei)表示图Gi中所有边的权值和;容易得出W(Ei)=W(Ei+1)+W(E)，其中W(E)表示在第i轮收缩过程中被收缩的边的权值和;由上式可知，如果在每次收缩过程中选择权值较大的边进行收缩，可以最大限度地减少收缩后图中边的权值。根据上述原理，HEM算法改进了RM算法:

步骤1 将图G中所有的节点标记为未被访问。

步骤2 随机地选择一个未被标记的节点V并标记V为已访问。

步骤3 选择与V有边相连且边的权值最大的节点与V合并。如果不能找到这样的节点，回到步骤2。

步骤4 判断图中是否还有未被访问过的节点。没有则该轮收缩结束，有则回到步骤2。

3.2 初始划分阶段

初始划分阶段将收缩后的图划分为K个部分，并使得每个部分包含的节点的权值和大致相等。可以使用2种方式得到图的初始划分:(1)在第一阶段不停地对图进行收缩，直到图中只剩下K个顶点。(2)采用贪婪算法，首先选择起始任务作为初始节点对图进行深度优先遍历;当已遍历过的节点的权值大致等于W(V)/K时停止;将已遍历过的节点从图中分割，对剩下的图重复上述操作，直至图被分割为K个部分。第一种方式有2个主要的缺点:(1)在对图进行收缩的最后阶段，整个图可能收缩得很慢;(2)由于在收缩的过程中只考虑图中的边的权值，并没有考虑顶点的权值，将整个图直接收缩为K个节点可能会导致K个节点的权值和极不平衡。在本文的算法中图的初始划分使用的是贪婪算法。

3.3 优化阶段

优化阶段是收缩阶段的逆过程。在优化阶段，经过初始划分的图将会由 Gm，Gm－1，…，G1变回 G。在由 Gi变到 Gi－1的过程中，由图 Gi－1收缩到 Gi过程中被收缩的节点被标记为可移动，如果这些节点位于被划分的子图的边界，算法就按一定的规则判断该节点是属于该子图还是与其相邻的子图。由于在收缩过程中各子节点包含图G中的节点数目逐渐增大，所以在优化阶段移动的节点包含图G中的节点数目逐渐减小，即优化的粒度由粗到细。

在优化阶段需要计算边界节点在各个子图间移动的利益函数以确定是否移动该节点。对于图Gi=(Vi，Ei)中的某一节点V，定义V的邻居N(V)为与该顶点有边相连的子图的并集。如果节点V是一个内部节点，定义N(V)为空。对于子图中的某一个边界节点V，定义它对于N(V)中某一子图的出度ED(V)为V与该子图相连的边的权值和。定义V的入度ID(V)为节点V与当前V所在的子图相连的边的权值和。例如，在图1中，节点V对子图a的出度为4，它对于子图c的入度为3。由于节点在2个子图间移动并不改变该节点对于其他子图的出度，可以定义在某一轮优化过程中节点V从子图a移动到子图b的收获为:G(V)=ED(V)-ID(V)。

图1 示例流程图

在边界节点的移动过程中，如果只单纯考虑利益函数的最小化，可能会导致划分得到的图与数据中心组成的图极不相符(使用上文提出的衡量算法)。因此，节点在移动的过程中必须符合下面2个公式。

式(1)表示在第i轮优化后，图Gi+1要比图Gi更符合数据中心的拓扑图。式(2)表示Gi+1中任意一个子图中的节点的权值和都不能超出对应的数据中心的容量。

优化阶段的具体步骤如下:在第i轮优化过程中，仍然以随机的方式访问图中的节点。对于访问到的节点V，如果该节点在子图的内部，则不移动。对于子图边界上的节点V，如果节点的移动不违反式(1)和式(2)，并且节点满足下面2个条件中的任意一个，则将V移动到对应的子图。

(1)移动节点V到该子图的收获G(V)在所有子图中是最大的。

(2)M(DAGi+1，G)在所有可能的移法中是最大的。

条件(1)表明在不违反平衡性条件下，优化算法会将节点V移动到能使整个图的边割最小的子图。条件(2)表明对于某一节点V，当没有对应的子图满足条件(1)时，优化算法将选择能使移动后的图更平衡的子图将V移动过去。如果没有子图能满足条件(1)和(2)，那么该节点不移动。在移动某一节点后，优化算法更新该节点的ED(V)等数据结构。当图中所有的节点都被访问过或者不能在图中找到满足上述条件的节点时，该轮迭代结束。

在下一轮(第i+1轮)迭代中，在第i轮被收缩的节点将被标记为可自由移动，然后重复上述过程。

4 实验结果及分析

为了验证本文算法的有效性，在CPU为Intel®CoreTMi5，内存为4 GB的PC机上进行了模拟实验。

由于实际的工作流程图只能反映一部分实际问题的情况，对其优化的结果不能说明算法对所有的工作流程图都有较好的加速效果。因此，为了全方位地检测本文提出的调度算法的效果，采用了文献［2］中的试验方法，即使用模拟、可定制的工作流程图作为算法的输入。

本文的实验对比了RR、MCGP、MCGRP算法的调度效果。为了保证算法输出的准确度，对于算法的每个输入，都重复10次计算，取结果的平均值作为算法的最终输出。

数据中心的数量固定为4，工作流中的任务数增加时3种调度策略的调度效果比较如图2所示。

图2 任务数不同时3种调度算法的比较

从实验结果来看，当工作流中任务较少时，MCGRP算法对工作流执行的加速效果并不十分明显。而随着任务数目的增加，MCGRP算法的调度效果明显优于RR算法和MCGP算法的调度效果。这是因为随着任务数目的增多，由于RR算法和MCGP算法并未考虑数据中心的负载情况，造成了部分数据中心的过载，大大增加了工作流的执行时间。

5 结束语

本文首先分析了制约云环境中科学工作流的执行效率的因素，指出各个数据中心间负载的不平衡是影响工作流执行过程的一个主要因素，进而提出了调度算法MCGRP。实验结果表明，MCGRP算法相对于其他两种算法(RR，MCGP)有较明显的优势。

为了让MCGRP算法更有应用价值，将深入研究制约科学工作流执行效率的因素，并在Eucalyptus平台上实现一种科学工作流的调度平台。

［1］Hoffa C，Mehta G，Freeman T，et al.On the use of cloud computing for scientific workflows［C］//Proceedings of the 4th IEEE International Conference on eScience.2008:640-645.

［2］刘少伟，孔令梅，任开军，等.云环境下优化科学工作流执行性能的两阶段数据放置与任务调度策略［J］.计算机学报，2011，34(11):2121-2130.

［3］Tanaka M，Tatebe O.Workflow scheduling to minimize data movement using multi-constraint graph partitioning［C］//Proceedings of the 12th IEEE/ACM International Symposium on Cluster，Cloud and Grid Computing.2012:65-72.

［4］Karypis G，Kumar V.Multilevel k-way Partitioning Scheme for Irregular Graphs［R］.University of Minnesota，1995.

［5］Yuan D，Yang Y，Liu X，et al.A cost-effective strategy for intermediate data storage in scientific cloud workflow systems［C］//Proceedings of the 2010 IEEE International Symposium on Parallel＆ Distributed Processing.2010.

［6］Karypis G，Kumar V.Multilevel algorithms for multi-constraint graph partitioning［C］//Proceedings of the 1998 ACM/IEEE Conference on Supercomputing.1998:64-76.

［7］Deng K，Song J，Ren K，et al.Graph-cut based coscheduling strategy towards efficient execution of scientific workflows in collaborative cloud environments［C］//Proceedings of the 12th IEEE/ACM International Conference on Grid Computing.2011:34-41.

［8］Foster I，Zhao Y，Raicu I，et al.Cloud computing and grid computing 360-degree compared［C］//Proceedings of the 2008 IEEE Workshop on Grid Computing Environments.2008:60-69.

［9］Armbrust M，Fox A，Griffith R，et al.A view of cloud computing［J］.Communications of the ACM，2010，53(4):50-58.

［10］Ostermann S，Iosup A，Yigitbasi N，et al.A performance analysis of EC2 cloud computing services for scientific computing［M］//Cloud Computing.Springer，Berlin，Heidelberg，2010，34:115-131.

［11］Nurmi D，Wolski R，Grzegorczyk C，et al.The eucalyptus open-source cloud-computing system［C］//Proceedings of the 9th IEEE/ACM International Symposium on Cluster Computing and the Grid.2009:124-131.

［12］Youseff L，Butrico M，Da Silva D.Toward a unified ontology of cloud computing［C］//Proceedings of the 2008 IEEE Workshop on Grid Computing Environments.2008:42-51.

［13］Velte T，Velte A，Elsenpeter R.Cloud Computing:A Practical Approach［M］.McGraw-Hill，2009.

［14］Marinos A，Briscoe G.Community cloud computing［C］//Proceedings of the 1st International Conference on Cloud Computing.2009:472-484.