云环境下基于聚簇的科学工作流执行优化策略

摘要：基于云环境下的科学工作流，以提高处理机利用率、降低费用为目标，提出了一种基于聚簇的执行优化策略。该策略首先基于合理的任务复制和分簇，以实现关键任务的尽早调度；在此基础上，对任务簇再次进行聚集，以充分利用任务簇中任务间可能的空闲时间。实验表明，该策略能够提高任务的并行度，提前工作流的最早完成时间，并且在提高处理机的利用率和降低科学工作流的执行费用方面有显著效果。

关键词：云计算；科学工作流；任务复制；聚簇；任务调度

中图分类号： TP301.6 文献标志码：A

英文摘要

Abstract：Focusing on the higher ratio of processor utilization and lower execution cost of a scientific workflow in cloud， a policy of execution optimization based on task cluster aggregation was proposed. First， the tasks were reasonably replicated and aggregated into several clusters. Therefore， the key tasks could be scheduled as early as possible. Then， the task clusters were aggregated again to facilitate the spare time among the tasks in the task cluster. The experimental results show that the proposed policy can improve the parallelism of workflow tasks， advance the earliest finish time of the whole workflow and it has a significant effect in improving the utilization ratio of processors and lowering the cost of workflow execution.

英文关键词

Key words：cloud computing； scientific workflow； task replication； cluster aggregation； task scheduling

0 引言

科学工作流（Scientific Workflow）是近年来出现的一种新的应用泛型，可支持科学研究人员集成、构造和协同分布异构的数据、服务和软件工具，提高科学实验过程的自动化程度。随着科学技术的发展，科学工作流逐渐变成数据密集型和计算密集型[1]，例如：生物信息领域广泛使用的下一代DNA测序技术，每轮测序便可以产生600Gb的基因数据，一次蛋白质仿真实验的计算时间就达到几CPU年[2]（1CPU年是1GFLOP处理器不停歇地工作一年的计算量的总和。1GFLOP处理器一秒十亿次浮点运算）。可见，常规的计算环境已经很难满足科学工作流的需要，云计算环境因其理论上可提供无穷的计算和存储能力以及经济、可伸缩和Payasyougo的支付方式等特点[3]，成为了科学工作流计算环境的理想选择。

虽然理论上云环境可以提供无穷的计算能力，用户可以按需使用其计算资源，但是计算资源的提供方案的变化可能涉及到实例的创建和分配以及数据移动，需要付出一定的代价，并可能影响科学工作流的执行效率和费用[4]。因此，生成一个合理的初始执行计划是非常重要的[5]。实现工作流任务到计算资源的合理映射是工作流执行的基础，也与工作流的执行效率和执行代价密切相关，该过程被称为工作流的执行计划生成。

生成工作流执行计划的关键是把任务调度到合适的资源[6]上，包括资源的数量及类型。科学工作流任务调度算法已经有很多，目前基于启发式的调度算法得到了广泛应用，主要包括基于任务复制的调度、基于优先级列表的调度和基于簇的调度。异态最早结束时间（Heterogeneous Earliest Finish Time，HEFT）算法和可靠性动态水平调度（Hierarchical ReliabilityDriven Scheduling，HRDS）算法[7]属于基于优先级列表的调度。HEFT调度算法是根据平均计算量和平均通信量计算任务的RRank值，排列任务的RRank值得到任务调度队列；HRDS算法是对HEFT算法的改进，考虑了处理器和网络链路都有一定的故障率而加入了可靠性因素。HEFT算法和HRDS算法执行性能较高，但是目标单纯以最早完成时间为调度依据，没有考虑任务调度中资源的空闲时间的有效利用及类型的差异。

一般来说，基于任务复制的调度要优于基于优先级列表调度和基于簇的调度[8]，因为基于任务复制的调度可以消除任务间的通信开销保留任务最初的并行性，从而减少总的执行时间。

