一种改进的异构多处理器实时任务调度算法研究

摘要

随着科学的日新月异，人们对计算机的处理能力提出更好、更快、更强的要求与挑战，多处理器技术便是这个挑战的有效突破口。任务调度是这个突破口中最为关键的技术之一。随着科技的进一步发展，多处理技术向着不同处理器对同一个任务有不同的处理速度的异构方向发展，这种异构性也让异构多处理器的任务的调度问题变得更加复杂。
　　 调度算法研究中，任务模型大多数采用有向无环图DAG(Directed AcyclicGraph)。任务的调度问题，已被证明是一个NP完全问题。现有的大多数异构多处理器实时任务调度算法采用的方式是首先初始化分簇，然后将簇进行放置，再对任务进行调度。基于复制可扩展实时任务调度算法与异构最早时间优先算法由于在分簇时综合考虑任务执行时间、处理器空闲状态、前趋关系等多个因素从而引起算法时间复杂度过高。
　　 针对此种情况，本文研究一种改进的异构多处理器实时任务调度算法HRTSA(Heterogeneous Real—time Task Scheduling Algorithm for multiprocessors)。本文在初始化分簇时提出一种基于前趋约束的最小执行时间分簇策略以降低时间复杂度，为了保证调度成功率，在放置策略和调度策略都进行改进。论文的具体改进工作如下：
　　 根据异构多处理器实时任务中同一子任务在不同处理器上执行时间各不相同的特点，本文提出一种基于前趋约束的最小执行时间分簇策略。这种策略将在某一处理器上具有最小执行时间的节点分配至同一处理器上执行，仅考虑节点的执行时间与前趋关系，以降低分簇算法的时间复杂度。当存在个别性能较优的处理器时，采用基于前趋约束的最小执行时间分策略会将大量节点分至较优的处理器上执行。这种情况将引起个别处理器过载，其它处理器空闲的问题。针对此问题，在放置各簇任务至各处理器时，采用负载均衡的放置策略。这种放置方式在保证处理器负载均衡的同时，能有效地提高任务的处理效率。
　　 为了减少任务通信时延，提高处理器的利用率，本文对现有的任务调度算法进行了改进，通过采用三种复制策略减少通信时延，以提高任务执行效率；并采用了冗余删除策略，删除不必要的冗余节点，以提高处理器的利用率。
　　 为了评估本文的算法的有效性，本文在PC平台上用Visual C++6.0实现了本文的算法及对比算法。实验分析表明本文提出的HRTSA算法，采用基于前趋约束的最小执行时间分簇策略有效地降低了时间复杂度，通过多重调度策略与冗余删除策略，在降低算法时间复杂度的同时，保证了任务的调度成功率、加速比。

目录

文摘

英文文摘

插图索引

附表索引

第1章 绪论

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

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

1.3 本文研究的内容和意义

1.4 本文工作与本文结构

1.5 小结

第2章 异构多处理器实时任务调度的相关研究

2.1 异构多处理器实时任务调度的研究方法

2.1.1 任务模型的三个发展阶段

2.1.2 研究不同阶段的任务调度的平台及其意义

2.2 异构多处理器的实时任务调度研究的相关概念

2.3 基于异构多处理器的实时任务调度算法分析

2.3.1 RTSDA算法

2.3.2 HEFT算法

2.3.3 CPOP算法

2.3.4 其它任务调度方法

2.4 小结

第3章 异构多处理器实时任务分簇策略研究

3.1 任务分簇策略分析

3.1.1 RTSDA分簇策略

3.1.2 HEFT分簇策略

3.1.3 遗传分簇策略

3.1.4 最小执行时间分簇策略

3.2 基于前趋约束的最小执行时间分簇策略

3.2.1 算法基本思想

3.2.2 算法描述

3.2.3 算法实例

3.2.4 算法性能评估分析

3.3 小结

第4章 一种改进的异构多处理器实时任务调度算法

4.1 调度算法的总体设计

4.2 基于负载均衡的聚合

4.2.1 初次分配处理器

4.2.2 采用负载均衡因子进行合并

4.3 任务复制

4.3.1 基于处理器空闲间隙复制

4.3.2 基于空闲处理器的簇复制

4.4 删除无效冗余节点

4.5 算法分析

4.5.1 合并算法分析

4.5.2 复制策略分析

4.5.3 冗余节点处理

4.5.4 算法时间复杂度分析

4.6 小结

第5章 算法实验评估

5.1 仿真实验

5.2 算法评估

5.3 实验数据

5.3.1 实验数据图

5.3.2 实验数据分析

5.4 小结

总结

参考文献

致谢

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

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