Formal and Heuristic Approaches to Real-time Scheduling on Reconfigurable Systems

Abstract

The dynamic partial reconfiguration (DPR) feature offered by modern FPGAs provides the flexibility of adapting the underlying hardware according to the needs of a particular situation during the runtime in response to application requirements. DPR has allowed the possibility of scheduling multiple real-time applications over both space and time so that the computation capacity of the FPGA floor may be efficiently harnessed. The scheduler generated/developed for the real-time tasks on FPGAs must not only handle all timing constraints, dependency constraints (if there is one), and FPGA based placement constraints but also correctly account for reconfiguration overheads involved in loading task bit streams onto the configuration memory of the FPGA through the ICAP port. Hence, static o_-line schedulers are often preferred for such a system in order to satisfy all these necessary constraints. In addition, o_-line computation also allows exhaustive solution space enumeration to pre-compute optimal schedules at design time, thus ensuring lower design costs through higher resource utilization. This thesis thus endeavors towards the exploration of new approaches and design of scheduling strategies for real-time tasks on partially reconfigurable platforms. Particularly, we present three static offline scheduler design approaches for reconfigurable systems: (i) a formal scheduler synthesis framework for the real-time tasks executing on an FPGA platform, using supervisory control of timed discrete event systems as the underlying formalism. (ii) an ILP based solution strategy for scheduling persistent real-time applications represented as precedence constrained task graphs on partially reconfigurable FPGAs and (iii) a heuristic solution methodology for scheduling persistent realtime applications represented as precedence constrained task graphs on partially reconfigurable FPGAs.