多核系统静态任务调度问题研究

发布时间：2017-09-29 13:09

  本文关键词：多核系统静态任务调度问题研究

  更多相关文章： 调度算法 拓扑序列 静态任务 多核

【摘要】：由于传统单核处理器的性能已经遇到发展瓶颈,多核处理器应运而生并获得广泛应用。作为多核技术的一个重要方面,任务调度是备受关注的一类NPC(Non-deterministic Polynomial Complete)问题。对于多核处理器的静态任务调度问题,经典列表调度(Simple List Scheduling, SLS)算法难以获得满意的调度解。本文从经典列表调度算法缺陷——只考虑任务优先级列表而忽略其它对应于更好调度结果的任务图拓扑序列出发,以拓展任务图拓扑序列搜索空间为指导,提出了迭代型列表调度方法,并给出两种迭代型列表调度算法实现：ILS-Mb (Iterative List Scheduling with Macroblock)和ILS-RS (Iterative List Scheduling with Random Swapping).其中迭代型列表调度算法ILS-Mb通过遍历宏块拓扑序列扩大任务图拓扑序列搜索空间,迭代型列表调度算法ILS-RS则通过对换两个随机任务的优先级以生成新的任务图拓扑序列。ILS-Mb算法和ILS-RS算法的共同之处在于多次进行列表调度并根据调度长度最小化原则筛选最优调度解。本文进一步地结合粒子群算法采用多个初始最优解的基本思路提出组合型列表调度方法。组合型列表调度方法以多个最优任务图拓扑序列作为初始解避免单个任务图拓扑序列陷入局部最优解。迭代型列表调度方法和组合型列表调度方法的结合形成迭代-组合型列表调度方法,以更高的算法时间复杂度以期获取更小的调度长度。文中通过理论分析证明,对于任意的一个任务图,两种迭代型列表调度方法所得的调度长度必不大于经典列表调度算法。为证实本文提出的迭代型列表调度方法的良好性能,文中采用四种常见类型任务图生成大量的任务图样本进行两个部分的对比实验。统计结果首先表明：在全互联通讯环境迭代型的列表调度算法ILS-Mb和ILS-RS能够有效改善经典列表调度算法的调度解,尤其在通信代价比超过1的情况下,调度性能提升超过14.6%,最大的调度性能提升达到102.8%以上：在片上网络通讯环境ILS-Mb算法和ILS-RS算法的相对性能优势更加明显。统计结果指出迭代型列表调度算法的调度效果优于ALS (Advanced List Scheduling)和CPOP (Critical Path on Processor)算法。实验数据还表明ILS-Mb和ILS-RS算法对调度解初始值不具有敏感性。
【关键词】：调度算法 拓扑序列 静态任务 多核
【学位授予单位】：合肥工业大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP332
【目录】：

• 致谢7-8
• 摘要8-9
• ABSTRACT9-16
• 第一章 绪论16-21
• 1.1 课题的背景与意义16-17
• 1.2 国内外研究现状17-19
• 1.2.1 国外研究现状17-18
• 1.2.2 国内研究现状18-19
• 1.3 论文的主要工作19
• 1.4 论文的组织结构19-21
• 第二章 任务调度问题概述21-31
• 2.1 多核微处理器的体系结构21-23
• 2.2 任务调度问题的多核系统模型23-24
• 2.3 任务调度问题的应用程序模型24-25
• 2.4 任务调度问题相关概念25-27
• 2.5 任务调度问题的NPC特性27-28
• 2.6 任务调度方案28-30
• 2.6.1 任务复制28-29
• 2.6.2 任务聚簇29
• 2.6.3 列表调度29-30
• 2.7 本章小结30-31
• 第三章 迭代型列表调度算法的设计方案31-41
• 3.1 经典列表调度算法及其缺陷31-34
• 3.2 迭代型列表调度方法34-35
• 3.3 组合型列表调度方法35-36
• 3.4 迭代—组合型列表调度方法36-37
• 3.5 片上网络通讯环境下的列表调度37-40
• 3.6 本章小结40-41
• 第四章 迭代型列表调度方法的算法实现41-56
• 4.1 SC算法41-47
• 4.1.1 宏块41-42
• 4.1.2 宏块拓扑序列42
• 4.1.3 宏块划分42
• 4.1.4 子任务图42-43
• 4.1.5 SC算法实现43-45
• 4.1.6 SC算法性能测试45-47
• 4.2 ILS-Mb算法47-52
• 4.2.1 宏块调度47-48
• 4.2.2 ILS-Mb算法实现48-52
• 4.3 ILS-RS算法52-55
• 4.4 本章小结55-56
• 第五章 静态任务调度算法的性能测试56-70
• 5.1 性能评估参数选取56
• 5.2 样本任务图的生成56-58
• 5.3 对比试验58-69
• 5.3.1 ILS算法和SLS算法的性能对比59-67
• 5.3.2 ILS和其它算法的性能对比67-68
• 5.3.3 ILS算法调度解初始值的设定68-69
• 5.4 本章小结69-70
• 第六章 总结和展望70-72
• 参考文献72-75
• 攻读硕士学位期间的学术活动和成果情况75

【相似文献】

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