已有的任务复制算法主要有：多处理器任务调度（Task Duplication based Scheduling，TDS）算法[9]将有向无环图（Directed Acyclic Graph，DAG）中的join节点与其友好前驱节点分配到同一处理机上来降低执行时间，但是没有考虑处理机个数优化问题；基于任务复制的最优调度（Optimal task duplication based Scheduling Algorithm，OSA）算法[10]将尽量多的父节点与子节点分配到同一个处理机上，使得当前任务能获得最小的最早开始时间，但是着眼于局部没有从全局出发，制约了整个工作流的调度长度优化；基于关键路径和任务复制的单任务调度（Critical Path and Task Duplicationbased single scheduling，CPTD）算法[11]把任务图转化为相应的产品加工树，查找关键路径，通过缩短关键路径中节点的完成时间来缩短整个工作流的完成时间，但是算法复杂；缩略语与全称首字母不对应，核实LWB（Lower Bound）算法[12]能得到最优调度且处理机的使用个数也较少，但是要满足后继节点的最小计算时间大于最大通信时间，约束条件过于苛刻；基于任务复制的聚集调度（Task Duplicationbased Clustering Scheduling，TDCS）算法[13]是针对最早完成时间的算法，目标是最小化科学工作流的执行时间，该算法简单、时间复杂度更小并且约束条件宽松，实用性强，但是该算法没有考虑处理机的使用数目、空闲时间的利用，也没有涉及处理机类型、执行费用。

因此，本文基于TDCS算法在满足科学工作流执行时间的基础上，为了提高处理机资源的利用率，充分挖掘处理机的空闲时间，从而减少所需处理机数目降低执行费用，提出了一种云环境下基于聚簇的科学工作流执行优化（Execution Optimization of Scientific Workflow based on Cluster Aggregation，EOSWCA）策略。该策略是在任务层对工作流的执行进行优化，文献[14]是在服务层对工作流的执行进行优化，提出了云服务副本放置策略。

本文的主要工作包括：1）确定对哪些任务进行复制可以使工作流的完成时间最早；2）在不增加完成时间的前提下对生成的任务队列进行聚簇，可减少任务簇的个数进而减少处理机的使用个数；3）为任务簇选择合适的资源进行调度；4）对本文算法EOSWCA与TDCS算法在处理机使用数目、利用率以及执行费用方面进行了比较。

本文的主要研究是：所提出的策略能够提高任务的并行度，缩短科学工作流完成时间的同时，可充分利用处理机的闲置时间，并最终提高处理机的利用率，降低工作流的执行费用。

1 科学工作流执行计划的生成

EOSWCA算法的一个目的是尽量提早工作流的最早完成时间，而整个工作流的最早完成时间依赖于结束任务的最早完成时间，根据任务间的约束关系可知，只有父任务执行完成后子任务才能执行，所以结束任务的最早开始时间依赖于父任务的最早完成时间。类似地，父任务的最早开始时间依赖于其父任务的最早完成时间。以此类推，只有每一个任务都最早完成整个工作流才能最早完成。要想尽早完成任务就要尽量减少等待时间尽早开始执行任务，所以要计算每一个任务的最早开始时间。

1.1 相关定义

1.2 任务集分簇

科学工作流的执行通常跨多个集群，这里假设不同集群间的通信速率相同，同一个集群的任务间的通信时间往往很小，文中忽略不计。

子任务的最早开始时间取决于父任务的最早完成时间和它们之间的通信时间，为了提前子任务的最早开始时间，要消除与父任务之间的通信时间。为此，要把子任务和其父任务放在一起，即划分到一个任务簇。同一个簇中的任务调度到同一个集群中执行时，同一个簇中的任务间的通信时间就可以被消除。

对于只有一个父任务的情况，直接把子任务加入即可；对于是关键节点的任务，要让到达关键节点最晚的前驱任务产生的数据尽早到达，为此把关键节点加入到其数据最晚到达的前驱所在的簇，这样关键节点的开始时间得以提前，从而使最早完成时间提前。

分簇的过程中会出现一个任务有多个后继的情况，即outdegreei≥2，其多个后继的最早开始时间可能都是它的最早完成时间，为了保证其后继能在最早开始时间开始执行，就要对部分主任务进行复制，如图1中的t1、t5、t7。复制的规则如下：

1）若其后继的前驱只有主任务一个，则复制主任务。

2）若其后继的前驱有多个，即这一任务是关键任务，有两种情况：①主任务是关键任务的数据最晚到达的前驱，则复制主任务；②主任务不是关键任务的数据最晚到达的前驱，则不复制主任务。

