基于多核处理器任务复制的分簇调度算法研究

摘要

随着多核处理器处理对象所包含的信息量不断的增大，任务之间的通信越来越频繁，人们对多核处理器的性能要求也不断的增高，使多核处理器的任务调度面临了巨大的挑战。由于基于任务复制的分簇调度策略在处理器资源有限、任务量大、以及任务之间通信频繁的系统中，能获得较好的调度效果，所以基于任务复制的分簇调度算法的研究也成为了近年来的研究热点。
　　传统的基于多核处理器任务复制的分簇调度算法在一定程度上减少了通信开销，加快了任务执行速度，但是在调度长度以及系统利用率上仍不够理想，优化条件过于复杂，并存在时间复杂度过高的情况。为改善传统算法中存在的不足，本文提出了一种基于任务复制的分簇调度改进算法，该算法采用二轮任务复制的分簇策略来减少任务集的调度长度，提高系统利用率。具体工作如下：
　　针对LG、PPA两种典型算法中任务调度长度过长，时间复杂度偏高的问题，通过扩大任务复制范围、简化复制条件的方法来减少任务之间的通信开销，降低计算量。该方法将复制的范围从最佳前驱任务扩展到满足复制条件的所有前驱任务，以使整个任务集的调度长度变得更短，从而进一步减少了任务之间的通信开销；并将任务复制条件简化为处理器的空闲时间大于前驱任务的执行时间，以达到降低时间复杂度的目标。
　　针对传统算法中处理器利用率偏低的问题，在簇合并原理的基础上，提出专门为簇合并服务进行任务复制的方法，以减少所需处理器的数目，提高处理器的利用率。在不影响子任务最早开始时间的前提下，在第一轮任务复制过程中未被复制的前驱任务，如果满足第二轮复制条件的话，将对这些任务进行复制，使在合并冗余簇的步骤中，能尽可能减少冗余簇，使满足必要簇映射所需处理器的数目尽量少，进而提高整个系统利用率。
　　为了验证该本文算法的有效性，本文在PC平台上用Microsoft Visual C++6.0对该算法进行了仿真实验，并对实验数据进行了对比和分析。实验表明，本文算法的调度长度和处理器的使用数目都优于传统算法，并具有更小的时间复杂度，有一定的实用性，对并行计算机系统性能的提升具有一定的意义。

目录

文摘

英文文摘

插图索引

插表索引

第1章 绪 论

1.1 多核处理器任务调度的研究的背景和意义

1.2 多核处理器任务调度的国内外研究现状

1.3 本文研究的内容

1.4 本文的组织结构

1.5 小结

第2章 多核处理器调度算法的研究

2.1 任务分类

2.2 多核处理器任务调度评价模型

2.3 多核处理器任务调度算法分类

2.4 多核处理器的任务调度模型

2.4.1 基于独立任务的调度模型

2.4.2 非独立任务调度模型

2.5 小结

第3章 基于多核处理器任务复制的分簇调度整体方案

3.1 调度的目标以及基本过程

3.2 调度模型

3.3 基于任务复制的分簇调度策略的核心问题分析

3.4 基于任务复制的分簇调度策略的改进

3.4.1 算法借鉴

3.4.2 策略改进思路

3.5 小结

第4章 一种基于多核处理器任务复制的分簇调度改进算法

4.1 基于任务复制的分簇调度改进算法的调度过程

4.1.1 为获得最早开始时间的第一次复制阶段

4.1.2 为簇合并服务的第二次复制阶段

4.1.3 簇的合并阶段

4.2 基于任务复制的分簇调度改进算法的算法设计

4.3 时间复杂度分析

4.4 实例分析说明

4.5 小结

第5章 算法验证及结果分析

5.1 仿真平台系统

5.1.1 仿真的硬件和软件平台

5.1.2 实验方案

5.1.3 算法评估标准

5.2 实验结果

5.3 实验结果分析

5.4 小结

总结和展望

参考文献

致 谢

附录A 攻读学位期间发表的学术论文

附录B 攻读学位期间所参与的研究项目