基于异构多核处理器系统的任务调度算法研究

论文摘要

异构多核处理器系统作为多核处理器系统中一大亮点,依靠高效率、低成本的特点广受人们的喜爱,同时也成为嵌入式系统中最常用的处理器系统。在对异构多核处理器系统研究的过程中,系统任务调度问题显得尤为重要,一个好的任务调度算法可以充分发挥系统性能。异构多核处理器系统任务调度问题已经被证明是NP完全问题,故一些常用的启发式任务调度算法在解决此类问题中显得不足。于是人们将研究目光转向了智能算法,希望从智能算法中获取此类问题的解决方案。本文即是将智能近似算法中改进的遗传算法应用到了异构多核处理器系统任务调度问题,并获得了比较好的解决方案。本文首先给出了异构多核处理器系统任务调度数学模型,并在基础遗传算法的基础上,提出了应用于异构多核处理器系统任务调度模型上的基于优良种群的动态遗传算法。改进的遗传算法通过在种群初始化时使用启发式算法来构建相对优良的种群,为算法进一步计算操作提供良好的基础。在算法计算过程中,针对异构多核处理器系统任务调度问题给出了相应的适应度函数,并根据种群中个体适应度不同提出了动态自适应的交叉率和变异率,使得算法在改良种群的过程中更具针对性。为了尽量节省算法运行时间,在算法终止条件设置中,加入了种群适应度相似度来优化算法。通过上述一系列改进措施,基于优良种群的动态遗传算法既满足解要求,又具有较好的收敛性。为了验证算法改进性能,本文对算法进行了实现,并在Microsoft Visual C++ 2010环境下进行相应的可行性、参数设置和同类算法对比实验并给出了结果分析,最后证明,改进的遗传算法可以有效的解决异构多核处理器系统任务调度问题。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景及其意义
• 1.2 论文所要做的工作
• 1.3 论文的组织结构
• 第二章 异构多核处理器系统任务调度现状
• 2.1 异构多核处理器系统发展
• 2.1.1 Cell 多核处理器系统
• 2.2 异构多核处理器任务调度问题
• 2.2.1 异构多核处理器任务调度系统
• 2.2.2 异构多核处理器任务调度系统设计要点
• 2.3 异构多核处理器任务调度算法研究现状与发展
• 2.3.1 异构多核处理器任务调度研究现状
• 2.3.2 新的异构多核处理器任务调度算法理论简介
• 2.4 本章小结
• 第三章 遗传算法
• 3.1 遗传算法思想
• 3.1.1 遗传算法思想起源
• 3.1.2 遗传算法基本思想
• 3.2 模式定理
• 3.3 遗传算法解决实际问题基本步骤
• 3.4 遗传算法优缺点
• 3.5 遗传算法的改进
• 3.6 本章小结
• 第四章 异构多核处理器系统任务调度算法
• 4.1 异构多核处理器系统任务调度数学模型
• 4.2 改进遗传算法解决异构多核处理器系统调度问题
• 4.2.1 编码
• 4.2.2 种群初始化
• 4.2.3 适应度函数
• 4.2.4 选择操作
• 4.2.5 交叉操作
• 4.2.6 变异操作
• 4.2.7 终止条件
• 4.3 基于优良种群的动态遗传算法小结
• 4.4 基于优良种群的动态遗传算法实现
• 4.4.1 种群初始化算法实现
• 4.4.2 选择算法实现
• 4.4.3 交叉算法实现
• 4.4.4 变异算法实现
• 4.4.5 基于优良种群的动态遗传算法实现
• 4.5 实验
• 4.5.1 实验一：算法功能验证
• 4.5.2 实验二：算法中各个参数实验分析
• 4.5.3 实验三：算法改进性比较
• 4.6 本章小结
• 第五章 总结和展望
• 5.1 研究总结
• 5.2 研究展望
• 致谢
• 参考文献
• 作者在硕士研究生期间发表的论文