异构多核处理器的任务分配及能耗研究

论文摘要

多核处理器是处理器的发展趋势,根据系统的内核结构是否存在差异,多核处理器可分为同构多核和异构多核。同构多核存在一定的局限性：在系统达到极限值之后,性能就无法随着内核数量的增加而显著提升。而异构多核能很好地解决同构多核所面临的问题,可以很好地提升系统的吞吐量、减少处理器能耗,因此设计者普遍相信异构多核处理器将会变得流行起来。同时,由于每个处理核处理相同任务的时间与能耗是不同的,所以异构多核处理器的出现为任务分配与调度问题带来了新的挑战。采用不同的任务分配与调度算法,会导致不同的时间消耗与能量消耗,而采用合适的任务分配与调度算法能节约较多的能耗。目前普遍认为最有发展前途的任务分配与调度技术是先用启发式方法进行任务分组,然后再用遗传算法进行任务调度。目前在异构多核处理器的任务分配与调度研究中,对负载均衡的研究较为深入,而对能耗方面的研究较少。本文主要研究在满足实时性的条件下如何节省较多的能耗,首先改进任务分组后,然后首次用遗传算法解决异构多核处理器能耗问题,并对遗传算法任务调度的改进,提高实时性。主要贡献在以下几个方面：1.在任务分配给处理节点时,更多地考虑进程间的通信开销,改进任务分组,促使任务分组后,处理节点间通信所带来的能耗最低；2.将遗传算法应用在异构多核处理器上解决能耗问题；3.利用OpenMP将遗传算法的操作线程化,使线程化的遗传算法更适合运行在异构多核处理器环境中,减少算法本身执行所需要的时间,为节省较多的能耗做好准备；4.变异算子优化,发生变异迁移时,保证任务从时间消耗较多的处理核上往时间消耗较少的处理核上变异迁移,在一定程度上保证了负载均衡；5.遗传算法在输出最佳个体时,综合考虑时间消耗与能量消耗,与改进前的基于遗传算法的任务调度相比,实时性得到提高。

论文目录

• 摘要
• Abstract
• 插图索引
• 附表索引
• 第1章 绪论
• 1.1 研究背景和意义
• 1.2 国内外研究现状
• 1.2.1 多处理器任务调度
• 1.2.2 多核处理器任务调度
• 1.3 论文的主要工作
• 1.4 论文的组织结构
• 1.5 小结
• 第2章 异构多核任务分配与调度的相关研究
• 2.1 引言
• 2.2 多核处理器的概述
• 2.2.1 多核处理器的优点
• 2.2.2 异构多核处理器的框架
• 2.3 任务分配及任务调度的介绍
• 2.3.1 异构多核环境任务调度特性
• 2.3.2 异构多核任务分配问题
• 2.3.3 调度算法的性能评估
• 2.4 遗传算法简介
• 2.4.1 遗传算法流程
• 2.4.2 收敛性分析
• 2.4.3 遗传算法优缺点
• 2.4.4 遗传算法在任务调度中的应用
• 2.5 小结
• 第3章 一种改进的任务分配方法
• 3.1 引言
• 3.2 任务模型的研究
• 3.2.1 周期模型
• 3.2.2 DAG模型
• 3.3 任务模型的建立
• 3.4 任务分组
• 3.4.1 任务分配到处理节点原则
• 3.4.2 任务分配到处理节点算法
• 3.5 小结
• 第4章 基于遗传算法的任务调度研究
• 4.1 引言
• 4.2 基于遗传算法的任务调度
• 4.2.1 编码结构
• 4.2.2 种群的初始化和选择
• 4.2.3 交叉算子
• 4.2.4 变异算子
• 4.2.5 适应度函数
• 4.3 能耗分析
• 4.4 能耗计算
• 4.5 模拟实验
• 4.5.1 实验环境
• 4.5.2 实验主要参数
• 4.5.3 实验一
• 4.5.4 实验二
• 4.6 小结
• 第5章 遗传算法任务调度的改进
• 5.1 引言
• 5.2 OpenMP多线程编程技术
• 5.3 并行遗传算法设计
• 5.4 遗传算法变异算子优化
• 5.5 遗传算法输出结果优化
• 5.6 模拟实验
• 5.6.1 实验环境
• 5.6.2 实验
• 5.7 小结
• 结论
• 参考文献
• 致谢
• 附录A 攻读学位期间所发表的学术论文