ATB: Area-Time response Balancing algorithm for scheduling real-time hardware tasks

This paper describes a novel scheduling algorithm for the execution of hardware tasks with real-time constraints onto partially and dynamically reconfigurable FPGAs. The Area-Time response Balancing scheduling algorithm (ATB) is inspired by the well-known Earliest Deadline First (EDF) algorithm, which is extended with a technique for reducing the fragmentation on FPGA´s reconfigurable area. This technique promotes the reuse of the resources that are released when great area tasks finish their execution by smaller area tasks as long as the real-time constraints permit to do so. Providing an exclusively time-based algorithm, such as EDF, with support for dealing with area-related issues ensures the best results. Simulation results reported in this paper show that ATB misses 23% less deadlines than EDF. Moreover, since FPGA´s damaged resources provoke unpredictable fragmentation on the device, ATB is currently the best scheduling option to be used in a Reliable Reconfigurable Real-Time Operating System (R3TOS).