Optimal Scheduling of Precedence-constrained Task Graphs on Heterogeneous Distributed Systems with Shared Buses

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. However, existing research works dealing with the optimal scheduling of PTGs, typically assume platforms consisting of homogeneous processing elements which interact through a fully connected network of homogeneous communication channels. In this work, we propose an Integer Linear Programming based optimal solution strategy for scheduling PTGs executing on a distributed platform composed of heterogeneous processing elements and inter-connected through a set of heterogeneous shared buses. 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 generic applicability. Conducted experiments on benchmark PTGs reveal the practical efficacy of our scheme.

I. Introduction

Applications in many time-critical cyber-physical systems, ranging from avionic, automotive and industrial control to telecommunication systems, health care and even a significant class of consumer electronic systems, are often represented as real-time Precedence-constrained Task Graphs (PTGs). Vertices in a PTG denote either the (sub)tasks or messages of the application and edges represent inter-task dependencies [21]. Traditionally, these systems have been implemented on homogeneous multi-core platforms. However, due to continuous demands for higher performance and reliability along with better thermal and power efficiencies, there is an increasing trend towards their implementation on complex distributed platforms consisting of heterogeneous processing elements (CPUs, DSPs, ASICs etc.) and shared buses (CAN, LIN, FlexRay etc.) [8]. For example, a modern automotive system such as the BMW-7 series, contains more than 70 processing elements (also known as ECUs) and are connected by heterogeneous shared bus networks consisting of High Speed-CAN (500 kbps), Low Speed CAN (100 kbps), FlexRay (10 Mbps), Media Oriented Systems Transport (MOST) and Ethernet [26].