Research On Reconfigurable Tasks Scheduling Algorithm Considering The Restriction Of FPGA Configuration Port

FPGA devices with Run-Time Partial Reconfiguration (RTPR) function, allow some parts of the FPGA's logical units running at the same time, other parts of the FPGA's logical units being configurated. RTPR technology not only makes multiple tasks be performed in parallel in the reconfigurable hardware device, but also help to improve resource utilization of the reconfigurable device. In reconfigurable system, the key to make full use of the reconfigurable resource and improve the performance is how to determine configuration time and switching time of the task. Through optimizing scheduling algorithm, the scheduling success rate of reconfigurable task and the reconfigurable resource utilization rate are increased, the overall run-time of the reconfigurable tasks set is reduced.Based on the sub-project"The Researching of Hardware Reconfigurable Technology"of the national 863 project"The Researching and Manufacture of Reconfigurable Router Components", this dissertation concentrates on the research of reconfigurable task scheduling algorithms considering the restriction of FPGA configuration port. The main work and contributions are outlined as follows:A Head-of-line Blocking Optimization Earliest Deadline First (HBO-EDF) scheduling algorithm for independent reconfigurable tasks is presented. By analyzing the phenomenon of head-of-line blocking, sufficient condition for distinguish invalid blocking task is given, the invalid blocking task drop strategy is introduced by defining the invalid blocking task to drop the tasks that can not be scheduled successfully in advance; the matching task and the second head task configuration bring forward strategy is introduced by defining the earliest successful placement time of head-of-line blocking task,so that the head task can still be scheduled successfully and part of the free reconfigurable resources and configuration port in head-of-line blocking process can be used effectively. Simulation results show that, HBO-EDF scheduling algorithm obtained a considerable improvement both in the task scheduling success rate and the reconfigurable resource using rate.A scheduling algorithm based on Configuration Completion First (CCF) for dependent reconfigurable tasks is presented. List scheduling based on pre-configuration is used to hide predecessor task's configuration time within the successor task's execution time; the configuration reuse mechanism based on configuration completion first is used to reduce the configuration process of the task which was scheduled, so that the whole run-time of the tasks set can be reduced. Simulation results show that, CCF scheduling algorithm can avoid deadlock scheduling and reduce the overall run-time of the tasks set effectively. A Preempted Based on Price (PBP) scheduling algorithm for the hybrid reconfigurable tasks which include both dependent tasks and independent tasks is presented. The equivalent running deadline of every task in the dependent reconfigurable tasks set was calculated to make the hybrid reconfigurable tasks be configurated according to configuration deadline. Considering the characteristic of dependent reconfigurable tasks, the dependent tasks set that can't be scheduled successfully was confirmed and dropped in advance according to the sufficient condition for deciding failing schedule of dependent reconfigurable task set; the limited pre-configuration avoids the dependent tasks occuping reconfigurable resources too earlier than it can start running time; the preempted based on price was used to reduce the number of scheduling failed tasks. Simulation results show that, PBP scheduling algorithm can increase the task scheduling success rate.