基于遗传算法的异构多核关键任务低功耗调度研究

论文摘要

近年来，日益突出的能耗问题促使处理器结构由单核向多核转变。多核处理器系统利用调度策略及低功耗技术可有效控制处理引擎的运行速率及功耗，成为降低系统能耗的有效途径之一。然而，现有低功耗任务调度技术多针对单核系统，难以充分发挥多核处理器的能耗优化效果，而异构多核处理器各处理引擎在执行任务过程中频率及功耗等参数的不同，使得基于异构多核处理器系统的低功耗调度问题更加复杂，成为当今学术界研究的热点课题。基于异构多核系统的低功耗任务调度是一个典型的NP完全问题。解决该问题的现有算法多采用两阶段的启发式策略，首先利用当前异构多核平台的划分算法将任务分配至各处理单元，然后，在给定的任务分配方案下，结合低功耗技术及调度算法确定任务的执行顺序和处理引擎的电压或频率级别。当前算法多依赖于随机搜索策略，算法的时间复杂度较高且较少关注任务特性对低功耗技术节能效果的影响，针对现有算法运行效率低及节能效果欠佳的问题，本文提出了一种改进的异构多核低功耗调度策略。针对异构多核低功耗调度算法的任务划分策略，提出了一种改进的遗传算法。该算法结合模拟退火思想的Metropolis接受准则，改进遗传算法的种群更新机制以扩大问题的解空间，克服传统遗传算法易于陷入局部最优解的“早熟”现象。改进后的划分策略将任务分配方案编码为染色体，利用遗传算法和模拟退火算法的相关算子搜索能耗最低的任务分配方案。针对算法的低功耗任务调度策略，在分析现有算法的基础上，结合当前流行的动态电压缩放技术，提出了一种基于关键任务分析的低功耗调度算法。文中首先分析研究了关键任务对任务实时性的影响，在给定的任务分配策略下，优先安排时效性紧迫的任务节点，然后，在满足任务截止期要求的前提下，以最大限度地降低系统能耗为目标，调整任务所处执行单元的电压级别。为验证算法性能，根据当前异构多核平台下的低功耗任务调度模型，设计实现了一个模拟系统，并在该系统下仿真实现了文中的解决方案及若干现有算法，将文中算法的任务划分及低功耗调度策略从能耗降低率和时间复杂度两方面进行评估。实验结果表明，本文的异构多核低功耗调度算法的任务划分策略扩大了问题的解空间，为低功耗调度提供了更加丰富的任务分配方案；算法的低功耗调度策略在有效地减少了系统能耗的同时显著地降低了算法的时间复杂度。

论文目录

• 摘要
• Abstract
• 目录
• 插图索引
• 附表索引
• 第1章 绪论
• 1.1 研究背景
• 1.2 异构多核低功耗调度问题研究概述
• 1.2.1 能耗来源及优化技术
• 1.2.2 异构多核低功耗调度研究现状
• 1.2.3 关键问题分析
• 1.3 本文工作及组织结构
• 1.4 小结
• 第2章 异构多核低功耗调度相关研究
• 2.1 异构多核低功耗调度问题的模型描述
• 2.1.1 能量模型
• 2.1.2 任务模型
• 2.1.3 系统模型
• 2.2 异构多核低功耗调度算法总体结构
• 2.3 异构多核低功耗调度算法研究
• 2.3.1 任务划分策略
• 2.3.2 低功耗调度算法
• 2.4 相关近似算法
• 2.5 小结
• 第3章 基于改进遗传算法的异构多核任务划分策略
• 3.1 问题描述
• 3.2 传统遗传算法收敛性分析
• 3.3 算法设计
• 3.3.1 异构多核任务划分的遗传算法描述
• 3.3.2 一种基于改进遗传算法的任务划分策略
• 3.3.3 算法收敛性及时间复杂度分析
• 3.4 小结
• 第4章 基于关键任务分析的低功耗调度算法
• 4.1 低功耗调度算法框架
• 4.2 低功耗调度算法设计
• 4.2.1 基于关键任务的调度算法
• 4.2.2 电压选择策略
• 4.3 算法时间复杂度分析
• 4.4 小结
• 第5章 算法验证及结果分析
• 5.1 实验平台系统
• 5.2 算法性能实验分析
• 5.2.1 任务划分算法性能分析
• 5.2.2 低功耗调度算法性能分析
• 5.2.3 异构多核低功耗调度算法性能分析
• 5.3 小结
• 结论与展望
• 参考文献
• 致谢
• 附录A 攻读学位期间发表的学术论文
• 附录B 攻读学位期间所参与的研究项目