Optimal Scheduling of PTGs with Multiple Service Levels on Heterogeneous Distributed Systems

Sanjit Kumar Roy1, Rajesh Devaraj2, Arnab Sarkar2

  • 1Indian Institute of Technology Guwahati
  • 2IIT Guwahati

Details

10:20 - 10:40 | Wed 10 Jul | Franklin 5 | WeA05.2

Session: Optimization I

Abstract

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 proposed scheme in order to demonstrate its applicability. Conducted simulation based experiments and comparison with a state of art approach, reveal the practical efficacy of our scheme.