【作者】 张宏烈；

【导师】 张国印；

【作者基本信息】 哈尔滨工程大学 ， 检测技术与自动化装置， 2011， 博士

【摘要】 随着大规模高性能可编程逻辑器件的出现以及电子设计自动化技术的不断完善,可重构计算成为系统结构领域的研究热点之一。作为一种全新的体系结构,可重构计算兼具牛的灵活性和硬件的高性能。然而传统的操作系统并不支持可重构系统的应用需求,如对可重构资源进行抽象和管理以及软硬件任务统一模型表示等功能,因此面向可重构系统的操作系统的研究还面临很多问题亟待解决。本文重点研究了可重构资源管理、任务的调度与重构配置以及软硬件划分等问题,并给出了相应的解决方案,为可重构操作系统的研究提供理论依据。本文的主要研究内容包括：1、针对空闲可重构资源的管理问题,提出一种基于图论技术的FPGA资源管理方法。该方法以矩形表示硬件任务形状,以二维区域模型为研究对象,将无向图与FPGA区域模型有机结合起来,分析出二者之间的映射关系,从而利用虚拟无向图计算最大空闲矩形集。该方法将寻找最大空闲矩形问题转化为求解有效回路和通路问题,使空闲区域划分过程大大简化。仿真结果验证了算法的可行性。2、针对动态部分重构带来的重构延时问题,研究在任务调度时减少重构配置开销方法。由于配置预取策略是加速和隐藏配置过程对应用执行时间影响的有效方法,又考虑到系统中包含多个硬件任务。因此基于预配置思想,以有向无环图的任务模型为研究对象,提出按照任务调度顺序建立任务配置预取队列的解决方案,该方案能够保证合理的配置顺序,达到配置与计算的统一。3、研究任务调度问题。调度算法是评价软硬件任务划分方案的标准,面向可重构系统的任务调度需要考虑硬件任务的重构延时和并发执行等特性,提出一种采用预配置策略的链式调度算法。该算法给出基于关键路径与任务工作量的调度优先级计算方法,通过合理调度,使得计算与配置尽可能在时间上重叠,达到减少配置开销以及提高系统应用执行时间的目的,仿真结果表明了调度算法的有效性。4、为了实现将应用映射到可重构系统之中,本文重点研究可重构系统的软硬件划分问题。提出基于混沌优化算法的软硬件划分算法,该算法用DAG图描述应用,并对包括配置时间参数在内的任务信息进行了定义,结合混沌优化理论实现了面向可重构系统的软硬件划分,并对划分结果的评价使用了基于优先级链式调度算法。针对混沌优化算法存在的局限性,进一步提出基于最大熵原理与混沌优化动态融合的软硬件划分算法,该算法引入时间熵概念并运用最大熵原理,将系统时间熵作为搜索最优解的第二判据,实现对劣解的选择性接受机制。此外,针对二次载波不完整问题,提出位跳变方法,采用对优化变量只改变某一位取值的方法,以扩大算法搜索范围。算法性能对比实验结果表明,与原有算法相比,在算法搜索能力和全局收敛速度方面均有所改善。更多还原

【Abstract】 As the emergence of large scale high performance programmable logic devices and the improvement of electronic design automation technology, reconfigurable computing has become an active research area of system architecture. Reconfigurable computing(RC) takes advantages of high performance by performing computation on hardware, and flexibility by software solution. However, traditional operating systems rarely support the application demands of reconfigurable computing system; such demands are how to abstract and manage the reconfigurable computation resources and how to provide a unified software/hardware programming model for any tasks. Therefore, research on operating system of RC still faces many problems to be solved.This dissertation focuses on reconfigurable resource management, task scheduling, reconfiguration, partitioning algorithms of software/hardware, and the other issues. The dissertation mainly consists of the following several parts of contr(?)ution.(1) A graph-based FPGA resource management method is proposed to solve the problem of free reconfigurable resource. The hardware tasks are expressed as rectangles. Two-dimensional model is applied as research object. Undirected graph and FPGA regional model are combined in and organized way. With the analysis of the mapping relation between undirected graph and FPGA regional model, the maximum set of empty rectangles is computed from the virtual undirected graph. The problem of finding maximum empty rectangles is transform into the problem of finding the available loop and pathway in virtual undirected graph, which simplifies the partitioning process of free region very much. Simulation results showed feasibility of the proposed algorithm.(2) The method of how to reduce reconfigurable disposition overhead is studied in this dissertation aiming to decrease the time delay introduced by dynamic partial reconfiguration process. Configuration prefetching strategy is an efficient way to accelerate or hide reconfiguration process by overlapping the execution time of configuration and applications. And there are hardware tasks which are running concurrently in a computing system. Considering of the idea of configuration prefetching, a solution that constructs configuration prefetching queue according to the order of tasks scheduling is proposed. The solution, which is oriented the DAG-based task model, makes the configuration tasks execute in optimal order, so that the configuration tasks are taken into account to the demand of computation tasks.(3) A chained scheduling algorithm with pre-configuration is proposed. Task scheduling algorithm is a standard evaluation of software/hardware task partitioning scheme. Task scheduling algorithm oriented reconfigurable system needs to consider the reconfiguration delay and concurrent execution of tasks. In order to reduce configuration overhead and accelerate system execution, the computation tasks and configuration tasks are overlapped as much as possible by task scheduling based on critical path and computation overhead. Simulation results showed the effectiveness of the proposed scheduling algorithm.(4) Software/hardware partitioning algorithm is proposed based on Chaos optimization algorithm. In order to map the applications to the reconfigurable system, DAG map is used to describe the applications, and chaotic optimization theory is introduced. The results of partitioning process are evaluated by the priority chained scheduling algorithm.Software/hardware partitioning algorithm based on dynamic combination of maximum entropy and Chaos optimization is propose to overcome the limitations of the former algorithm. The concept of time entropy is introduced and the maximum entropy theory is applied. Time entropy is regarded as the second criterion in the search process of the optimization solution. The mechanism of selective acceptance of inferior solutions is described. In addition, bit reverse method is proposed for second carrier incomplete. Only one bit of optimized variable is reversed to expand the search space of the algorithm. Simulation results showed that the search capability and global convergence of the proposed algorithm were better than the original algorithm.更多还原