Study And Implementation Of Scheduling Algorithm For Real-Time Tasks On Reconfigurable Systems

With the fast development of FPGA (Field Programmable Gate Arrays) devices, a novel technique Dynamic Partial Reconfiguration (DPR) based on FPGA is paid more and more attention by the academia. Reconfigurable technology changes the traditional design method of embedded systems, and takes into account both system performance and design flexibility.Taking advantage of DPR, a reconfigurable system can independently configure a portion of specific computing resources in reconfigurable devices without affecting the execution of other parts. This allows hardware tasks to be placed and removed dynamically at runtime in multi-tasking systems, thus, greatly improves the overall performance of system and gains better area resource utilization. The thesis research details reconfigurable system by three aspects:basic hardware device or FPGA, system model, operating system.Real-time multi-tasking systems not only need to support sharing of the resources in space, but also need to guarantee timely execution of the tasks. The thesis study deeply about the algorithm of placer and scheduler for reconfigurable system, and solves the on-line real-time task placement and scheduling problems in 2D area model. By means of the concept Reject Region, a novel and efficient placement strategy is proposed which achieves denser task placement and reserves more continuous free area. Then, the thesis presents a scheduling approach with two phases.In first phase, through the proper combination of the task placement strategy, directly allocate the task to the Reconfigurable Resource (RC). In second phase, it tries to schedule an incoming task by introducing arrangement of reserved list. As shown in our simulation experiments, our proposed approach has rather high task accept ratio and average area utilization ratio.The thesis concludes in the final part, and prospects the work and research issues in future.