任务集分簇结束后，一般情况下，为了保证任务并行性则有几个簇就要占用几个处理机来执行任务。对于图1则要6个处理机，数目较多。为了减少处理机的使用个数、提高处理机空闲时间的利用率、降低费用，本文并不立即把任务簇调度到处理机上执行而是对任务簇进行处理。下面是对科学工作流初生成的执行计划的优化。

2 科学工作流执行计划的优化

定义4 聚簇是对分簇得到的任务簇进行合理的合并，以充分利用任务簇中的空闲时间来减少任务簇的个数，进而减少处理机的使用个数。

EOSWCA算法的另一个目的是在不改变工作流最早完成时间的前提下，尽量减少处理机的使用个数。上面分簇后的结果可以直接映射到处理机上执行，为了满足每个任务的最早完成时间，要为每个簇分配一个处理机，但是这样占用的处理机资源较多，造成资源的浪费。分簇结束时就可以得到工作流的最早完成时间，在不改变工作流最早完成时间的前提下对任务簇作聚簇处理。

也就是说在保证整个工作流最早完成时间不增加的前提下，可以通过改变中间某些任务的最早开始时间，进行聚簇处理来减少处理机的使用个数，只要保证任务节点在其后继节点开始之前完成即可。

对于任务簇C（i），查找在C（j）（i>j）中没有出现过的任务和C（j）的空闲时间，在空闲时间段中为没有出现过的任务查找合适的时间段，时间段应满足两个条件：1）时间段的大小要大于或等于任务的计算时间；2）时间段的结束时间要在任务的后继节点开始之前。若C（i）中所有未出现过的任务都能在C（j）的多个空闲时间段中找到满足1）～2）的时间段，则C（i）与C（j）聚簇。

2.1 聚簇算法

在分簇的过程中，已经计算出了每个任务的参数及整个工作流的最早完成时间makespan，根据参数进行聚簇处理。以含有结束任务的簇开始向前聚簇：

1）记录C（i）的空闲时间段（i=0，1，…，n，n是簇的个数）；

2）在 C（i+1）中查找没有出现过的任务；

3）查看未出现过的任务的计算时间和后继的最早开始时间，在C（j）（j=0，1，…，i）的空闲时间段里查找满足空闲时间大于或等于是否要加上或等于加上或等于计算时间并且结束时间在最早开始时间之前的空闲时间段，若有就聚簇，把任务加入C（j）簇，否则不聚簇；

4）聚簇后，修改C（j）的空闲时间段，i=i+1，转到步骤2），i>n-1结束；

5）不能聚簇的任务簇，i=i+1，转到步骤1）， i>n-1结束。

根据聚簇算法对图1分簇结果进行聚簇，C（0）空闲时间段17～20，C（1）中没出现过的任务t9，c9=2，后继est（t11）=20，则聚簇，即C（0）={ t1，t5，t7，t10，t9，t11}，C（0）的空闲时间段修改为19～20；转到步骤2），C（2）中没有出现过的任务t8，c8=2，后继est（t10）=13，则不能聚簇，根据步骤5）转到步骤1）；直到结束。图1的聚簇结果为：{ t1，t5，t7，t10，t9，t11}、{ t1，t5，t8}、{ t1，t4，t3，t6}、{ t1，t2}，与是否1.2节？还是第1章？是1.2小节1.2节的分簇结果对比，发现少了两个任务簇而整个工作流的最早完成时间不会被改变。

2.2 任务簇分配策略

经过聚簇后进行任务调度，要根据科学工作流的类型和用户的要求选择处理机的类型，因为处理机的类型不同，性能和价格也不同。虽然减少处理机的使用个数、提高利用率可以降低执行费用，但是根据需求选择合适的处理机也很重要。

任务簇分配过程如下：

1）根据科学工作流的类型和用户的需求选定处理机类型，初始化count=0。

2）统计处理机空闲时间段，也就是查看处理机空闲时间的开始时间和结束时间，并计算出时间段的大小，设置flag=0，放入队列。

3）从队列中为任务簇查找合适的处理机空闲时间段，如果有且flag=0，则count=count+1；然后修改flag=1。

4）如果没有合适的空闲时间段则把任务簇划分成小的任务簇，执行步骤3）。

