Reconfigurable-System-Oriented Resources Management And Hardware/Software Partitioning Algorithm

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.