多核系统静态任务调度算法研究
发布时间：2021-04-25 17:17
多核处理器现已成为微处理器的主流架构,大大提高了微处理器性能,因此任务调度作为影响多核系统性能的关键因素,逐渐引起人们的重视。对于多核系统静态任务调度问题,基于列表的任务调度算法因其实现简单、效果良好而受到大家的关注,SLS算法作为其典型代表有其固有缺陷:只考虑基于BL权值的优先级调度列表,而忽略了任务图调度解空间的其他调度列表,因此对任务图调度解空间的探索极其不足。针对SLS算法这一固有缺陷,本文结合生物类算法初始化多个问题可行解进行同步寻优迭代的策略,选择4种权值计算策略所形成的优先级调度列表作为初始调度列表组合,同时提出任务扰动迭代策略,对初始调度列表组合内的列表进行同步迭代以生成最优调度列表,该算法实现简单,且能够对任务图调度解空间进行更广泛的探索,从而获得更好的任务调度结果。由于任务图复杂的拓扑结构,常常导致多个任务具有相同的任务权值,使任务陷入权值一致排序困境。为解决这一问题,本文参考SC算法宏块和宏块拓扑序列的概念,提出一种基于特殊宏块的列表调度算法,将权值一致的任务集中为特殊宏块,然后遍历其宏块拓扑序列以产生更优任务调度列表,从而优化任务调度结果。本文通过对任务图和系统...
【文章来源】：合肥工业大学安徽省 211工程院校 教育部直属院校
【文章页数】：68 页
【学位级别】：硕士
【文章目录】：
致谢
摘要
ABSTRACT
第一章 绪论
1.1 课题的背景和意义
1.2 国内外研究现状
1.2.1 国外研究现状
1.2.2 国内研究现状
1.3 论文的主要工作
1.4 论文的组织架构
第二章 多核系统任务调度问题概述
2.1 多核系统架构
2.1.1 同构多核处理器
2.1.2 异构多核处理器
2.2 多核处理器通信模型
2.2.1 总线通信模型
2.2.2 片上网络通信模型
2.2.3 全互联通信模型
2.3 多核系统的优势以及面临的问题
2.4 任务调度概述
2.4.1 任务调度模型
2.4.2 任务调度基本约束
2.4.3 任务调度分类
2.4.4 任务调度问题的NPC特性
2.5 多核系统任务调度常用算法
2.5.1 列表调度算法
2.5.2 聚簇调度算法
2.5.3 任务复制调度算法
2.5.4 遗传算法
2.5.5 蚁群算法
2.6 本章小结
第三章 一种基于任务扰动的组合迭代型列表调度算法
3.1 任务权值计算策略
3.2 SLS算法介绍
3.3 SLS算法缺陷分析
3.4 生物类算法的初始化策略
3.4.1 遗传算法种群初始化策略
3.4.2 粒子群算法的初始化策略
3.5 一种基于任务扰动的组合迭代型列表调度算法
3.5.1 组合迭代策略
3.5.2 初始调度列表组合
3.5.3 任务扰动迭代策略
3.5.4 算法的具体实现
3.6 本章小结
第四章 一种基于特殊宏块的列表调度算法
4.1 任务权值一致排序困境
4.2 SC算法介绍
4.2.1 宏块
4.2.2 宏块拓扑序列
4.2.3 宏块划分
4.2.4 SC算法实现
4.3 基于特殊宏块的列表调度算法
4.3.1 特殊宏块
4.3.2 遍历特殊宏块拓扑序列策略
4.3.3 算法具体实现
4.4 本章小结
第五章 算法性能验证和分析
5.1 算法性能评估参数
5.2 测试任务图生成
5.3 算法测试平台
5.4 算法测试方案
5.5 算法测试与分析
5.6 本章小结
第六章 总结与展望
参考文献
攻读硕士学位期间的学术活动及成果情况
【参考文献】：
期刊论文
[1]异构分布式计算环境下一种新型表调度算法[J]. 李云洋,周川,王琦. 计算机工程. 2018(08)
[2]混合粒子群算法的异构多核处理器间任务调度[J]. 田辉. 单片机与嵌入式系统应用. 2017(05)
[3]基于多核系统NoC架构的静态列表调度算法[J]. 李东生,李龙,王骁,高杨. 计算机应用研究. 2016(04)
[4]面向多核任务调度的混合遗传算法[J]. 姚英彪,王璇. 系统工程与电子技术. 2015(08)
[5]基于关键路径和任务复制的多核调度算法[J]. 谢志强,韩英杰,齐永红,杨静. 国防科技大学学报. 2014(01)
[6]基于粒子群优化的异构多处理器任务调度算法[J]. 李静梅,张博,王雪. 计算机应用研究. 2012(10)
[7]并行嵌入式系统中具有通信竞争任务调度问题的高级列表调度方法[J]. 穆鹏程,NEZAN Jean-Franois,RAULET Mickaёl,COUSIN Jean-Gabriel. 中国科学:信息科学. 2011(03)
[8]改进的异构多处理器的实时任务调度算法研究[J]. 尹杨美,徐成,刘彦. 计算机应用研究. 2010(04)
[9]片上网络拓扑结构[J]. 常政威,谢晓娜,熊光泽. 计算机应用. 2007(11)
[10]分布式环境下多任务调度问题的分析与求解[J]. 何琨,赵勇,陈阳. 系统工程理论与实践. 2007(05)
博士论文
[1]粒子群算法及其应用研究[D]. 雷开友.西南大学 2006
硕士论文
[1]多核系统静态任务调度问题研究[D]. 杨俊.合肥工业大学 2016
[2]异构多核处理器的任务调度策略研究[D]. 陈文艳.湖南大学 2013
本文编号：3159779
【文章来源】：合肥工业大学安徽省 211工程院校 教育部直属院校
【文章页数】：68 页
【学位级别】：硕士
【文章目录】：
致谢
摘要
ABSTRACT
第一章 绪论
1.1 课题的背景和意义
1.2 国内外研究现状
1.2.1 国外研究现状
1.2.2 国内研究现状
1.3 论文的主要工作
1.4 论文的组织架构
第二章 多核系统任务调度问题概述
2.1 多核系统架构
2.1.1 同构多核处理器
2.1.2 异构多核处理器
2.2 多核处理器通信模型
2.2.1 总线通信模型
2.2.2 片上网络通信模型
2.2.3 全互联通信模型
2.3 多核系统的优势以及面临的问题
2.4 任务调度概述
2.4.1 任务调度模型
2.4.2 任务调度基本约束
2.4.3 任务调度分类
2.4.4 任务调度问题的NPC特性
2.5 多核系统任务调度常用算法
2.5.1 列表调度算法
2.5.2 聚簇调度算法
2.5.3 任务复制调度算法
2.5.4 遗传算法
2.5.5 蚁群算法
2.6 本章小结
第三章 一种基于任务扰动的组合迭代型列表调度算法
3.1 任务权值计算策略
3.2 SLS算法介绍
3.3 SLS算法缺陷分析
3.4 生物类算法的初始化策略
3.4.1 遗传算法种群初始化策略
3.4.2 粒子群算法的初始化策略
3.5 一种基于任务扰动的组合迭代型列表调度算法
3.5.1 组合迭代策略
3.5.2 初始调度列表组合
3.5.3 任务扰动迭代策略
3.5.4 算法的具体实现
3.6 本章小结
第四章 一种基于特殊宏块的列表调度算法
4.1 任务权值一致排序困境
4.2 SC算法介绍
4.2.1 宏块
4.2.2 宏块拓扑序列
4.2.3 宏块划分
4.2.4 SC算法实现
4.3 基于特殊宏块的列表调度算法
4.3.1 特殊宏块
4.3.2 遍历特殊宏块拓扑序列策略
4.3.3 算法具体实现
4.4 本章小结
第五章 算法性能验证和分析
5.1 算法性能评估参数
5.2 测试任务图生成
5.3 算法测试平台
5.4 算法测试方案
5.5 算法测试与分析
5.6 本章小结
第六章 总结与展望
参考文献
攻读硕士学位期间的学术活动及成果情况
【参考文献】：
期刊论文
[1]异构分布式计算环境下一种新型表调度算法[J]. 李云洋,周川,王琦. 计算机工程. 2018(08)
[2]混合粒子群算法的异构多核处理器间任务调度[J]. 田辉. 单片机与嵌入式系统应用. 2017(05)
[3]基于多核系统NoC架构的静态列表调度算法[J]. 李东生,李龙,王骁,高杨. 计算机应用研究. 2016(04)
[4]面向多核任务调度的混合遗传算法[J]. 姚英彪,王璇. 系统工程与电子技术. 2015(08)
[5]基于关键路径和任务复制的多核调度算法[J]. 谢志强,韩英杰,齐永红,杨静. 国防科技大学学报. 2014(01)
[6]基于粒子群优化的异构多处理器任务调度算法[J]. 李静梅,张博,王雪. 计算机应用研究. 2012(10)
[7]并行嵌入式系统中具有通信竞争任务调度问题的高级列表调度方法[J]. 穆鹏程,NEZAN Jean-Franois,RAULET Mickaёl,COUSIN Jean-Gabriel. 中国科学:信息科学. 2011(03)
[8]改进的异构多处理器的实时任务调度算法研究[J]. 尹杨美,徐成,刘彦. 计算机应用研究. 2010(04)
[9]片上网络拓扑结构[J]. 常政威,谢晓娜,熊光泽. 计算机应用. 2007(11)
[10]分布式环境下多任务调度问题的分析与求解[J]. 何琨,赵勇,陈阳. 系统工程理论与实践. 2007(05)
博士论文
[1]粒子群算法及其应用研究[D]. 雷开友.西南大学 2006
硕士论文
[1]多核系统静态任务调度问题研究[D]. 杨俊.合肥工业大学 2016
[2]异构多核处理器的任务调度策略研究[D]. 陈文艳.湖南大学 2013
本文编号：3159779
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3159779.html
