异构多核系统中面向细粒度任务集的调度算法研究

异构多核系统中面向细粒度任务集的调度算法研究

论文摘要

随着异构多核处理器的快速发展,异构多核系统中的任务调度成为研究热点。目前,适用于普通任务集调度的算法在调度细粒度任务集时,存在处理器负载失衡,处理器空闲时间多,并行性差和冗余任务等诸多缺陷,严重影响了多核系统的性能。本文针对这些问题展开研究。结合聚簇、列表和复制算法各自的优势,本文提出了一种高效的适合细粒度任务集的调度算法HCDUL,HCDUL分为聚簇、优先级计算和就绪任务列表建立、任务调度、复制上层节点四个阶段。通过聚簇降低了通信开销,调度过程中动态更新就绪列表,并实时对其排序,关键任务有最高的优先级;每次取列表头节点,并调度到完成时间最小的处理器核上;利用当前节点之前的空闲时间段复制上层节点,进一步减小通信开销,提前子任务的开始时间,从而缩短整个任务集的完成时间。针对复制算法存在冗余任务问题,本文提出了一种优化算法HDO。首先,查找并删除冗余任务,然后计算冗余任务后继节点的开始时间,最后调整后继节点。通过消除冗余任务,提前了后续节点开始时间,节省了处理器资源,并进一步缩短了调度长度。本文使用随机生成图进行了大量实验,在调度细粒度任务集时,与HEFT和HCNF算法比较,HCDUL算法的调度长度率SLR更小,加速比Speedup更大。同样,使用大量的随机生成图对HDO算法验证,HCNF和HCDUL算法的调度结果经HDO算法优化之后,总执行时间比率SETR更小,并且在一定程度上,调度长度率SLR减小,加速比Speedup增加。