5）修改处理机的空闲时间段，重复执行步骤3）～4）直到所有的任务簇分配完毕。

6）结束时，输出占用的处理机个数count值和flag=1的处理机的空闲时间段。

聚簇算法的主要目的是减少处理机的使用个数，同时提高处理机空闲时间的利用率，而任务调度的主要目的是利用处理机的空闲时间进而提高处理机的利用率。图1的科学工作流任务簇最终调度到4个处理机上执行，与TDCS算法相比，处理机的使用个数减少了2个。

3 实验与分析

为了验证本文提出的云环境下基于聚簇的科学工作流执行优化策略的有效性，使用当前主流的开源云计算仿真平台CloudSim进行仿真实验，对CloudSim平台进行了扩展，利用Ant工具通过对CloudSim仿真平台源代码中的DataCenterBroker类、Cloudlet类和VirtualMachine类等分别进行重写，实现了本文算法EOSWCA、TDCS算法和TDS算法，然后对CloudSim重新编译新生成的平台，在新的平台上进行仿真实验。本文采用的编程工具是Myeclipse 8.0。

本文从不同的方面对三种算法进行了比较，从工作流的执行时间方面对EOSWCA算法和TDS算法进行了比较，从处理机的使用个数及利用率方面对EOSWCA算法、TDCS算法和TDS算法进行了比较。工作流的执行时间用调度长度makespan来度量。为了更好地体现算法的比较结果本文选用的任务数分别为 10，20，30，40，50，60，70，80，90，100的10种类型的工作流，每种类型的工作流随机产生10个，计算它们的平均调度长度makespan、处理机个数、处理机利用率。任务的计算时间ci和通信时间mij是在[1，20]内随机产生的。

由图2可以看出，在工作流任务数小于50时，EOSWCA算法与TDS算法的调度长度相差不大，但随着任务数的增加，EOSWCA算法的优势越来越明显。从图中曲线的走势也可以观察出，随着任务数的增加EOSWCA算法的makespan增长缓慢，可知EOSWCA算法适用于多任务的工作流。

图3中，很明显EOSWCA算法的处理机使用个数要少于TDS算法，并且随着任务数的增加这种优势越来越突出；虽然EOSWCA算法相对于TDCS算法的优势没有相对于TDS算法的明显，但是仍然绝对地优于TDCS算法。整体来说，随着任务数的增加，TDS算法处理机使用个数增加较快尤其是任务数多于70以后，任务数每增加10个所需处理机的个数增幅很大，而后两种算法没有太大的起伏。

在任务数相同的情况下，使用处理机个数越少意味着处理机的利用率越高，如图4所示。图4是以EOSWCA算法的处理机空闲时间为分子，分别计算EOSWCA算法处理机空闲时间与TDCS算法、TDS算法的处理机空闲时间的比值得到的。由图可以看出TDCS算法与EOSWCA算法的比值在0.8左右，并且随着任务数的增加呈下降趋势；TDS算法与EOSWCA算法的比值总体来看在0.8以下，虽然有起伏但是整体呈下降趋势。

结合图2～4可知：TDCS算法不但调度长度小于TDS算法，而且处理机的使用个数和利用率上也优于TDS算法；由于EOSWCA算法和TDCS算法的调度长度相差不大，所以只比较了处理机的个数和利用率，从哪里看出？把文中的图2修改为附件中的图2.实验结果表明在调度长度基本一致的情况下，本文算法在处理机的个数和利用率上都绝对地优于TDCS算法，并且随着工作流任务数的增加本文算法的优势越明显。

科学工作流执行费用与处理机的个数和类型有关，若用户没有特殊要求，则根据科学工作流的类型选择不同类型的处理机；反之则要考虑用户的需求选择合适的处理机类型。无论在什么情况下，使用的处理机个数越少意味着执行费用越低，所以本文采用聚簇的方法，在不增加执行时间的前提下尽量减少任务簇的个数从而减少占用处理机的个数，达到降低执行费用的目的。

处理机利用率相对值应说明本文算法的优势，为何只对比TDCS和TDS，无EOSWCA？文中已说明图4为EOSWCA处理机空闲时间分别与TDCS、TDS的比值，EOSWCA看作单位1，所以没有EOSWCA。

4 结语

