第1页共23页云环境下基于聚簇的科学工作流执行优化策略摘要：基于云环境下的科学工作流，以提高处理机利用率、降低费用为目标，提出了一种基于聚簇的执行优化策略。该策略首先基于合理的任务复制和分簇，以实现关键任务的尽早调度；在此基础上，对任务簇再次进行聚集，以充分利用任务簇中任务间可能的空闲时间。实验表明，该策略能够提高任务的并行度，提前工作流的最早完成时间，并且在提高处理机的利用率和降低科学工作流的执行费用方面有显著效果。关键词：云计算；科学工作流；任务复制；聚簇；任务调度：TP301.6文献标志码：A英文摘要Abstract：Focusingonthehigherratioofprocessorutilizationandlowerexecutioncostofascientific第2页共23页workflowincloud，apolicyofexecutionoptimizationbasedontaskclusteraggregationwasproposed.First，thetaskswerereasonablyreplicatedandaggregatedintoseveralclusters.Therefore，thekeytaskscouldbescheduledasearlyaspossible.Then，thetaskclusterswereaggregatedagaintofacilitatethesparetimeamongthetasksinthetaskcluster.Theexperimentalresultsshowthattheproposedpolicycanimprovetheparallelismofworkflowtasks，advancetheearliestfinishtimeofthewholeworkflowandithasasignificanteffectinimprovingtheutilizationratioofprocessorsandloweringthecostofworkflowexecution.英文关键词Keywords：cloudcomputing；scientificworkflow；taskreplication；clusteraggregation；taskscheduling第3页共23页0引言科学工作流（ScientificWorkflow）是近年来出现的一种新的应用泛型，可支持科学研究人员集成、构造和协同分布异构的数据、服务和软件工具，提高科学实验过程的自动化程度。随着科学技术的发展，科学工作流逐渐变成数据密集型和计算密集型[1]，例如：生物信息领域广泛使用的下一代DNA测序技术，每轮测序便可以产生600Gb的基因数据，一次蛋白质仿真实验的计算时间就达到几CPU年[2]（1CPU年是1GFLOP处理器不停歇地工作一年的计算量的总和。1GFLOP处理器一秒十亿次浮点运算）。可见，常规的计算环境已经很难满足科学工作流的需要，云计算环境因其理论上可提供无穷的计算和存储能力以及经济、可伸缩和Payasyougo的支付方式等特点[3]，成为了科学工作流计算环境的理想选择。虽然理论上云环境可以提供无穷的计算能力，用户可以按需使用其计算资源，但是计算资源的提供方案的变化可能涉及到实例的创建和分配以及数据移动，需要付出一定的代价，并可能影响科学第4页共23页工作流的执行效率和费用[4]。因此，生成一个合理的初始执行计划是非常重要的[5]。实现工作流任务到计算资源的合理映射是工作流执行的基础，也与工作流的执行效率和执行代价密切相关，该过程被称为工作流的执行计划生成。生成工作流执行计划的关键是把任务调度到合适的资源[6]上，包括资源的数量及类型。科学工作流任务调度算法已经有很多，目前基于启发式的调度算法得到了广泛应用，主要包括基于任务复制的调度、基于优先级列表的调度和基于簇的调度。异态最早结束时间（HeterogeneousEarliestFinishTime，HEFT）算法和可靠性动态水平调度（HierarchicalReliabilityDrivenScheduling，HRDS）算法[7]属于基于优先级列表的调度。HEFT调度算法是根据平均计算量和平均通信量计算任务的RRank值，排列任务的RRank值得到任务调度队列；HRDS算法是对HEFT算法的改进，考虑了处理器和网络链路都有一定的故障率而加入了可靠性因素。HEFT算法和HRDS算法执行性能较高，但是目标单纯以最早完成时间第5页共23页为调度依据，没有考虑任务调度中资源的空闲时间的有效利用及类型的差异。一般来说，基于任务复制的调度要优于基于优先级列表调度和基于簇的调度[8]，因为基于任务复制的调度可以消除任务间的通信开销保留任务最初的并行性，从而减少总的执行时间。已有的任务复制算法主要有：多处理器任务调度（TaskDuplicationbasedScheduling，TDS）算法[9]将有向无环图（DirectedAcyclicGraph，DAG）中的join节点与其友好前驱节点分配到同一处理机上来降低执行时间，但...