PRESTO: A Penalty-Aware Real-Time Scheduler for Task Graphs on Heterogeneous Platforms
Debabrata Senapati, Arnab Sarkar, Chandan Karfa · IEEE Transactions on Computers · 2021
Scheduling real-time applications modelled as directed acyclic graphs on heterogeneous distributed platforms is known to be a challenging as well as a computationally demanding problem. This article deals with the design of an efficient scheduler for executing a real-time task graph on a distributed platform consisting of a set of fully connected heterogeneous processors. The objective of the scheduling strategy is to minimize ageneric penalty functionwhich can be amicably adopted toward its deployment in various application domains such as real-time embedded systems, cloud/fog computing, industrial automation and IoTs, smart grids, automotive and avionic systems, etc. We have first encoded the problem as a constraint satisfaction problem and then developed an efficient list-based heuristic scheduling algorithm calledPenalty-aware REal-time Scheduler for Task graphs on heterOgeneous platforms(PRESTO), to generate a minimal penalty deadline-meeting static schedule. The generic efficacy ofPRESTOis exhibited through extensive simulation-based experiments using standard benchmark task graphs. The practical applicability ofPRESTOin diverse scenarios have further been exhibited by using the scheme in two different real-world case studies, the first of which relates to automotive embedded systems, while the second is in the domain of fog computing.