针对科学工作流执行过程中所涉及到的执行时间、资源利用以及执行费用问题，本文探讨了一种云环境下科学工作流的执行优化策略，该策略通过任务复制来减少任务间的通信时间，进而使科学工作流的最早完成时间最小化，在保证科学工作流最早完成时间不增加的前提下，对任务簇进一步进行聚簇，从而减少处理机的使用个数。实验结果表明，本文提出的策略对于缩短科学工作流的完成时间、充分利用处理机的闲置时间并最终提高处理机的利用率和降低工作流的执行费用有明显的效果。下一步将针对混合并行科学工作流，探讨其在云环境中的执行优化。

参考文献：

[1]ZHAO Y， LI Y， TIAN W， et al. Scientificworkflowmanagementasaservice in the cloud [C]// Proceedings of the 2012 Second International Conference on Cloud and Green Computing. Piscataway： IEEE， 2012： 97-104.

[2]CHEN W， ALTINTAS I， WANG J， et al. Enhancing smart rerun of Kepler scientific workflows based on near optimum provenance caching in cloud [C]// Proceedings of the 2014 IEEE World Congress on Services. Piscataway： IEEE， 2014： 378-384.

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

[4]DEJUN J， PIERRE G， CHI C H. EC2 performance analysis for resource provisioning of serviceoriented applications [C]// Proceedings of ICSOC/ServiceWave 2009 Workshops ServiceOriented Computing， LNCS 6275. Berlin：Springer， 2010： 197-207.

[5]KIM H， elKHAMRA Y， RODERO I， et al. Autonomic management of application workflows on hybrid computing infrastructure[J]. Scientific ProgrammingScienceDriven Cloud Computing， 2011， 19（2/3）： 75-89.

[6]SHI X， XU K. Utility maximization model of virtual machine scheduling in cloud environment [J]. Chinese Journal of Computers， 2013， 36（2）： 252-262.（ 师雪霖，徐恪.云虚拟机资源分配的效用最大化模型[J].计算机学报，2013，36（2）：252-262.）.

[7]YAN G， YU J， YANG X. Twostep task scheduling strategy for scientific workflow on cloud computing platform [J]. Journal of Computer Applications， 2013， 33（4）： 1006-1009.（闫歌，于炯，杨兴耀.云计算环境下科学工作流两阶段任务调度策略[J]. 计算机应用，2013，33（4）：1006-1009.）

[8]BAJAJ R， AGRAWAL D P. Improving scheduling of tasks in a heterogeneous environment [J]. IEEE Transactions on Parallel and Distributed Systems， 2004， 15（2）： 107-118.

[9]DARBHA S， AGRAWAL D P. Optimal scheduling algorithm for distributedmemory machines[J]. IEEE Transactions on Parallel and Distributed Systems， 1998， 9（1）： 87-95.

[10]PARK CI， CHOE TY. An optimal scheduling algorithm based on task duplication [C]// ICPADS 2001： Proceedings of the Eighth International Conference on Parallel and Distributed Systems. Piscataway： IEEE， 2001： 9-14.

[11]XIE Z， HAN Y， QI Y， et al. A scheduling algorithm for multicore based on critical path and task duplication [J]. Journal of National University of Defense Technology， 2014， 36（1）： 172-177. （谢志强，韩英杰，齐永红，等.基于关键路径和任务复制的多核调度算法[J].国防科技大学学报，2014，36（1）：172-177.）

[12]COLIN J Y， CHRETIENNE P. C.P.M.C.P.M.为文章题目中一部分 scheduling with small communication delays and task duplication [J]. Operations Research， 1991， 39（4）： 680-684.

[13]ZHANG J， LI Q， QU Y. Task duplication based scheduling algorithm [J]. Computer Engineering and Design， 2009， 30（8）： 1896-1899.（张建军，李庆华，瞿勇.基于任务复制的调度算法[J].计算机工程与设计，2009，30（8）：1896-1899.）

[14]LUO H， CHEN W. Replica allocation policy of cloudy services based on social network properties [J]. Journal of Computer Applications， 2013， 33（8）： 2143-2146.（罗浩宇，陈旺虎.基于社会网络特征的云服务副本放置策略[J].计算机应用，2013，33（8）：2143-2146.）