工作流 jflow(云环境下基于聚簇的科学工作流执行优化策略)
基于云环，以提高处理器利用率和降低成本为目标的科学工作流，提出了一种基于聚类的执行优化策略。首先，该策略基于合理的任务复制和聚类，实现关键任务的早期调度。在此基础上，再次对对任务簇进行聚类，以充分利用任务簇中任务之间可能的空闲时间。这个过程称为工作流执行计划生成。
关键词：云计算；科学工作流程；复制任务；聚类；任务调度
引言科学工作流是近年来出现的一种新的应用类属，它可以支持科研人员集成、构建和协同分发异构数据、服务和软件工具，提高科学实验过程的自动化程度。随着科学技术的发展，科学工作流逐渐变得数据密集型和计算密集型[1]。例如，生物信息学领域广泛使用的下一代DNA测序技术，每轮测序可产生600Gb的基因数据，蛋白质模拟实验的计算时间可达几个CPU年[2](1CPU年是1GFLOP处理器不间断工作一年的计算量之和。1GFLOP处理器每秒10亿次浮点运算)。由此可见，传统的计算环境已经难以满足科学工作流的需求，而云计算环境由于理论上可以提供无限的计算和存储能力，并且具有经济性、可扩展性和支付方式的特点，已经成为科学工作流计算环境的理想选择。
虽然在理论上，云环可以提供无限的计算能力，并且用户可以根据自己的需要使用他们的计算资源，但是计算资源的供应方案的变化可能涉及实例的创建和分配以及数据的移动，这需要付出一定的代价，并且可能影响科学工作流的执行效率和成本[4]。因此，制定合理的初始执行计划非常重要[5]。实现工作流任务到计算资源的合理映射是工作流执行的基础，也与工作流执行的效率和成本密切相关。这个过程称为工作流执行计划生成。生成工作流执行计划的关键是将任务调度到适当的资源[6]，包括资源的数量和类型。科学工作流中有许多任务调度算法。目前，启发式调度算法得到了广泛的应用，包括基于任务复制的调度、基于优先级列表的调度和基于集群的调度。异构最早完成时间(HEFT)算法和分层可靠性驱动调度(HRDS)算法[7]属于基于优先级列表的调度。HEFT调度算法根据平均计算量和平均流量计算任务的排序值，并排列任务的排序值得到任务调度队列；HRDS算法是对对HEFT算法的改进，它考虑了处理器和网络链路的故障率，并加入了可靠性因素。HEFT算法和HRDS算法具有较高的性能，但目标只是基于最早完成时间，没有考虑任务调度中资源的有效利用率和空闲时间的类型差异。
一般来说，基于任务复制的调度优于基于优先级列表和集群的调度[8]，因为基于任务复制的调度可以消除任务之间的通信开销，并保持任务的初始并行性，从而减少总执行时间。现有的任务复制算法主要包括：基于任务复制的调度(TDS)算法[9]将有向无环图(DAG)中的连接节点分配给与其友好的前身相同的处理器，以减少执行时间，但没有考虑处理器数量的优化；基于最优任务复制的调度算法(OSA)算法[10]将尽可能多的父任务和子任务分配给同一个处理器，使得当前任务可以得到最小的最早开始时间，但是只关注局部而不是从全局开始，这限制了整个工作流的调度长度优化。基于关键路径和任务复制的单一调度算法(CPTD) [11]将任务图作为相应的产品加工树，找到关键路径，通过缩短关键路径中节点的完成时间来缩短整个工作流的完成时间，但算法复杂。缩写与全名的首字母不对应。验证了LWB(下界)算法[12]可以得到最优调度，并且使用的处理器数量也很少，但是约束条件过于苛刻，不能满足后继节点的最小计算时间大于最大通信时间的要求。TDCS(基于任务重复的聚类调度)算法[13]是一种针对对，最早完成时间的算法，其目标是最小化科学工作流的执行时间。该方法简单，时间复杂度低，约束条件宽松，实用性强。但是，它没有考虑使用的处理器数量、空闲时间的使用、处理器的类型和执行成本。
因此，基于TDCS算法，为了提高处理器资源的利用率，充分利用处理器的空闲时间，减少了所需的处理器数量，降低了执行成本。本文提出了一种基于集群聚合策略的云环科学工作流执行优化方法。该策略是在任务层优化对工作流的执行，而文件[14]是在服务层优化对工作流的执行，并提出了云服务副本放置策略。本文的主要工作包括：1)确定对哪些任务可以复制，使工作流的完成时间最早；2)在不增加完成时间的情况下，对对生成的任务队列进行聚类，这可以减少任务聚类的数量，从而减少使用的处理器数量；3)为任务集群选择合适的资源进行调度；4)对从使用的处理器数量、利用率和执行成本方面比较了EOSWCA和TDCS算法。
本文的主要研究内容是提出的策略能够提高任务的并行性，缩短科学工作流的完成时间，充分利用处理器的空闲时间，最终提高处理器的利用率，降低工作流的执行成本。
黑曼巴 