SLAQA: Quality-level Aware Scheduling of Task Graphs on Heterogeneous Distributed Systems

Continuous demands for higher performance and reliability within stringent resource budgets is driving a shift from homogeneous to heterogeneous processing platforms for the implementation of today's cyber-physical systems (CPSs). These CPSs are typically represented as Directed-acyclic Task Graph (DTG) due to the complex interactions between their functional components that are often distributed in nature. In this article, we consider the problem of scheduling a real-time application modelled as a single DTG, where tasks may have multiple implementations designated as quality-levels, with higher quality-levels producing more accurate results and contributing to higher rewards/Quality-of-Service for the system. First, we introduce an optimal solution using Integer Linear Programming (ILP) for a DTG with multiple quality-levels, to be executed on a heterogeneous distributed platform. However, this ILP-based optimal solution exhibits high computational complexity and does not scale for moderately large problem sizes. Hence, we propose two low-overhead heuristic algorithms called Global Slack Aware Quality-level Allocator (G-SLAQA) and Total Slack Aware Quality-level Allocator (T-SLAQA), which are able to produce satisfactorily efficient as well as fast solutions within a reasonable time. G-SLAQA, the baseline heuristic, is greedier and faster than its counter-part T-SLAQA, whose performance is at least as efficient as G-SLAQA. The efficiency of all the proposed schemes have been extensively evaluated through simulation-based experiments using benchmark and randomly generated DTGs. Through the case study of a real-world automotive traction controller, we generate schedules using our proposed schemes to demonstrate their practical applicability.

Automated summary

The shift towards heterogeneous processing platforms for cyber-physical systems is driven by the need for higher performance within resource constraints. The article proposes two low-overhead heuristic algorithms to efficiently schedule real-time applications modeled as Directed-acyclic Task Graphs with multiple quality-level tasks, providing faster solutions compared to an optimal solution based on Integer Linear Programming.