摘要：基于云环境下的科学工作流，以提高处理机利用率、降低费用为目标，提出了一种基于聚簇的执行优化策略。该策略首先基于合理的任务复制和分簇，以实现关键任务的尽早调度；在此基础上，对任务簇再次进行聚集，以充分利用任务簇中任务间可能的空闲时间。实验表明，该策略能够提高任务的并行度，提前工作流的最早完成时间，并且在提高处理机的利用率和降低科学工作流的执行费用方面有显著效果。
关键词：云计算；科学工作流；任务复制；聚簇；任务调度
中图分类号： 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 引言
虽然理论上云环境可以提供无穷的计算能力，用户可以按需使用其计算资源，但是计算资源的提供方案的变化可能涉及到实例的创建和分配以及数据移动，需要付出一定的代价，并可能影响科学工作流的执行效率和费用[4]。因此，生成一个合理的初始执行计划是非常重要的[5]。实现工作流任务到计算资源的合理映射是工作流执行的基础，也与工作流的执行效率和执行代价密切相关，该过程被称为工作流的执行计划生成。
生成工作流执行计划的关键是把任务调度到合适的资源[6]上，包括资源的数量及类型。科学工作流任务调度算法已经有很多，目前基于启发式的调度算法得到了广泛应用，主要包括基于任务复制的调度、基于优先级列表的调度和基于簇的调度。异态最早结束时间（Heterogeneous Earliest Finish Time，HEFT）算法和可靠性动态水平调度（Hierarchical ReliabilityDriven Scheduling，HRDS）算法[7]属于基于优先级列表的调度。HEFT调度算法是根据平均计算量和平均通信量计算任务的RRank值，排列任务的RRank值得到任务调度队列；HRDS算法是对HEFT算法的改进，考虑了处理器和网络链路都有一定的故障率而加入了可靠性因素。HEFT算法和HRDS算法执行性能较高，但是目标单纯以最早完成时间为调度依据，没有考虑任务调度中资源的空闲时间的有效利用及类型的差异。
一般来说，基于任务复制的调度要优于基于优先级列表调度和基于簇的调度[8]，因为基于任务复制的调度可以消除任务间的通信开销保留任务最初的并行性，从而减少总的执行时间。
本文的主要研究是：所提出的策略能够提高任务的并行度，缩短科学工作流完成时间的同时，可充分利用处理机的闲置时间，并最终提高处理机的利用率，降低工作流的执行费用。
1 科学工作流执行计划的生成
EOSWCA算法的一个目的是尽量提早工作流的最早完成时间，而整个工作流的最早完成时间依赖于结束任务的最早完成时间，根据任务间的约束关系可知，只有父任务执行完成后子任务才能执行，所以结束任务的最早开始时间依赖于父任务的最早完成时间。类似地，父任务的最早开始时间依赖于其父任务的最早完成时间。以此类推，只有每一个任务都最早完成整个工作流才能最早完成。要想尽早完成任务就要尽量减少等待时间尽早开始执行任务，所以要计算每一个任务的最早开始时间。
1.1 相关定义
科学工作流的执行通常跨多个集群，这里假设不同集群间的通信速率相同，同一个集群的任务间的通信时间往往很小，文中忽略不计。
子任务的最早开始时间取决于父任务的最早完成时间和它们之间的通信时间，为了提前子任务的最早开始时间，要消除与父任务之间的通信时间。为此，要把子任务和其父任务放在一起，即划分到一个任务簇。同一个簇中的任务调度到同一个集群中执行时，同一个簇中的任务间的通信时间就可以被消除。
对于只有一个父任务的情况，直接把子任务加入即可；对于是关键节点的任务，要让到达关键节点最晚的前驱任务产生的数据尽早到达，为此把关键节点加入到其数据最晚到达的前驱所在的簇，这样关键节点的开始时间得以提前，从而使最早完成时间提前。
分簇的过程中会出现一个任务有多个后继的情况，即outdegreei≥2，其多个后继的最早开始时间可能都是它的最早完成时间，为了保证其后继能在最早开始时间开始执行，就要对部分主任务进行复制，如图1中的t1、t5、t7。复制的规则如下：
1）若其后继的前驱只有主任务一个，则复制主任务。
2）若其后继的前驱有多个，即这一任务是关键任务，有两种情况：①主任务是关键任务的数据最晚到达的前驱，则复制主任务；②主任务不是关键任务的数据最晚到达的前驱，则不复制主任务。
任务集分簇结束后，一般情况下，为了保证任务并行性则有几个簇就要占用几个处理机来执行任务。对于图1则要6个处理机，数目较多。为了减少处理机的使用个数、提高处理机空闲时间的利用率、降低费用，本文并不立即把任务簇调度到处理机上执行而是对任务簇进行处理。下面是对科学工作流初生成的执行计划的优化。
2 科学工作流执行计划的优化
定义4 聚簇是对分簇得到的任务簇进行合理的合并，以充分利用任务簇中的空闲时间来减少任务簇的个数，进而减少处理机的使用个数。
EOSWCA算法的另一个目的是在不改变工作流最早完成时间的前提下，尽量减少处理机的使用个数。上面分簇后的结果可以直接映射到处理机上执行，为了满足每个任务的最早完成时间，要为每个簇分配一个处理机，但是这样占用的处理机资源较多，造成资源的浪费。分簇结束时就可以得到工作流的最早完成时间，在不改变工作流最早完成时间的前提下对任务簇作聚簇处理。
也就是说在保证整个工作流最早完成时间不增加的前提下，可以通过改变中间某些任务的最早开始时间，进行聚簇处理来减少处理机的使用个数，只要保证任务节点在其后继节点开始之前完成即可。
2.1 聚簇算法
在分簇的过程中，已经计算出了每个任务的参数及整个工作流的最早完成时间makespan，根据参数进行聚簇处理。以含有结束任务的簇开始向前聚簇：
1）记录C（i）的空闲时间段（i=0，1，…，n，n是簇的个数）；
2）在 C（i+1）中查找没有出现过的任务；
3）查看未出现过的任务的计算时间和后继的最早开始时间，在C（j）（j=0，1，…，i）的空闲时间段里查找满足空闲时间大于或等于是否要加上或等于加上或等于计算时间并且结束时间在最早开始时间之前的空闲时间段，若有就聚簇，把任务加入C（j）簇，否则不聚簇；
5）不能聚簇的任务簇，i=i+1，转到步骤1）， i>n-1结束。
经过聚簇后进行任务调度，要根据科学工作流的类型和用户的要求选择处理机的类型，因为处理机的类型不同，性能和价格也不同。虽然减少处理机的使用个数、提高利用率可以降低执行费用，但是根据需求选择合适的处理机也很重要。
任务簇分配过程如下：
1）根据科学工作流的类型和用户的需求选定处理机类型，初始化count=0。
2）统计处理机空闲时间段，也就是查看处理机空闲时间的开始时间和结束时间，并计算出时间段的大小，设置flag=0，放入队列。
3）从队列中为任务簇查找合适的处理机空闲时间段，如果有且flag=0，则count=count+1；然后修改flag=1。
4）如果没有合适的空闲时间段则把任务簇划分成小的任务簇，执行步骤3）。
5）修改处理机的空闲时间段，重复执行步骤3）～4）直到所有的任务簇分配完毕。
6）结束时，输出占用的处理机个数count值和flag=1的处理机的空闲时间段。
3 实验与分析
为了验证本文提出的云环境下基于聚簇的科学工作流执行优化策略的有效性，使用当前主流的开源云计算仿真平台CloudSim进行仿真实验，对CloudSim平台进行了扩展，利用Ant工具通过对CloudSim仿真平台源代码中的DataCenterBroker类、Cloudlet类和VirtualMachine类等分别进行重写，实现了本文算法EOSWCA、TDCS算法和TDS算法，然后对CloudSim重新编译发布新生成的平台，在新的平台上进行仿真实验。本文采用的编程工具是Myeclipse 8.0。
由图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 结语
针对科学工作流执行过程中所涉及到的执行时间、资源利用以及执行费用问题，本文探讨了一种云环境下科学工作流的执行优化策略，该策略通过任务复制来减少任务间的通信时间，进而使科学工作流的最早完成时间最小化，在保证科学工作流最早完成时间不增加的前提下，对任务簇进一步进行聚簇，从而减少处理机的使用个数。实验结果表明，本文提出的策略对于缩短科学工作流的完成时间、充分利用处理机的闲置时间并最终提高处理机的利用率和降低工作流的执行费用有明显的效果。下一步将针对混合并行科学工作流，探讨其在云环境中的执行优化。
参考文献：
[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.
[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.
[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.