基于异构多核处理器的静态任务调度算法研究

发布时间：2017-06-29 11:13

  本文关键词：基于异构多核处理器的静态任务调度算法研究，由笔耕文化传播整理发布。

【摘要】：伴随着半导体制造工艺的发展,单位面积内所能集成的晶体管的数目已经达到极限,单核处理器碰到了无法逾越的障碍,多核处理器逐渐变成人们研究的热门和重点。多核处理器分为同构多核处理器和异构多核处理器,专家学者和界内人士普遍认为异构多核处理器将会是未来的主流处理器。任务调度的顺序将会直接影响处理器的性能,因此,异构多核处理器的任务调度研究已经成为研究热点。异构多核处理器的任务调度已经被证明是NP完全问题,目前还没有算法可以在多项式时间内求得最优解,现有算法大都是使用启发式的算法求得近似解,而其中的基于列表调度算法应用较为广泛。经典的基于列表调度算法有HEFT(Heterogeneous Earlier Finish Time)算法和HCNF(Heterogeneous Critical Node First)算法。HEFT算法按照ranku非递增次序调度任务,使用区间插入技术分配任务。HCNF算法优先调度关键任务,使用任务复制技术分配任务。以上算法存在调度结果不理想、处理器空闲时间段较多等问题,众多专家学者对此都提出了改进方案。综合考虑任务的约束依赖关系对调度结果的影响,使用区间插入技术和任务复制技术充分利用处理器的空闲时间段。本文吸取典型算法的优点,并综合专家学者的改进策略,在现有算法的基础上加以改进。为了评价改进算法的性能,本文通过具体的测试用例说明改进算法的具体实现过程,并对比调度结果,接着设计测试方案,调度随机生成的DAG任务图集,对实验结果进行分析比较。通过实验证明,改进算法可以在一定程度上缩短任务调度的长度,提高处理器的性能。
【关键词】：异构多核处理器 任务调度 HEFT HCNF 改进
【学位授予单位】：南京邮电大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP301.6;TP332
【目录】：

• 摘要4-5
• Abstract5-8
• 第一章 绪论8-13
• 1.1 研究背景及意义8-9
• 1.2 国内外研究现状9-12
• 1.2.1 国外研究现状9-10
• 1.2.2 国内研究现状10-12
• 1.3 论文主要工作12
• 1.4 论文组织架构12-13
• 第二章 多核处理器与任务调度13-24
• 2.1 多核处理器13-16
• 2.1.1 处理器架构13-14
• 2.1.2 同构多核处理器14-15
• 2.1.3 异构多核处理器15-16
• 2.1.4 多核处理器的特性16
• 2.2 任务调度16-17
• 2.3 任务调度模型17-19
• 2.4 动态任务调度算法19
• 2.5 静态任务调度算法19-23
• 2.5.1 随机搜索算法19-22
• 2.5.2 启发式算法22-23
• 2.6 本章小结23-24
• 第三章 异构多核处理器静态任务调度算法24-30
• 3.1 HEFT算法24-26
• 3.2 HCNF算法26-29
• 3.3 本章小结29-30
• 第四章 改进异构多核处理器静态调度算法设计30-42
• 4.1 改进算法任务调度策略30-31
• 4.1.1 算法假设条件30
• 4.1.2 改进算法执行过程分析30-31
• 4.2 算法分析31-41
• 4.2.1 算法实现原理31-36
• 4.2.2 算法实例分析36-40
• 4.2.3 改进任务调度算法时间复杂度分析40-41
• 4.3 本章小结41-42
• 第五章 模拟实验及结果分析42-47
• 5.1 性能评估参数设计42
• 5.2 随机DAG任务图生成方法42-43
• 5.3 实验分析43-46
• 5.3.1 参考DAG任务图实验43-44
• 5.3.2 随机DAG任务图实验44-46
• 5.4 本章小结46-47
• 第六章 总结与展望47-49
• 参考文献49-53
• 附录一 攻读硕士学位期间撰写的论文53-54
• 致谢54

【相似文献】

中国期刊全文数据库 前10条

1 张洋;;虞志益:引领多核处理器创新之路[J];中国发明与专利;2013年01期

2 羽路;;多核处理器悄然崛起[J];集成电路应用;2005年05期

3 ;多核处理器强调多任务并行处理[J];每周电脑报;2006年35期

4 冯磊;;多核处理器的数量裸奔[J];信息系统工程;2006年11期

5 张浩;兰峰;;多核处理器基本原理及其在汽车领域中应用的展望[J];汽车科技;2007年03期

6 何军;王飙;;多核处理器的结构设计研究[J];计算机工程;2007年16期

7 肖红;;基于多核处理器系统开发中的几个问题[J];广东广播电视大学学报;2007年04期

8 张健浪;;三大于二,多核CPU之田忌赛马[J];新电脑;2008年06期

9 都思丹;;前言:嵌入式多核处理器系统及视频信号处理技术研究进展[J];南京大学学报(自然科学版);2009年01期

10 黄国睿;张平;魏广博;;多核处理器的关键技术及其发展趋势[J];计算机工程与设计;2009年10期

