The Design And Implementation Of Placement And Task Scheduling Algorithms In Operating System For Reconfigurable System

With the development of integrated circuit technology, the capability of FPGA has achieved several millions of gates and the dynamic partial reconfigurable function of FPGA is also realized. The hybrid system composed of FPGA and instruction set processor has the advantages of high performance, flexible programmability and more extensive usage. In order to improve the utilization of FPGA and simplify the design flow, operating system must provide more support for the reconfigurable device.This thesis focuses on the placement and task scheduling algorithms for the resource and task management of the operating system that supports the reconfigurable computing system. Analysis and comparison are given on the Edmonds, MH and KVIT placement algorithms and the Horizon, Stuffing and MGS task scheduling algorithms in aspects of data structure and algorithm design method. Improvement is made on Stuffing algorithm, which forms the CStuffing algorithm. For the Match functions in the KVIT and MGS algorithms, a realization is given for different situations when new arrival task matches different number of vertexes with the already scheduled tasks. MH and KVIT placement algorithms and Stuffing, CStuffing and MGS task scheduling algorithms run on the experiment platform we built for comparing and verifying the result performance. The experimental results show that KVIT placement algorithm is a little better than MH placement algorithm in the execution time and task rejection ratio, but MH placement algorithm has advantage in the free space management and defragmentation; the execution time of CStuffing algorithm is a little less than that of Stuffing algorithm, and MGS task scheduling algorithm is a little better in the execution time, task rejection number and chip utilization, but the MGS algorithm has a high requirement on memory space.