基于粒子群优化算法的多核多线程系统任务调度研究

摘要

多核多线程系统的任务调度是当前高性能处理器研究的热点之一。近年来，针对当前多核处理器任务调度问题，出现了许多的研究方案。旨在减少通信开销、缩短任务调度长度、提高处理器性能。多数任务调度问题已被证明是NP完全问题，各种调度算法都是在特定的限制条件下得到次优解。任务调度是从两个方向解决任务的资源分配的方法过程，两个方向分别是时间及空间，一个优秀的任务调度算法能较大程度提高多核多线程系统的综合性能。
　　目前人们普遍认为最具有发展前景的任务调度技术是启发式调度，比如遗传算法、粒子群算法，希望能在智能算法中找到解决此类问题的方法。遗传算法在任务调度上模型的应用偏于相对复杂、容易过早收敛，而粒子群优化算法对次优解的收敛速度通常要快于遗传算法。
　　基于上述背景，本文针对多核多线程系统任务调度进行编码，提出一种基于粒子群优化算法的多核多线程系统任务调度算法。建立多核多线程系统模型，原始的粒子位置更新方式、适应度函数以及部分参数都已经无法适用该模型，因此，对粒子群算法进行适应性的改进。通过与已有的基于多核多线程系统的智能算法即遗传算法进行比较，分析获取最优解的效率，以及获取最优解的命中率，改进的粒子群算法都有一定程度上的提高。

目录

声明

摘要

1．1 课题研究背景

1．2 课题的研究目的和意义

1．3 国内外研究现状

1．4 主要工作

1．5 论文结构安排

2 多核多线程系统与算法研究

2．1 多核处理器

2．1．1 多核处理器概念的提出

2．1．2 CMP的技术优势

2．2 多核处理器的优势与应用

2．3 现有调度算法的分析

2．3．1 优先级列表调度算法

2．3．2 任务复制算法

2．3．3 随机搜索算法

2．3．4 遗传算法研究

2．4 本章小结

3．1 任务模型

3．1．1 多核静态调度的任务模型

3．1．2 多核动态任务调度模型

3．2 处理器模型

3．2．1 处理器负载均衡

3．2．2 处理器亲和性

3．3 本章小结

4 基于粒子群优化的调度算法研究

4．1 粒子群算法

4．2 PSO算法的基本公式

4．3 惯性权重

4．4 初始化

4．5 算法流程

4．6 本章小结

5．1 算法测试平台

5．2 测试结果与分析

5．3 本章小结

6．1 结论

6．2 展望

致谢

参考文献

附录1 攻读硕士学位期间发表的论文

附录2 攻读硕士学位期间参加的科研项目