中国重要会议论文全文数据库 前10条

1 郭建军;戴葵;王志英;;一种多核处理器存储层次性能评估模型[A];第八届全国信息隐藏与多媒体安全学术大会湖南省计算机学会第十一届学术年会论文集[C];2009年

2 彭林;张小强;刘德峰;谢伦国;田祖伟;;一种挖掘多核处理器存储级并行的算法[A];第15届全国信息存储技术学术会议论文集[C];2008年

3 刘杰;马彦;叶维;高剑刚;;多核处理器存储体系分析[A];第十五届计算机工程与工艺年会暨第一届微处理器技术论坛论文集（A辑）[C];2011年

4 潘送军;胡瑜;李晓维;;多核处理器瞬态故障敏感性分析[A];第五届中国测试学术会议论文集[C];2008年

5 万志涛;章恒;张若渊;;基于多核处理器的深度包检测的实现和性能评估[A];中国通信学会信息通信网络技术委员会2009年年会论文集（上册）[C];2009年

6 方娟;张红波;;多核处理器预取策略的研究[A];2010年全国开放式分布与并行计算机学术会议论文集[C];2010年

7 何军;王飙;;通用多核处理器发展现状和趋势研究[A];第十五届计算机工程与工艺年会暨第一届微处理器技术论坛论文集（A辑）[C];2011年

8 桂亚东;;高效能计算机技术展望[A];庆祝中国力学学会成立50周年暨中国力学学会学术大会’2007论文摘要集（下）[C];2007年

9 万志涛;;基于多核处理器的面向时延敏感服务的云基础架构[A];中国通信学会信息通信网络技术委员会2011年年会论文集（上册）[C];2011年

10 陈远知;;多核处理器的里程碑——TILE64[A];全国第三届信号和智能信息处理与应用学术交流会专刊[C];2009年

中国重要报纸全文数据库 前10条

1 记者 曹继军 颜维琦;我国多核处理器研究实现新突破[N];光明日报;2012年

2 庆广;多核处理器助力无线多媒体业务拓展[N];中国电子报;2009年

3 北京大学计算语言所副所长 詹卫东;多核服务器：计算优势更上层楼[N];计算机世界;2005年

4 北京大学计算语言所副所长 詹卫东;双/多核服务器 计算优势更上层楼[N];网络世界;2005年

5 江南计算技术研究所 何正未;软件滞后制约多核应用[N];计算机世界;2006年

6 李梅　编译;多核处理器新年井喷[N];计算机世界;2007年

7 英特尔产品与平台市场部门数字家庭市场经理 庄淳杰;多核将大行其道[N];计算机世界;2007年

8 本报记者 陈斌;多核处理器的未来路径[N];计算机世界;2008年

9 王悦承;Oracle改变多核定价模式[N];中国计算机报;2006年

10 ;多核：技术无悬念应用待拓展[N];计算机世界;2008年

中国博士学位论文全文数据库 前10条

1 柴松;片上多核处理器的调度算法研究[D];电子科技大学;2014年

2 王淼;面向多核处理器的并行编译及优化关键技术研究[D];国防科学技术大学;2010年

3 魏海涛;面向多核处理器的数据流程序编译关键技术研究[D];华中科技大学;2010年

4 吕海;多核处理器芯片计算平台中并行程序性能优化的研究[D];北京工业大学;2012年

5 李建华;片上多核处理器缓存子系统优化的研究[D];中国科学技术大学;2013年

6 杜建军;共享高速缓存多核处理器的关键技术研究[D];重庆大学;2011年

7 陈锐忠;非对称多核处理器的若干调度问题研究[D];华南理工大学;2013年

8 邓林;单芯片多核处理器存储优化技术研究[D];国防科学技术大学;2011年

9 吕正;多核处理器存储系统的验证方法研究[D];西北大学;2013年

10 张宇昂;三维多核处理器存储关键技术研究[D];南京大学;2015年

中国硕士学位论文全文数据库 前10条

1 秦培斌;基于多核路由器的加密卡驱动系统设计与实现[D];西南交通大学;2015年

2 张请;多核处理器关键技术研究[D];复旦大学;2014年

3 陈帅军;基于国产多核处理器核级冗余静态绑定和动态绑定机制的研究[D];哈尔滨工业大学;2015年

4 罗成;基于多核处理器的高速数码印花机数据传输处理系统硬件设计[D];浙江大学;2015年

5 宦维祥;基于众核的多租户网络出访问控制的研究[D];复旦大学;2013年

6 杨杭军;基于多核处理器的视频编解码并行算法研究[D];南京大学;2013年

7 吴熙;JPEG压缩编码在嵌入式多核处理器上的优化技术研究[D];武汉纺织大学;2015年

8 王宗炎;基于OVP的多核处理器系统级建模与评估[D];复旦大学;2014年

9 范少华;多核处理器映射关键技术研究[D];复旦大学;2014年

10 裘凯;多核处理器映射关键技术研究[D];复旦大学;2014年

  本文关键词：基于异构多核处理器的静态任务调度算法研究，，由笔耕文化传播整理发布。

本文编号：497668