1 孟宪福;基于优先级的任务调度与负载均衡模型研究[J];小型微型计算机系统;2005年09期

2 廖晓文;廖京盛;;时间触发模式的任务调度与分解策略[J];单片机与嵌入式系统应用;2006年07期

3 樊晓香;;任务调度问题机制设计[J];计算机技术与发展;2008年07期

4 黄漾;;分布式环境下任务调度探讨[J];电脑知识与技术;2011年19期

5 陈军;谢立;孙钟秀;;分布式任务调度研究的新趋向[J];计算机研究与发展;1990年04期

6 陈艇;;基于混沌最优博弈的网络任务调度算法仿真[J];计算机仿真;2013年11期

7 李陶深;李明丽;张希翔;;云计算环境下任务调度技术的研究进展[J];玉林师范学院学报;2014年02期

8 刘雄文,陆鑫达;元计算环境中任务调度的深入分析[J];计算机工程与应用;2002年17期

9 罗红,慕德俊,邓智群,王晓东;网格计算中任务调度研究综述[J];计算机应用研究;2005年05期

10 张国海;江平宇;周光辉;;多设计任务调度的非合作博弈研究[J];西安交通大学学报;2007年03期

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

1 刘培培;李连;丛海鹏;谢勇;;基于多代理协商机制的任务调度系统研究[A];2006北京地区高校研究生学术交流会——通信与信息技术会议论文集（下）[C];2006年

2 张磊;马军;;描述短时资源混杂占用型任务调度的数学模型与算法[A];2005年全国理论计算机科学学术年会论文集[C];2005年

3 王军;巢玉强;彭钊轶;;基于任务调度的电能量计量采集系统的设计与实现[A];2006电力系统自动化学术交流研讨大会论文集[C];2006年

4 张志强;王万玉;王建平;李凡;袁刚;;多站多星任务调度优化模型研究[A];第二十三届全国空间探测学术交流会论文摘要集[C];2010年

5 韩云;于炯;张伟;王命全;;基于负载均衡的任务调度改进算法[A];2010年全国开放式分布与并行计算机学术会议论文集[C];2010年

6 王全民;王靓;许智宏;;网格环境中基于蚁群算法的批量任务调度的研究[A];2006北京地区高校研究生学术交流会——通信与信息技术会议论文集（上）[C];2006年

7 张晓云;岳继光;杨麟祥;;零星任务调度在多控制任务系统中的应用[A];第16届中国过程控制学术年会暨第4届全国故障诊断与安全性学术会议论文集[C];2005年

8 刘宇;刘玉荣;周冰;;基于WCF的环境减灾星座运控任务调度系统[A];第二十五届全国空间探测学术研讨会摘要集[C];2012年

9 黄文泽;邵峰晶;孙仁诚;;基于双总线安全结构的操作系统任务调度[A];2009全国计算机网络与通信学术会议论文集[C];2009年

10 杨舰;黄道平;李小亚;;GDCS任务调度的SPN模型研究[A];第二十六届中国控制会议论文集[C];2007年

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

1 王波;Linux与服务器集群技术[N];中国计算机报;2002年

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

1 赵凡宇;航天器多目标观测任务调度与规划方法研究[D];北京理工大学;2015年

2 孙明明;云计算平台上任务调度算法的研究[D];中国科学技术大学;2015年

3 郭力争;云计算环境下资源部署与任务调度研究[D];东华大学;2015年

4 黄万伟;基于服务属性区分的可重构任务调度研究[D];解放军信息工程大学;2009年

5 瞿进;可重构系统软硬功能划分及任务调度技术研究[D];解放军信息工程大学;2011年

6 周双娥;实时分布容错系统的任务调度技术研究[D];哈尔滨工程大学;2003年

7 柴亚辉;基于FPGA的高性能计算架构硬件任务与资源模型研究[D];上海大学;2012年

8 金刚;云环境下任务调度关键问题研究[D];吉林大学;2015年

9 耿晓中;基于多核分布式环境下的任务调度关键技术研究[D];吉林大学;2013年

10 陈锡明;基于NOW的任务调度和负载平衡方法研究[D];电子科技大学;2000年

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

1 张巧龙;云计算环境下任务调度问题的研究[D];江南大学;2015年

2 徐彬;云环境下基于动态融合遗传蚁群算法的DAG任务调度研究[D];南京信息工程大学;2015年

3 姜志刚;数据中心温度感知任务调度技术研究[D];南京大学;2014年

4 周凯;Hadoop任务调度本地化研究[D];华中科技大学;2014年

5 聂如云;云服务系统任务调度负载均衡的研究[D];首都经济贸易大学;2016年

6 张金虎;云计算环境下基于服务成本的任务调度研究[D];云南大学;2016年

7 王靖云;面向iVCE云平台的数据分析任务调度系统的设计与实现[D];哈尔滨工业大学;2016年

8 肖健;基于分布式任务调度的机票旗舰店系统的设计与实现[D];哈尔滨工业大学;2016年

9 李梦盈;基于动态优先级的云计算任务调度研究[D];南京信息工程大学;2016年

10 范增辉;进化算法在软件工程任务调度中的研究与应用[D];江南大学;2016年

，

本文编号：942175