论文目录

  • 摘要
  • Abstract
  • 目录
  • 插图索引
  • 附表索引
  • 第1章 绪论
  • 1.1 选题背景与意义
  • 1.2 调度算法研究的状况
  • 1.2.1 国外研究状况
  • 1.2.2 国内研究状况
  • 1.3 本文主要研究内容
  • 1.4 论文组织结构
  • 1.5 本章小结
  • 第2章 异构多核系统与调度模型
  • 2.1 多核系统
  • 2.1.1 多核系统硬件环境研究
  • 2.1.2 异构多核平台的软件系统设计
  • 2.2 任务调度模型
  • 2.2.1 运行系统的数学模型
  • 2.2.2 任务的数学模型
  • 2.2.3 调度的约束条件分析
  • 2.3 任务调度的 NP 完全性综述
  • 2.3.1 静态调度的 NP 完全问题
  • 2.3.2 静态调度算法的复杂性分析
  • 2.4 本章小结
  • 第3章 多核系统中的调度算法分析
  • 3.1 多核系统中调度算法分类
  • 3.1.1 按调度思想分类
  • 3.1.2 按调度环境分类
  • 3.2 启发式算法
  • 3.2.1 聚簇算法
  • 3.2.2 列表算法
  • 3.2.3 复制算法
  • 3.3 异构多核系统中经典算法分析
  • 3.3.1 HEFT 算法
  • 3.3.2 HCNF 算法
  • 3.4 本章小结
  • 第4章 针对细粒度任务集的调度方法设计
  • 4.1 算法缺陷分析
  • 4.2 HCDUL 算法
  • 4.2.1 HCDUL 算法原理
  • 4.2.2 HCDUL 算法实例分析
  • 4.2.3 算法复杂度分析
  • 4.3 复制算法的缺陷
  • 4.4 HDO 算法
  • 4.4.1 HDO 算法原理
  • 4.4.2 HDO 算法实例分析
  • 4.4.3 算法复杂度分析
  • 4.5 本章小结
  • 第5章 实验仿真及性能分析
  • 5.1 HCDUL 性能测试设计
  • 5.1.1 性能测试参考标准
  • 5.1.2 性能测试方案设计
  • 5.2 测试结果分析
  • 5.3 三种算法时间复杂度比较
  • 5.4 HDO 性能测试方案设计
  • 5.5 测试结果分析
  • 5.6 本章小结
  • 结论
  • 参考文献
  • 致谢
  • 附录A 攻读学位期间发表的学术论文
  • 附录B 攻读学位期间参与的科研项目
  • 相关论文文献

    • [1].基于粗糙集的耦合任务集聚类方法[J]. 机械制造 2017(07)
    • [2].深度优先搜索在耦合任务集识别中的应用[J]. 科学技术与工程 2010(14)
    • [3].基于改进型统一调度算法改善任务集的可调度性[J]. 计算机工程与科学 2017(06)
    • [4].基于装配任务集的装配过程建模研究[J]. 中国机械工程 2012(11)
    • [5].多任务集实时交换局域网高速调度方案[J]. 湖南师范大学自然科学学报 2009(04)
    • [6].Hadoop集群中给定候选任务集的最大利润问题[J]. 计算机技术与发展 2018(12)
    • [7].云计算平台中面向车联网应用的能耗感知调度算法[J]. 计算机科学 2016(03)
    • [8].耦合任务集执行序列优选理论与方法初探[J]. 中国机械工程 2011(12)
    • [9].基于内部迭代的耦合任务集求解方法[J]. 计算机集成制造系统 2008(12)
    • [10].产品协同设计过程冲突预消解研究[J]. 组合机床与自动化加工技术 2009(08)
    • [11].多任务多联盟并行生成:模型与求解[J]. 系统工程理论与实践 2008(04)
    • [12].内聚度和粒度在作战任务分解评估中的应用[J]. 电光与控制 2012(12)
    • [13].嵌入式系统的低功耗调度算法研究[J]. 计算机测量与控制 2009(12)
    • [14].面向复杂任务集的任务调度算法[J]. 现代防御技术 2019(03)
    • [15].面向紧急任务的柔性车间混合动态调度模型[J]. 计算机应用研究 2009(10)
    • [16].产品多领域协同设计中协同与协同度分析及应用[J]. 制造业自动化 2008(08)
    • [17].一种基于混合任务集的高能效调度算法[J]. 电子技术应用 2013(08)
    • [18].基于AHP的耦合任务集资源分配权重确定方法[J]. 计算机工程与应用 2018(21)
    • [19].面向抖动优化的任务静态优先级指派算法[J]. 计算机工程 2012(20)
    • [20].产品多领域协同设计中协同分析及量化研究[J]. 济南大学学报(自然科学版) 2009(02)
    • [21].紧贴部队实际 把握特点规律——提高“动”中抓建质量的关键[J]. 政工导刊 2016(11)
    • [22].基于启发搜索策略的飞行仿真系统实时调度算法[J]. 沈阳工业大学学报 2011(01)
    • [23].硬实时调度的线性近似分析方法[J]. 计算机应用 2010(02)
    • [24].空间科学探测任务集同论证平台[J]. 科研信息化技术与应用 2011(03)
    • [25].一种针对依赖性周期任务的实时多核调度算法[J]. 计算机应用研究 2013(05)
    • [26].无线传感器网络异步任务集双效节能延迟调度算法研究[J]. 传感技术学报 2008(01)
    • [27].基于多核处理器的节能任务调度方法[J]. 中国电子科学研究院学报 2012(02)
    • [28].云计算中虚拟资源调度的决策系统[J]. 计算机测量与控制 2011(12)
    • [29].基于DSM的协同设计过程规划方法[J]. 兰州理工大学学报 2009(06)
    • [30].多核平台下考虑能耗的实时任务分派与调度研究[J]. 智能计算机与应用 2015(04)

    标签:;  ;  ;  ;  ;  

    异构多核系统中面向细粒度任务集的调度算法研究
    下载Doc文档

    猜你喜欢