一种改进的异构多处理器实时任务调度算法研究
发布时间：2021-10-28 19:08
随着科学的日新月异,人们对计算机的处理能力提出更好、更快、更强的要求与挑战,多处理器技术便是这个挑战的有效突破口。任务调度是这个突破口中最为关键的技术之一。随着科技的进一步发展,多处理技术向着不同处理器对同一个任务有不同的处理速度的异构方向发展,这种异构性也让异构多处理器的任务的调度问题变得更加复杂。调度算法研究中,任务模型大多数采用有向无环图DAG（Directed Acyclic Graph）。任务的调度问题,已被证明是一个NP完全问题。现有的大多数异构多处理器实时任务调度算法采用的方式是首先初始化分簇,然后将簇进行放置,再对任务进行调度。基于复制可扩展实时任务调度算法与异构最早时间优先算法由于在分簇时综合考虑任务执行时间、处理器空闲状态、前趋关系等多个因素从而引起算法时间复杂度过高。针对此种情况,本文研究一种改进的异构多处理器实时任务调度算法HRTSA（Heterogeneous Real-time Task Scheduling Algorithm for multiprocessors）。本文在初始化分簇时提出一种基于前趋约束的最小执行时间分簇策略以降低时间复杂度,为了保证调...
【文章来源】：湖南大学湖南省 211工程院校 985工程院校 教育部直属院校
【文章页数】：64 页
【学位级别】：硕士
【文章目录】：
摘要
Abstract
插图索引
附表索引
第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 攻读学位期间所参与的研究项目
【参考文献】：
期刊论文
[1]考虑通信竞争的任意处理机网络表调度算法[J]. 唐小勇,唐小勇,李肯立,PADUA Divid. 中国科学（F辑:信息科学）. 2009(07)
[2]基于扩展的随机DAG的EST估算与任务调度[J]. 胡凯,姜燕,杨志斌,张新宇. 计算机工程. 2008(24)
[3]基于扩展的随机DAG的并行任务调度算法研究[J]. 姜燕,胡凯,杨志斌,张新宇. 计算机科学. 2008(07)
[4]基于任务复制的分簇与调度算法[J]. 何琨,赵勇,黄文奇. 计算机学报. 2008(05)
[5]网格环境下的静态启发式任务调度算法[J]. 张忠平,刘欣媛. 计算机研究与发展. 2008(S1)
[6]异构实时多处理器系统的动态调度算法研究[J]. 杨玉海,宾雪莲,余胜生,周敬利. 小型微型计算机系统. 2008(01)
[7]一种基于分簇复制的DAG任务图调度算法[J]. 乔伟光,曾国荪. 计算机工程. 2006(17)
[8]一种基于任务复制调度算法研究[J]. 林剑柠,吴慧中. 小型微型计算机系统. 2006(07)
[9]同构计算环境中一种快速有效的静态任务调度算法[J]. 李庆华,韩建军,Abbas A.Essa. 计算机研究与发展. 2005(01)
[10]一种基于有向无环图的实时任务调度算法[J]. 何黎刚,韩宗芬,秦啸,庞丽萍. 华中理工大学学报. 2000(10)
硕士论文
[1]基于遗传算法的网格任务调度研究及实现[D]. 陈莹.四川大学 2006
[2]基于DAG模型的高效并行任务调度算法研究[D]. 华强胜.中南大学 2004
本文编号：3463214
【文章来源】：湖南大学湖南省 211工程院校 985工程院校 教育部直属院校
【文章页数】：64 页
【学位级别】：硕士
【文章目录】：
摘要
Abstract
插图索引
附表索引
第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 攻读学位期间所参与的研究项目
【参考文献】：
期刊论文
[1]考虑通信竞争的任意处理机网络表调度算法[J]. 唐小勇,唐小勇,李肯立,PADUA Divid. 中国科学（F辑:信息科学）. 2009(07)
[2]基于扩展的随机DAG的EST估算与任务调度[J]. 胡凯,姜燕,杨志斌,张新宇. 计算机工程. 2008(24)
[3]基于扩展的随机DAG的并行任务调度算法研究[J]. 姜燕,胡凯,杨志斌,张新宇. 计算机科学. 2008(07)
[4]基于任务复制的分簇与调度算法[J]. 何琨,赵勇,黄文奇. 计算机学报. 2008(05)
[5]网格环境下的静态启发式任务调度算法[J]. 张忠平,刘欣媛. 计算机研究与发展. 2008(S1)
[6]异构实时多处理器系统的动态调度算法研究[J]. 杨玉海,宾雪莲,余胜生,周敬利. 小型微型计算机系统. 2008(01)
[7]一种基于分簇复制的DAG任务图调度算法[J]. 乔伟光,曾国荪. 计算机工程. 2006(17)
[8]一种基于任务复制调度算法研究[J]. 林剑柠,吴慧中. 小型微型计算机系统. 2006(07)
[9]同构计算环境中一种快速有效的静态任务调度算法[J]. 李庆华,韩建军,Abbas A.Essa. 计算机研究与发展. 2005(01)
[10]一种基于有向无环图的实时任务调度算法[J]. 何黎刚,韩宗芬,秦啸,庞丽萍. 华中理工大学学报. 2000(10)
硕士论文
[1]基于遗传算法的网格任务调度研究及实现[D]. 陈莹.四川大学 2006
[2]基于DAG模型的高效并行任务调度算法研究[D]. 华强胜.中南大学 2004
本文编号：3463214
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/3463214.html
