可重构系统操作系统布局与任务调度算法设计与实现

摘要

随着集成电路技术的发展,FPGA的容量已达数百万门且具有动态部分可重构功能。由FPGA作为可以动态分配的计算资源与指令集处理器构成的可重构混合系统具有计算性能高、灵活性强、适用范围广的优点。为了提高FPGA的利用率、简化开发流程和提高系统的性能,操作系统必须对可重构器件提供更有效的支持。
　　 本文对可重构系统操作系统中资源管理和任务管理部分的布局算法和任务调度算法进行了研究。对布局算法中的Edmonds算法、MH算法和KVIT算法以及任务调度算法中的Horizon算法、Stuffing算法和MGS算法从数据结构、算法设计方法等方面进行了较深入的分析和比较,将Stuffing算法改进为CStuffing算法,对KVIT算法和MGS算法中的Match函数根据新到达硬件任务与已布局硬件任务顶点的不同匹配情况给出了具体的实现方案。结合实验平台分别对MH和KVIT布局算法以及Stuffing、CStuffing和MGS任务调度算法进行了算法性能的比较和验证。实验结果表明KVIT布局算法在执行时间和任务拒绝率方面稍优于MH布局算法,但MH布局算法具有在空闲空间管理和碎片整理方面无法取代的优势；CStuffing算法的执行时间略小于Stuffing算法,MGS任务调度算法在执行时间、任务拒绝数和芯片利用率方面稍优于Stuffing任务调度算法,但MGS算法对存储空间有较高要求。

目录

文摘

英文文摘

第一章 绪论

1.1 引言

1.2 研究目标及研究意义

1.3 论文的主要工作及组织结构

第二章 可重构计算技术概述

2.1 可重构计算技术的定义

2.2 可重构计算技术的发展历史

2.3 可重构计算技术的时空域计算特性

2.4 可重构计算技术的实现

2.4.1 系统重构方式

2.4.2 可重构逻辑器件的分类

2.4.3 可重构混合系统

2.5 支持可重构计算的混合系统操作系统

2.6 本章小结

第三章 可重构系统操作系统布局算法设计与实现

3.1 模型描述和基本概念

3.2 Bazargan算法

3.2.1 基于非重叠空闲矩形的算法

3.2.2 基于重叠空闲矩形的算法

3.3 Bazargan算法的改进

3.4 Edmonds算法

3.4.1 算法设计

3.4.2 时间和空间复杂度分析

3.5 Edmonds算法的改进

3.6 KVIT算法

3.6.1 算法描述

3.6.2 基于被占用区域连续度的代价函数

3.7 Match算法描述

3.7.1 2v情形的Match算法

3.7.2 3v情形的Match算法

3.7.3 4v情形的Match算法

3.7.4 Match算法小结

3.8 仿真实验及结果分析

3.8.1 仿真实验环境与实验方案

3.8.2 实验结果与性能分析

3.9 本章小结

第四章 可重构系统操作系统任务调度算法设计与实现

4.1 模型描述和基本概念

4.1.1 资源模型与任务模型

4.1.2 现有技术的局限

4.2 Horizon算法

4.2.1 一维Horizon算法

4.2.2 二维Horizon算法

4.3 一维Stuffing算法

4.4 一维Horizon与Stuffing算法的比较

4.5 Stuffing算法的改进

4.5.1 CStuffing算法数据结构

4.5.2 CStuffing算法描述

4.6 MGS算法

4.6.1 数据结构

4.6.2 MGS算法描述

4.6.3 MGS代价函数

4.6.4 二维MGS算法

4.7 MGS、Horizon和Stuffing算法的比较

4.8 KVIT与MGS中Match算法的比较

4.9 仿真实验及结果分析

4.9.1 仿真实验环境与实验方案

4.9.2 实验结果及性能分析

4.10 本章小结

第五章 总结与展望

5.1 论文总结

5.2 进一步的工作

致谢

参考文献

作者在读期间研究成果