可重配置硬件系统调度算法的模拟与分析

论文摘要

可编程逻辑门阵列FPGA器件已成为嵌入式系统设计领域关注的热点,同时一些计算密集型任务可以在FPGA上灵活的实现并执行。硬件任务使传统的软硬件协同设计领域发生了重大变革。实时调度算法是实时系统中的关键而且调度分析是实时应用设计的必经步骤。动态可重构FPGA允许硬件任务运行时动态放置及移出。动态可重构FPGA上硬件任务的调度对传统的实时调度理论带来挑战,到目前为止还没有像软件任务一样成熟的调度算法。本文设计和实现一个动态可重配置系统硬件任务实时调度的模拟与分析工具。该工具将抽象可重构计算系统的主要特征,允许用户在其上建立不同类型的调度算法,并对调度算法的各方面性能进行评估,为支持动态可重构计算的操作系统研究提供便利。本文讨论了实时调度算法目前两种主要验证方法：系统模拟验证、形式化校验方法（定理推导方法,模型验证方法）。提出了动态可重构FPGA上可调度性分析的模拟原理和方法以及模型检测的自动机模型的建立方法。然后讨论了一种动态可重配置系统实时调度的模拟与分析工具--VeriTool的详细设计与实现。最后使用VeriTool进行实验分析得出各验证方法的性能评估,并给出了各方法具体的应用场景。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题背景
• 1.2 研究的目标和意义
• 1.3 创新点
• 1.4 论文安排
• 第2章 相关工作
• 2.1 实时调度基本理论
• 2.1.1 基本概念和相关术语
• 2.1.2 实时系统
• 2.1.3 实时调度
• 2.1.4 实时调度算法的性能评估标准
• 2.2 常用调度算法概述
• 2.2.1 RM调度算法
• 2.2.2 DM调度算法
• 2.2.3 EDF调度算法
• 2.2.4 LSF调度算法
• 2.3 实时调度分析的三种方法
• 2.3.1 定理推导验证方法
• 2.3.2 模拟验证方法
• 2.3.3 模型检测方法
• 2.4 FPGA调度问题的相关工作
• 2.4.1 1D模型下的硬件任务实时调度问题及可调度判定研究进展
• 2.4.2 2D模型下的区域管理策略和调度问题研究进展
• 2.4.3 区域碎片度的评估问题研究现状
• 第3章 基于模拟方法的FPGA实时调度分析
• 3.1 基本概念
• 3.2 模拟的硬件任务模型
• 3.3 模拟调度系统模型
• 3.4 可调度性判定
• 3.5 调度性能的评价标准
• 3.6 任务的放置策略选择
• 3.7 本章小结
• 第4章 基于模型检测的FPGA实时调度分析
• 4.1 时间自动机及UPPAAL简介
• 4.1.1 时间自动机理论
• 4.1.2 UPPAAL简介
• 4.2 使用UPPAAL对可抢占调度进行建模
• 4.2.1 问题描述
• 4.2.2 建模
• 4.3 使用UPPAAL对不可抢占调度进行建模
• 4.3.1 问题描述
• 4.3.2 建模
• 4.4 本章小结
• 第5章 验证工具Veri Tool的设计与实现
• 5.1 系统结构设计
• 5.1.1 总体系统结构
• 5.1.2 Client端结构设计
• 5.1.3 Server端结构设计
• 5.1.4 Client/Server通信协议
• 5.2 model-checking以及推导验证部分
• 5.2.1 model-checking验证流程
• 5.2.2 推导验证流程
• 5.3 模拟验证
• 5.3.1 模拟器的结构
• 5.3.2 模拟器的运行流程
• 5.3.3 模拟验证引擎的运行流程
• 5.4 本章小结
• 第6章 实验结果及分析
• 6.1 各种方法接受率的测试
• 6.1.1 模拟验证与模型检测接受率比较
• 6.1.2 定理推导与模拟检测接受率的比较
• 6.1.3 不同重配置比例下各方法任务接受率的测试
• 6.2 各种方法可伸展性的测试
• 6.3 实验结果分析
• 第7章 结论与展望
• 参考文献
• 致谢
• 科研项目和论文发表情况