可重构计算的操作系统支持研究

论文摘要

可重构计算已经成为一种能兼顾设计灵活性与性能的计算模式。对这种新计算模式的普遍应用与开发需要对底层平台细节的抽象，提供给开发人员统一的视图，此外还需要对可重构资源进行有效的管理以提高利用率。通常情况下，抽象和资源管理都是由操作系统提供的服务，因此有必要研究可重构计算的操作系统支持。本文主要在该课题上开展了部分研究，并主要完成了以下工作：首先，在对可重构计算的历史进行简单的回顾后，针对目前已经报道的可重构计算平台进行了简要分类，接着对系统的重构方式以及缩短重构时间的手段进行了总结。然后简要介绍了FPGA的岛状模型以及设计流程。第二，在分析软硬件任务本质区别的基础上，提出并实现了一种基于统一多任务模型的RTOS，称为SHUM-UCOS。它能跟踪和管理可重构资源的使用，通过硬件任务预配置技术，提高资源利用率和任务并行性。定义了两种标准硬件线程接口，对总线型和星型通信拓扑结构支持。试验表明，SHUM-UCOS能够在提升系统性能的同时，有效缩减从软件实现到硬件实现的迁移时间。第三，对于可重构计算中的硬件任务划分问题，在节点面积和任务通信约束条件下，提出了一种基于簇的层次敏感的LSCBP划分算法。该算法是一种列表算法，按照依赖优先、最早最先和碎片利用三原则构造了启发函数ASLevel，能跟踪节点分配过程并进行动态调整。该算法克服了CBP算法机械选取节点进行划分的缺点，同时算法复杂度也增大到O{|V|2+|E|}。对随机生成的任务图（节点数小于250）的划分试验表明，对于相同的DAG图，LSCBP算法能比BCP算法获得更少的任务簇（可重构资源需求量）和簇间有向边（通信代价）。第四，对于硬件任务划分问题，为了得到更好的划分结果，并在算法运行时间和解的质量之间取得更好的平衡，提出随机构造技术与遗传算法相融合的PCGA（Probabilistic Constructive Genetic Algorithm）划分算法。基本思想是利用随机构造技术能够快速构造高质量解群体的优势，产生遗传算法的初始种群，然后利用遗传算法群体性和全局搜索能力进行解的进一步优化。对于DFG图划分问题，结合列表法设计了随机构造算法，并定义了划分结果多样性的量化度量方法，从而保证了初始解群体的质量与多样性。对于具有20～100个节点的随机任务图的划分结果表明：该算法在求解质量上高于列表算法；在同等解质量的情况下，比随机产生初始群体的遗传算法运行时间提高一倍以上，并且划分问题规模越大，优势越明显。最后，研究了硬件任务的动态定位与调度问题，提出了FORS算法。为了进行可重构硬件任务的动态管理，要为硬件任务在可重构器件上找到合适的配置位置，并且进行配置后才能运行硬件任务。FORS算法采用最早最迟开始时间优先、最优化空白区域管理和配置重用的调度原则，能反映实时任务的紧迫度，快速地调度实时可配置硬件任务，同时有效的管理可重构资源。实验表明，算法可以有效提高系统的总体性能。

论文目录

• 摘要
• Abstract
• 第1章 引言
• 1.1 研究背景
• 1.2 研究现状
• 1.3 本文的主要工作
• 第2章 可重构计算及其系统
• 2.1 可重构计算的历史
• 2.2 器件基础
• 2.2.1 器件支持情况
• 2.2.2 FPGA的岛状模型
• 2.2.3 器件模型抽象
• 2.2.4 设计流程
• 2.3 可重构计算平台概览
• 2.3.1 五个典型可重构计算平台
• 2.3.2 可重构计算的分类
• 2.3.3 系统重构的方式
• 2.3.4 缩短重构时间的方法
• 2.4 可重构计算的操作系统支持
• 2.4.1 硬（软）件任务之间的主要区别
• 2.4.2 关键问题
• 2.4.3 目标平台模型
• 第3章 SHUM-UCOS:基于统一多任务模型的可重构系统RTOS
• 3.1 引言
• 3.2 相关概念
• 3.3 SHUM-UCOS的统一任务模型概述
• 3.4 模型实现
• 3.4.1 生成硬件任务预配置表
• 3.4.2 硬件任务的管理
• 3.4.3 可重构资源管理
• 3.4.4 例:创建任务
• 3.4.5 硬件任务接口设计
• 3.5 实验结果及分析
• 3.5.1 试验平台
• 3.5.2 SHUM-UCOS性能测试
• 3.5.3 应用实例
• 3.6 本章小结
• 第4章 基于簇的层次敏感的可重构系统任务划分算法
• 4.1 引言
• 4.2 问题定义
• 4.3 LSCBP算法
• 4.3.1 两种例外
• 4.3.2 算法描述
• 4.3.3 复杂度分析
• 4.4 试验及结果分析
• 4.4.1 实例分析
• 4.4.2 随机任务图结果分析
• 4.5 本章小结
• 第5章 概率构造算法与遗传算法融合的可重构系统硬件任务划分
• 5.1 引言
• 5.2 问题定义
• 5.3 概率构造算法与遗传算法的特点
• 5.3.1 概率构造算法
• 5.3.2 遗传算法
• 5.4 PCGA算法
• 5.4.1 划分结果表示方法
• 5.4.2 采用概率构造算法生成初始种群
• 5.4.3 遗传算法设计
• 5.5 实验
• 5.5.1 实验设计
• 5.5.2 实验结果及分析
• 5.6 本章小结
• 第6章 可重构硬件任务的动态调度
• 6.1 概述
• 6.2 相关概念
• 6.3 FORS调度算法
• 6.3.1 最早最迟开始执行时间优先的调度原则
• 6.3.2 配置重用
• 6.3.3 空白位置管理
• 6.3.4 可重构硬件任务调度算法
• 6.4 模拟评估
• 6.5 本章小结
• 第7章 结论与展望
• 7.1 主要贡献
• 7.2 未来研究工作
• 参考文献
• 致谢
• 附录 攻读博士期间科研工作