可重构系统中实时任务调度算法的研究及实现

论文摘要

随着FPGA (Field Programmable Gate Arrays)器件的出现及快速发展,一种基于该器件新型的局部重构技术受到学术界越来越广泛的关注。可重构计算技术改变了传统的嵌入式系统的设计方法,兼顾了系统的性能和设计的灵活性。利用局部重构技术,可重构计算系统可以对可重构逻辑器件上的指定计算资源进行独立地配置,而不影响器件上其余部分的执行。这允许多任务系统中硬件任务的动态插入和删除,有效地提高了系统的整体性能和资源利用率。本文从三个方面介绍了可重构系统：硬件基础——FPGA,系统模型,操作系统。实时多任务系统不仅需要支持空间资源的共享,而且要保证任务及时完成。本文对可重构操作系统中调度器和放置器的算法做了深入的研究,解决了2D区域模型下的硬件实时任务在线放置和调度问题。利用拒绝区域等概念,提出了新颖且高效的放置策略。该策略使任务在时间和空间上放置的都非常密集,为后续任务留出更大的连续空闲区域。然后,提出了一个两阶段的总体调度策略,在该调度策略的第一阶段,通过与放置算法恰当的结合,进行任务的直接部署；第二阶段,通过引入保留列表的重排,对到来任务做进一步的调度尝试。通过大量的模拟实验表明,本文提出的算法有很高的硬件任务接收率和空间利用率。论文最后部分对论文工作进行了总结,并对下一步研究进行了展望。

论文目录

• 中文摘要
• ABSTRACT
• 第1章 引言
• 1.1 研究背景
• 1.2 问题定义
• 1.3 相关工作
• 1.3.1 可重构计算系统
• 1.3.2 任务调度
• 1.3.3 任务放置
• 1.4 论文结构
• 第2章 可重构系统概述
• 2.1 FPGA介绍
• 2.1.1 FPGA分类及基本概念
• 2.1.2 FPGA配置粒度
• 2.2 可重构系统模型
• 2.2.1 动态可重构系统
• 2.2.2 可重构系统耦合度
• 2.3 操作系统
• 2.4 本章小结
• 第3章 FPGA上任务调度框架
• 3.1 FPGA区域模型
• 3.2 定义及术语
• 3.3 本章小结
• 第4章 硬件实时任务在线调度算法的研究
• 4.1 任务放置算法
• 4.1.1 2D放置指标
• 4.1.2 3D指标和放置算法
• 4.2 任务总体调度算法
• 4.3 本章小结
• 第5章 性能评估与实验分析
• 5.1 复杂度分析
• 5.1.1 放置算法复杂度
• 5.1.2 调度算法复杂度
• 5.2 模拟实验
• 5.2.1 实验假设
• 5.2.2 性能比较
• 5.2.3 结果分析
• 5.3 简单OS原型设计
• 5.3.1 硬件任务控制块
• 5.3.2 硬件任务状态转换
• 5.3.3 具体方案
• 5.4 本章小结
• 第6章 结论与展望
• 6.1 结论
• 6.2 未来的工作及展望
• 参考文献
• 致谢
• 科研项目和论文发表情况