基于自适应混沌的多核任务调度算法研究

摘要

随着高性能处理器的不断发展，异构多核处理器逐渐成为了现代处理器发展的方向。异构多核处理器具有效率高、成本低等特点，深受人们喜爱，也成为了当前的热门的处理器系统。多核处理器必须通过合适的任务调度策略才能充分发挥自身的高性能优势。异构多核处理器系统任务调度问题是NP完全问题，有很多智能算法在解决此类问题上已经得到了应用，但是依旧存在任务调度效率低、任务调度不合理等问题。为进一步提高多核处理器的系统性能，有必要进行新的任务调度策略研究。
　　本文在分析研究现有任务调度基本原理及策略的基础上，提出了解决多核任务调度问题的DAG图和任务模型。本文在介绍遗传算法、蚁群算法和混沌理论的基础上，设计实现了基于遗传和蚁群的多核任务调度算法，仿真结果表明遗传算法后期收敛效果差，而蚁群算法前期收敛很慢，两个算法都比较容易过早收敛，陷入局部最优解。为了提高算法性能，论文将遗传与蚁群算法的优势相结合，并引入混沌优化策略，提出自适应混沌的多核任务调度算法。算法开始利用混沌理论的随机性和遍历性，初始化种群，扩大前期解的搜索范围。然后利用遗传操作保留每代的最优解，同时将每代的最差解进行混沌优化，生成新的可行解。在遗传操作收敛速率逐渐变慢时，引入蚁群操作的正反馈思想，利用之前搜索的有效信息来指导本代搜索，同时对本代搜索的最优解进行混沌优化，增加解的多样性，提高全局搜索能力，防止算法过早收敛。最后，本文给出了整个算法的任务调度流程，并用C++语言实现了该算法的任务调度。
　　为验证提出任务调度策略的可行性和高效性，本文使用随机任务产生器TGFF生成3组随机任务数据，分别用遗传算法、蚁群算法和所提出算法所实现的任务调度对这3组数据进行测试。仿真结果表明，与遗传算法、蚁群算法相比，本文提出的算法不仅在寻优效果更好，收敛速度更快，而且算法运行时间更短，大大节省了时间开销，有效地提升了多核处理器任务调度的效率。
　　论文工作对今后异构多核系统任务调度算法的研究具有一定的参考意义。

目录

封面

声明

中文摘要

英文摘要

插图索引

表格索引

缩略语对照表

目录

第一章绪论

1.1 研究背景和意义

1.2 国内外研究现状

1.3 论文所要做的工作

1.4 论文的组织结构

第二章 多核任务调度研究

2.1 任务调度理论

2.2 基本的任务调度技术

2.3 任务调度问题的复杂性分析

2.4 任务调度模型

2.5 本章小结

第三章 基于自适应混沌算法的多核任务调度方案设计

3.1 基于遗传的任务调度算法实现和分析

3.2 基于蚁群的任务调度算法实现和分析

3.3 混沌理论

3.4 基于自适应混沌理论的多核任务调度算法设计

3.5 本章小结

第四章 基于自适应混沌算法的多核任务调度实现

4.1 BACMTS算法流程

4.2 目标函数设计

4.3 混沌算法初始化任务

4.4 遗传操作

4.5 蚁群操作

4.6 本章小结

第五章 算法仿真与测试

5.1 算法仿真环境

5.2 随机任务产生器

5.3 仿真设置

5.4 算法仿真结果与分析

5.5 本章小结

第六章 总结和展望

参考文献

致谢

作者简介

1.基本情况

2.教育背景