Optimal Scheduling of PTGs with Multiple Service Levels on Heterogeneous Distributed Systems
Sanjit Kumar Roy, Rajesh Devaraj, Arnab Sarkar · 2019
Real-time applications in today's distributed cyber-physical control systems are often represented as Precedence-constrained Task Graphs (PTGs) and increasingly implemented on heterogeneous platforms to cater to their high performance demands. Optimal scheduling solutions for such systems can provide advantages in terms of performance, reliability, cost etc. This paper addresses the problem of scheduling a real-time application modelled as PTG where tasks have multiple optional service levels (where higher service level implies higher Quality-of-Service (QoS)). In particular, we propose an Integer Linear Programming based optimal solution strategy for scheduling PTGs with multiple service levels, executing on a distributed platform composed of heterogeneous processing elements. Through the real-world case study of an automotive cruise controller, we generate an optimal schedule using our scheme in order to demonstrate its applicability. Conducted simulation based experiments and comparison with a state-of-the-art approach, reveal the practical efficacy of our scheme.