摘  要

        有效融合了专用集成电路(Application Specific Integrated Circuit, ASIC)与通用目的处理器(General Purpose Processor)优势的可重构计算系统，以其良好的灵活性，可重构性以及优异的计算性能，日益成为学术界与工业界应用研究的热点。可重构计算研究主要涉及可重构软硬件平台、可重构操作系统、编程语言及相关算法与实际工程应用等领域。

针对可重构计算及其硬件平台的特点，阐述了可重构计算中任务调度与放置的重要性。任务调度主要关注硬件任务与可重构区域的映射，受可重构资源数与任务间时序关系等的影响，目标为降低任务的总执行时间与可重构平台的配置开销；硬件任务放置旨在提高可重构芯片的利用率与任务的接受率，侧重对可重构资源的管理，主要受制于可重构空闲区域的大小与放置方案。

        充分考虑了任务间的数据依赖与通信约束、可重构平台的异质性以及任务非并发执行对可重构系统性能的影响，对任务调度机制进行建模与分析，用有限状态机(Finite State Machine, FSM)描述任务的时序转换、以有向无环图(Directed Acyclic Graph, DAG)表述任务间的依赖，提出了一种基于组策略的硬件任务调度算法(Clustering Strategy Scheduling, CSS)。该算法能较好地平衡任务调度开销与调度性能(如任务总执行时间，FPGA配置开销)，并通过实验指出随非并发任务在系统中比例的增加，任务总执行时间将急剧上升。

        针对当前任务放置算法如Horizon、Stuffing、BestFitt和FirstFit等的不足提出了基本改进方法。在一维资源模型中，提出了一种任务长度感知度的放置策略(LHAPS)，该策略是对Horizon与Stuffing放置策略的改进，能够有效地降低任务的总执行时间与碎片数。

        对硬件平台与调度算法进行了实验与性能测试。在Xilinx Virtex-II Pro上实现了DES的部分动态可重构，验证了其在FPGA上部分动态可重构的运行效果。

论文报告