Spatio-Temporal Scheduling of Preemptive Real-Time Tasks on Partially Reconfigurable Systems

Sangeet Saha, Arnab Sarkar, Amlan Chakrabarti

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


Reconfigurable devices that promise to offer the twin benefits of flexibility as in general-purpose processors along with the efficiency of dedicated hardwares often provide a lucrative solution for many of today's highly complex real-time embedded systems. However, online scheduling of dynamic hard real-time tasks on such systems with efficient resource utilization in terms of both space and time poses an enormously challenging problem. We attempt to solve this problem using a combined offline-online approach. The offline component generates and stores various optional feasible placement solutions for different sub-sets of tasks that may possibly be co-mapped together. Given a set of periodic preemptive real-time tasks that requires to be executed at runtime, the online scheduler first carries out an admission control procedure and then produces a schedule, which is guaranteed to meet all timing constraints provided it is spatially feasible to place designated subsets of these tasks at specified scheduling points within a future time interval. These feasibility checks are done and actual placement solutions are obtained through a low overhead search of the statically precomputed placement solutions. Based on this approach, we have proposed a periodic preemptive real-time scheduling methodology for runtime partially reconfigurable devices. Effectiveness of the proposed strategy has been verified through simulation based experiments and we observed that the strategy achieves high resource utilization with low task rejection rates over various simulation scenarios.

Original languageEnglish
Article number71
Number of pages26
JournalACM Transactions on Design Automation of Electronic Systems
Issue number4
Early online date13 Jun 2017
Publication statusPublished - 1 Oct 2017
Externally publishedYes


Dive into the research topics of 'Spatio-Temporal Scheduling of Preemptive Real-Time Tasks on Partially Reconfigurable Systems'. Together they form a unique fingerprint.

Cite this