【作者】 李涛；

【导师】 杨愚鲁；

【作者基本信息】 南开大学 ， 计算机应用技术， 2007， 博士

【摘要】 以通信和多媒体技术为代表的应用需求的迅速发展,对传统的微处理器和ASIC的性能提出了更高的要求。VLSI技术的进步促进了以FPGA为代表的可重构硬件的快速发展,尤其是具有动态部分重构能力的可重构硬件的出现,使可重构计算成为解决这类问题的重要方法。但是,限于目前可重构硬件的系统结构和重构技术等方面的发展现状,可重构计算的实用化还存在诸多挑战性问题。针对微处理器和可重构硬件构成的动态重构系统,本文重点研究了系统的重构方式、可重构资源管理、硬件任务的调度与布局以及软硬件划分等问题,并给出了相应的解决方案和实验分析,为进一步研究可重构计算及其实用化打下了良好的基础。本文的主要研究内容包括:在分析FPGA配置结构和动态模块对应的部分位流结构的基础上,实现了一种动态模块的重定位方法。基于模块的部分重构是降低系统重构开销的一种有效方法,但由于部分位流是在FPGA的某位置上预综合得到的,配置到FPGA上并启动该电路模块的执行也必须是在相同的位置,因此会导致时间上相互交叉的模块产生冲突。利用重定位技术可以根据需要将该模块转移到同构资源的空闲位置上,能够提高系统的执行效率。提出了一种基于配置页的可重构资源管理方法,并基于Virtex II平台FPGA实现了相应的原型系统。系统对不同的可重构资源进行分类建模,分析了配置页尺寸的确定方法,并以配置页为基本单位进行管理。运行时可以根据应用需求分配一段由不同数量的连续配置页构成的逻辑区域,以及回收和合并空闲配置页等,有效地实现了1D划分下的可重构资源管理。提出了可重构硬件的一种2D区域模型,并给出了该模型下可重构资源管理和硬件任务布局的算法及实验分析。基于任务上边界的最大空闲矩形保持算法能够有效地管理可重构硬件上的空闲资源,便于在运行时动态分配与回收可重构资源以及使用FF和启发式BF算法实现硬件任务的在线布局。与1D划分相比,能够提高可重构硬件的资源利用率,从而提高系统的性能。基于可重构硬件的动态部分重构能力,采用2D区域模型进行可重构资源的分配与回收,并考虑硬件任务的重构延时和并发执行等特性,采用遗传算法和爬山算法实现了面向动态重构系统的软硬件划分,其中对划分结果的评价使用了动态优先级调度算法。软硬件划分能够有效地将任务流图表示的应用调度到系统中的微处理器和可重构硬件上,以充分发挥两者各自的优势,达到优化动态重构系统性能的目标。更多还原

【Abstract】 With the rapid increase of the computing requirement from some applications such as communication and multimedia technologies, the performance improvement of traditional processors and ASICs has been required greatly. Due to the advancement of the VLSI technology and the reconfigurable hardware such as FPGA, the reconfigurable computing has become an important resolution for these kinds of applications, especially the advent of the partially run-time reconfigurable ability of reconfigurable hardware. But, it is very difficulty for reconfigurable computing to become actual universal and high performance computing system with the current reconfigurable hardware architecture and reconfiguration technology. Based on the dynamical reconfigurable system composed of the microprocessor and reconfigurable hardware, some important issues have been studied in this dissertation. For example, the reconfiguration schemes, the management of reconfigurable resources, the scheduling and placement of hardware task and the hardware/software partitioning. Some solutions are proposed and the experiment results are analyzed. The results show that they are benefit for the reconfigurable computing and its practicality. All of the researches are as follows.Based on the analysis of the configuration architecture of FPGA and the structure of partial bitstream for dynamical module, the Dynamical Module ReLocation method (DMRL) is implemented. Module based partial reconfiguration is efficient for decreasing the reconfiguration overhead. The partial bitstream was generated on some area of FPGA in advance. So this dynamical module won’t be configured rightly when its original area has been occupied by another running module. The dynamical module can be shifted to another empty area on the homogeneous resource using DMRL method. And the execution efficiency of the reconfigurable system will be improved.The configuration page based reconfigurable resource management is proposed and the prototype system is implemented on the Virtex II platform FPGA. The different reconfigurable resource is modeled respectively and organized by the configuration page. And the size of the configuration page is discussed. Different number of continuous configuration pages can be allocated to a hardware task at run time. Unused configuration pages can be reclaimed and some neighboring configuration pages can be merged. The reconfigurable resource management is implemented effectively in one-dimensional area model.A two-dimensional area model of reconfigurable hardware is proposed in this dissertation. The reconfigurable resource management and the hardware task placement are presented based on the two-dimensional area model. The unoccupied resources on the reconfigurable hardware can be effectively managed by the Task-Top based Keep All Maximal Empty Rectangles algorithm. It facilities the dynamical allocation and reclamation of the reconfigurable resource, and the FF and heuristic BF algorithms to select a Maximal Empty Rectangle to place hardware task at run time. Compared to the one-dimensional area model, the utilization per cent of reconfigurable hardware is improved, and so the system performance.Based on the two-dimensional area model of the partially dynamical reconfigurable hardware, the hardware/software partitioning for the dynamical reconfigurable system is implemented by the genetic algorithm and hill-climb algorithm, where the configuration delay and parallel execution of hardware tasks are considered. And the partitioning results are evaluated by the dynamical priority scheduling algorithm. The application presented by the task flow graph can be scheduled to the microprocessor and reconfigurable hardware effectively using the partitioning algorithm. The results show that the partitioning algorithm is helpful for them to cooperate with each other and improve their performance.更多还原