Research On Algorithms Of Online Placement And Scheduling Of Real-time Tasks For Reconfigurable System-on-chip

Reconfigurable computing technology combines the advantages of GPP(General-Purpose Processor) and ASIC(Application Specific Integrated Circuits), providing the hardware efficiency and software programmability in one platform. It is one of the hot topics of current computer research. As the most recent development of reconfigurable computing technology, dynamic partial reconfiguration can reconfigure a part of the reconfigurable logic device while other parts of the system continue to operate, enabling the parallel execution of running tasks and reconfigurations. It can efficiently utilize the reconfigurable resource and improve flexibility of the reconfigurable computing system.Managing the free resource on the chip and scheduling the hardware tasks online in dynamic reconfigurable system is one of the critical factors that is concerned closely with the performance of the dynamic reconfigurable computing system. In order to low the tasks rejection ratio, reduce the overall runtime and higher chip utilization, so it requires a high quality placement and scheduling algorithm to make the performance of the system optimization or nearly optimization.This paper focuses on the on-line placement and scheduling of real-time tasks on a two-dimensional reconfigurable device, the research of this thesis addresses all these aspects, in which the new contributions are:(1)A placement methodology on partially reconfigurable devices based on adjacent surface of the already running tasks. According to vertexes of the already running tasks, the algorithm selects the best vertex which has the maximum adjacent surface value from all the feasible placements to place the arrival tasks.(2)The Look-aheadest scheduling algorithm for dynamic reconfigurable computing based on the vertexes of placed tasks. After the new task arrival, it simulate the tasks beginning of the reservation list and the tasks ending of the execution list until the latest starting time, and get the vertex and starting time that have the maximum cost function value to schedule the arrival tasks, so it minimize the area fragmentation. The simulation results show that the proposed algorithm can achieve higher chip utilization and lower task rejection ratio. However, the runtime efficiency is acceptable.(3)Design a prototype system which supports the software/hardware transparent programming model, then implement a reconfigurable resource manager in a transplanting embedded Linux operating system. It can manage the dynamic configuration and running states of the hardware functions. Last after test the hardware function library of our project team, verify the correctness of the prototype system.