论文部分内容阅读
云计算是一种新兴的资源使用和交付模式,它以一种有趣的形式呈现并且推动科学的发展和商业应用。类似于水电,云计算通过按需消费向用户提供一种即时、灵活和可扩展的服务。云计算旨在允许以完全虚拟化的方法访问大量的计算能力。通过整合资源并提供一个单一的系统视图,目的在于提供一个实用的计算。云计算表示一种一个计算基础设施可以作为一个“云”的模式,企业或者个人均可以从世界的任何地方访问这些及应用。如何有效快速地将用户提交的应用任务分配到各个处理器上执行,以获得最短的响应时间和最有效的执行结果,这一难题使得云计算中的任务调度问题成为学术界的热点问题。许多经典与新兴的算法被应用到云计算的调度中,为适应云计算的异构性、动态性和可扩展性均作出了一定的调整和改进。现今学术界遇到的云计算调度的问题越来越多,也越来越复杂。许多科学应用,如生物信息学、化学、天文学等,这些应用中包含大量的任务,任务间存在复杂的先后约束关系,这些应用需要大量的计算和通信开销,在云计算系统中处理时已不能使用简单的图来表示。本文主要研究云计算中的任务调度,使用遗传算法来辅助完成云计算下的任务调度。本文中主要针对复杂的任务使用复杂的DAG图来进行表示,并将任务调度到云计算平台上的处理器上进行处理。本文的主要内容和创新点如下：1、提出了一种自适应工作流调度算法IAHA(Improved Adaptive heuristic algorithm)。该算法主要对HSGA算法进行改进,首先将用户提交的任务转为DAG图后,对DAG图中的任务节点进行计算排序,考虑复杂DAG图中的拓扑结构和优先级约束,对每个染色体进行预先优化,以减少迭代次数更快获得最优解,再根据种群的情况自适应改变交叉和变异率来控制和引导算法获得最优解。2、提出了带任务重复的工作流调度算法D-IAHA(Improved Adaptive heuristic algorithm with duplication)。该算法利用处理器上出现的空闲时间隙来重复出度最多或者完成时间最晚的父任务来达到减少处理器间任务通信时间的目的,从而使子任务的开始时间提前,整个调度的调度时间缩短。与此同时考虑了冗余任务的删除,在调度后检查是否存在冗余的重复任务,若存在则删除,这样不至于增加处理器的计算负载。3、提出了一种带任务重复的任务划分策略算法D-ITPS(Improved task partitioning Strategy with duplication),该算法首先将DAG图中的一些满足归并条件的任务进行归并,然后将所有的任务按照划分策略划分为一个个包,将包按照Max-Min策略整体调度到处理器上执行,在完成基本的映射后,检测每个染色体是否可以通过任务重复来减少通信时间,若可以则在处理器的空闲时间隙重复任务以减少总调度长度。4、通过实验仿真工具CloudSim对本文中提出的三种算法进行实验,与其他几种算法进行比较,验证本文中三种算法的可行性和有效性。