动态可重构系统实时任务调度算法研究
发布时间：2020-09-29 16:47
可重构计算技术结合了通用处理器(General-Purpose Processor, GPP)和专用集成电路(Application Specific Integrated Circuits, ASIC)两者的优点,能够提供硬件的高效性和软件的可编程性,是当前热门的研究课题之一。动态部分可重构技术是可重构计算技术的最新进展之一。该技术能够在可重构系统正常工作的情况下,配置其中部分可重构资源,使得一部分任务的执行能够与另一部分任务的配置同时进行。动态重构技术能提高系统的灵活性和资源利用率,从而提升整个系统的性能。 在动态可重构系统中,硬件任务的调度是影响动态可重构系统性能的关键因素之一。为了尽量提高系统芯片的利用率,降低硬件任务的拒绝率和调度时间开销,这就需要采用高质量的调度算法来对硬件任务进行合理的调度和管理。本文针对实时任务在二维可重构器件上的在线放置和调度问题,主要完成了以下工作： (1)本文考虑将硬件任务按照长、宽及调度时间构成一个三维资源模型,将每个硬件任务看成是一个空间块,提出了一种基于三维空间邻接度的放置算法。该算法首先对可重构资源进行编码,到达的任务总是通过某个顶点依附另一个任务的边界被放置,确定候选的放置顶点；然后以到达任务与已放置在三维空间的邻接度为代价函数,选择代价函数值最大的顶点放置任务,从而使得到达任务与已放置任务在三维空间接触的邻接面最大。可使任务安排得更紧凑,减小对系统资源的浪费,提高芯片利用率。 (2)本文提出了一种基于顶点链表的硬件任务间最小空间调度算法MSSA (minimun space scheduling algorithm),该算法充分考虑利用任务的松弛时间内的调度延迟,采用基于三维空间邻接度的放置方法,选择松弛时间内使得邻接度最大的放置顶点和任务开始执行时间来执行任务,使得任务更加整齐、紧密的放置,从而降低任务拒绝率,提高硬件任务执行的并发度和资源利用率。 (3)设计仿真实验,将MSSA调度算法分别和Stuffing算法、MGS算法、CR算法,从任务拒绝率、可重构资源面积利用率和时间复杂度上进行比较。四种算法采用相同的参数,实验结果表明,MSSA算法在任务调度成功率和芯片利用率明显优于已有算法,同时在运行时间和开销上并未明显增加。
【学位单位】：湖南大学
【学位级别】：硕士
【学位年份】：2010
【中图分类】：TP302.1
【文章目录】：
摘要
Abstract
插图索引
附表索引
第1章 绪论
1.1 研究背景
1.2 研究的意义
1.3 研究的主要内容
1.4 拟解决的关键问题
1.5 本文的组织
第2章 可重构计算技术
2.1 可重构计算技术概述
2.1.1 可重构计算技术的定义
2.1.2 可重构计算技术的发展历史
2.1.3 可重构计算的应用
2.2 动态可重构系统
2.2.1 技术分类
2.2.2 动态可重构系统的重构方式
2.2.3 动态可重构系统的优点
2.3 可重构片上系统与可重构操作系统
2.4 可重构计算系统的研究方向和难题
2.5 硬件任务在线放置模型
2.5.1 任务模型
2.5.2 资源模型
2.6 模型的描述与基本概念
2.6.1 模型的描述
2.6.2 基本概念
2.7 小结
第3章 硬件任务的放置算法
3.1 放置算法综述
3.1.1 基于矩形的放置算法
3.1.2 基于顶点链表的放置算法
3.1.3 常用放置算法的特性
3.2 一种基于空间邻接度的放置算法
3.2.1 数据结构
3.2.2 代价函数
3.2.3 算法描述
3.2.4 放置实例
3.3 仿真实验及结果分析
3.3.1 仿真试验平台
3.3.2 性能评估及分析
3.4 小结
第4章 MSSA实时任务调度算法
4.1 基本概念
4.2 调度模型
4.3 调度算法相关研究工作
4.4 MSSA调度算法
4.4.1 数据结构
4.4.2 算法描述
4.5 MSSA调度算法实例
4.6 小结
第5章 仿真实验与结果分析
5.1 仿真实验设计
5.2 实验参数
5.3 实验结果及性能分析
5.4 小结
结论和展望
参考文献
附录A 攻读学位期间所发表的学术论文与参加的项目
致谢
本文编号：2829990
【学位单位】：湖南大学
【学位级别】：硕士
【学位年份】：2010
【中图分类】：TP302.1
【文章目录】：
摘要
Abstract
插图索引
附表索引
第1章 绪论
1.1 研究背景
1.2 研究的意义
1.3 研究的主要内容
1.4 拟解决的关键问题
1.5 本文的组织
第2章 可重构计算技术
2.1 可重构计算技术概述
2.1.1 可重构计算技术的定义
2.1.2 可重构计算技术的发展历史
2.1.3 可重构计算的应用
2.2 动态可重构系统
2.2.1 技术分类
2.2.2 动态可重构系统的重构方式
2.2.3 动态可重构系统的优点
2.3 可重构片上系统与可重构操作系统
2.4 可重构计算系统的研究方向和难题
2.5 硬件任务在线放置模型
2.5.1 任务模型
2.5.2 资源模型
2.6 模型的描述与基本概念
2.6.1 模型的描述
2.6.2 基本概念
2.7 小结
第3章 硬件任务的放置算法
3.1 放置算法综述
3.1.1 基于矩形的放置算法
3.1.2 基于顶点链表的放置算法
3.1.3 常用放置算法的特性
3.2 一种基于空间邻接度的放置算法
3.2.1 数据结构
3.2.2 代价函数
3.2.3 算法描述
3.2.4 放置实例
3.3 仿真实验及结果分析
3.3.1 仿真试验平台
3.3.2 性能评估及分析
3.4 小结
第4章 MSSA实时任务调度算法
4.1 基本概念
4.2 调度模型
4.3 调度算法相关研究工作
4.4 MSSA调度算法
4.4.1 数据结构
4.4.2 算法描述
4.5 MSSA调度算法实例
4.6 小结
第5章 仿真实验与结果分析
5.1 仿真实验设计
5.2 实验参数
5.3 实验结果及性能分析
5.4 小结
结论和展望
参考文献
附录A 攻读学位期间所发表的学术论文与参加的项目
致谢
【引证文献】
相关硕士学位论文 前1条
1 赵馨;可重构嵌入式系统软硬件划分方法的研究[D];哈尔滨理工大学;2012年
本文编号：2829990
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/2829990.html
