论文部分内容阅读
任务调度方法研究是计算机学科的基本课题之一。近年来,多核体系结构的出现,给这门学科带来了新的挑战。多核系统的任务调度问题是把若干个任务分配到一定数目的处理器上,使得任务完成时间最短。有效的任务调度方法将会大大提高多处理器系统的计算能力,降低不必要的能耗。异构多核系统由于其处理器特性的不同,任务调度方法也尤为复杂。异构环境下的任务调度方法主要分为两个步骤:(一)将一个应用程序分割成若干个任务,生成应用模型,尽可能的获取任务间的并行性。(二)根据应用模型,采用一定任务调度算法,将任务分配到合适的处理器上。本文以独立任务和依赖任务为研究对象,对异构多处理器系统的任务调度方法进行深入的研究。通过对当前的独立任务调度算法和依赖任务调度算法的改进,获得更快的任务完成时间和较小的算法复杂度。主要工作体现在如下几个方面:(1)从任务模型和处理器模型两方面对应用模型进行介绍,对目前主要的任务分割方法、任务调度模型和处理器模型进行比较和分析。(2)基于任务交互图任务模型(Task Precedence Graph,TPG),对现有的独立任务调度方法进行研究。针对Min-Min算法在处理器性能差别较大和短作业较多两种情况下,存在的任务完成时间过长及处理器负载不均问题,提出一种改进的Div-Sub算法。Div-Sub算法在分配任务之前,先观察当前每个处理器的负载,再把该任务分配给使当前所有任务的完成时间最小的处理器。仿真结果表明,相对于Min-Min算法,Div-Sub算法在任务完成时间上提升了7%左右,是一种高效的独立任务调度方法。(3)基于有向无环图任务模型(Directed Acycling Graph,DAG),采用基于表结构的调度算法对现有的依赖任务调度方法进行研究。针对HEFT算法的两个不足,提出了一种改进的APS(Accurate Priority Scheduling)算法。第一个不足是HEFT算法的任务优先级的确定方式一次到位,无法对任务优先级进行调整。针对这个不足,APS算法根据已有的分配方案,对任务优先级进行二次估算,动态的反应任务优先级的变化。第二个不足是HEFT算法仅仅采用了一个参数对任务优先级进行估算,不够精确。针对这个不足,APS算法加入了一个新的优先级参数。仿真结果表明,APS算法在大多数情况下,任务完成时间都小于HEFT算法,在时间效率上提高了10%左右,是一种高效的依赖任务调度方法。