Research On Operating System Support For Reconfigurable Computing

Reconfigurable computing has been accepted as vehicles for both achieving potentially much higher performance than software and maintaining a higher level of flexibility than hardware. The convenient development for such a system requires abstraction from platform details and the management of the system resources. These two major requirements, abstraction and resource management, are usually provided by an operating system (OS). It is important to do some research on operating system support for reconfigurable computing (RC). This paper presents an design approach of OS for RC and following is what we have done.Firstly, after a simple review of reconfigurable computing's history, this paper classified current modern reconfigurable computing systems into several groups. The methods for reconfiguration and to reduce configuration time are also summarized in chapter 2. Then, we introduced island-style model and design flow of FPGA.Secondly, based on the essential differences between software-tasks and hardware-tasks, this paper presents and implements a RTOS for reconfigurable systems using uniform multi-task model, called SHUM-UCOS (Software-Tasks Hardware-Tasks Uniform Management UCOS), which is designed with the UCOSII as prototype. This RTOS traces and manages the usage of re-configurable resources (FPGAs), and can improve the utilization of these resources and the parallelism of the tasks with the hardware-tasks preconfiguration. And it has been proved by experiments that SHUM-UCOS can shorten the migration time from software implements to hardware implements with the performance improvement.Thirdly, we presents a DAG (Directed acyclic Graphs) partitioning algorithm for reconfigurable computing, called LSCBP (Level Sensitive cluster-base Partitioning) Algorithm, which partitions the whole task graph into small segments and keeps task precedence relations under area constraints. The proposed heuristic function AS_Level can denote allocation priorities of the ready list and will be adjusted during the partition process. The heuristic function is constructed with the guideline of "dependence first", "earliest time first" and "fragment reuse". The proposed algorithm can overcome the drawback of CBP algorithm and its time complexity increases to O{| V |~2 + |E |}. For the same DAGs, the experiment results on random DAGs show that LSCBP algorithm can get less task-clusters (meaning less requirements for reconfigurable devices) and inter-cluster edges (meaning less communication costs) than BCP algorithm.Fourthly, to solve the hardware-task temporal partitioning problem under node area and communication cost constraints in the reconfigurable computing, we proposed a probabilistic constructive genetic algorithm (PCGA) to obtain better tradeoff between the solution quality and algorithm's run time. The fundamental idea is to combine the merits of probabilistic constructive optimization technology (PCOT) and genetic algorithm: It use the PCOT to construct different acceptable problem solutions fast, and then use the global search ability of genetic algorithm to improve the final solution quality with these solutions as GA's initial population. To ensure the diversity of the initial population, a method of measuring the diversity between different solutions has been proposed. Experimental results on random task graphs with 20-200 nods show the PCGA generates better solutions than list methods; for the same solution quality, the PCGA hase short execution time and it is discovered that the bigger the size of partitioning problem is, the better the PCGA performs.Finally, To fully utilize reconfigurable devices with dynamically reconfigurable ability, it is vital for scheduler to find appropriate places for hardware tasks fast and to configure them. We propose an on-line scheduling for reconfigurable real-time tasks, called FORS (Fast On-line Real-time Scheduling). The algorithm adopts the scheduling principle of earliest latest staring time first, which will reflect different emergency levels of real time tasks. The algorithm constructs a fast and correct empty resource management and is based on configuration reuse. The experiments show that the developed scheduler can lead to great performance gains.