多核处理器中任务调度与负载均衡的研究

论文摘要

多年以来,处理器性能的提升主要依赖其工作频率的提高,然而受到芯片功耗及发热等因素的影响,这种做法已接近极限。在这种情况下多核处理器应运而生并得到了迅速发展,与此同时多核处理器系统也为任务调度与负载均衡研究提供了广阔的发展空间。目前,在多核处理器的任务调度和负载均衡中,首先将任务节点分配到处理器,其次在处理器中对任务节点进行调度,目标是使系统的整体执行时间最少,最大化发挥多核处理器的优势。本文对现有任务分配和任务调度算法进行改进,并在改进算法的同时考虑到任务处理器之间和处理核之间的负载均衡,主要工作包括以下两个方面：一方面,在现有DAG任务分配模型的基础上建立任务分组,并对任务分配算法进行改进,改进的重点是在进程任务进行复合时,不是单纯依据进程任务的通信时间来进行复合,而是综合考虑复合两个进程任务的通信时间和执行时间两个因素,依据设定的标准,选择最佳的两个进程任务进行复合,使分配到处理器上的进程任务更加均衡。模拟实验表明,改进的任务分配算法在处理器上的任务负载度和在处理器之间的任务执行时间差两方面比已有任务分配算法均有改进。另一方面,针对遗传算法在初始种群生成具有一定的盲目性问题,提出均衡种群遗传算法(Balanced Population Genetic Algorithm, BPGA),该算法对标准遗传算法初始种群生成算法进行改进,首先,在保证任务节点的高度约束的条件下,将任务节点依据高度值进行分组；然后,随机选择处理核和任务节点,并保证分配到每个处理核上的任务节点数基本均等,最后,在任务分配完成后,再根据任务分配到处理核上的执行时间大小实现任务节点的调整,使分配到每个处理核上任务节点的执行时间相对均衡,从而缩短整体任务执行时间,进一步提高处理核之间任务负载均衡。实验结果显示,BPGA算法在处理核间的任务负载均衡度和整体执行时间两个方面优于其他同类算法。

论文目录

• 摘要
• Abstract
• 插图索引
• 附表索引
• 第1章 绪论
• 1.1 课题研究背景及意义
• 1.2 国内外研究现状
• 1.2.1 任务调度现状研究
• 1.2.2 负载均衡现状研究
• 1.3 本文的主要工作
• 1.4 本文组织结构
• 1.5 小结
• 第2章 任务调度及负载均衡的相关介绍
• 2.1 多核处理器
• 2.1.1 多核处理器简介
• 2.1.2 多核处理器特点
• 2.2 任务调度与负载均衡
• 2.2.1 任务调度
• 2.2.2 负载均衡
• 2.3 遗传算法
• 2.3.1 遗传算法基本术语
• 2.3.2 遗传算法基本思想
• 2.3.3 遗传操作
• 2.4 小结
• 第3章 一种任务分配的改进算法
• 3.1 引言
• 3.2 任务分配模型分类
• 3.2.1 周期模型
• 3.2.2 TIG模型
• 3.2.3 TPG模型
• 3.2.4 DAG模型
• 3.3 任务模型的建立
• 3.3.1 DAG任务模型定义
• 3.3.2 任务进行分配原则
• 3.4 任务模型分配算法
• 3.4.1 任务分配算法实现
• 3.4.2 任务分配算法存在的问题及原因
• 3.5 任务分配算法改进
• 3.5.1 改进分配算法思路
• 3.5.2 改进分配算法实现
• 3.6 任务分配到处理器
• 3.7 实验仿真与分析
• 3.7.1 实验环境
• 3.7.2 实验数据分析
• 3.8 小结
• 第4章 基于遗传算法的任务调度与负载均衡研究
• 4.1 引言
• 4.2 任务调度与遗传算法
• 4.2.1 任务调度策略
• 4.2.2 编码结构
• 4.2.3 初始种群
• 4.3 适应度函数
• 4.4 选择策略
• 4.5 交叉算子
• 4.5.1 交叉操作算法设计
• 4.5.2 交叉操作的改进
• 4.6 变异算子
• 4.6.1 变异操作算法实现
• 4.6.2 变异算子的改进
• 4.7 算法终止条件
• 4.8 性能分析
• 4.9 实验分仿真与分析
• 4.9.1 实验环境
• 4.9.2 实验数据分析
• 4.10 小结
• 结论
• 参考文献
• 致谢
• 附录A 攻读学位期间发表的学术论文