学位论文 > 优秀研究生学位论文题录展示

异构多核环境下的任务调度方法研究

作　者: 刘侃侃
导　师: 吴国华
学　校: 杭州电子科技大学
专　业: 计算机应用技术
关键词: 异构多核系统任务应用模型独立任务调度依赖任务调度
分类号: TP302
类　型: 硕士论文
年　份: 2010年
下　载: 128次
引　用: 0次
阅　读: 论文下载

内容摘要

任务调度方法研究是计算机学科的基本课题之一。近年来,多核体系结构的出现,给这门学科带来了新的挑战。多核系统的任务调度问题是把若干个任务分配到一定数目的处理器上,使得任务完成时间最短。有效的任务调度方法将会大大提高多处理器系统的计算能力,降低不必要的能耗。异构多核系统由于其处理器特性的不同,任务调度方法也尤为复杂。异构环境下的任务调度方法主要分为两个步骤:(一)将一个应用程序分割成若干个任务,生成应用模型,尽可能的获取任务间的并行性。(二)根据应用模型,采用一定任务调度算法,将任务分配到合适的处理器上。本文以独立任务和依赖任务为研究对象,对异构多处理器系统的任务调度方法进行深入的研究。通过对当前的独立任务调度算法和依赖任务调度算法的改进,获得更快的任务完成时间和较小的算法复杂度。主要工作体现在如下几个方面:(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%左右,是一种高效的依赖任务调度方法。

全文目录

摘要  5-6
ABSTRACT  6-9
第一章绪论  9-16
  1.1 研究背景及意义  9-10
  1.2 研究现状  10-14
  1.3 研究内容  14-15
  1.4 论文组织结构  15-16
第二章应用模型研究  16-23
  2.1 相关背景  16-17
  2.2 处理器模型  17-18
  2.3 任务模型  18-22
    2.3.1 任务属性  18-19
    2.3.2 任务分割方法  19-20
    2.3.3 任务模型  20-22
  2.4 本章小结  22-23
第三章独立任务调度算法研究  23-34
  3.1 Min-Min 算法  23-25
  3.2 Div-Sub 算法  25-30
  3.3 仿真及结果分析  30-33
    3.3.1 实验数据生成原则  30
    3.3.2 实验结果  30-33
  3.4 本章小结  33-34
第四章基于表结构的依赖任务调度算法研究  34-53
  4.1 算法前提条件  34-36
  4.2 HEFT 算法  36-39
  4.3 APS 算法  39-45
  4.4 仿真及结果分析  45-51
    4.4.1 实验数据生成原则  45-47
    4.4.2 实验评估原则  47
    4.4.3 实验结果  47-49
    4.4.4 算法优化  49-51
  4.5 本章小结  51-53
第五章总结与展望  53-55
致谢  55-56
参考文献  56-61
附录  61

异构多核环境下的任务调度方法研究

内容摘要

全文目录

相似论文