Loading [MathJax]/extensions/MathMenu.js
Counting Priority Inversions: Computing Maximum Additional Core Requests of DAG Tasks | IEEE Conference Publication | IEEE Xplore

Counting Priority Inversions: Computing Maximum Additional Core Requests of DAG Tasks


Abstract:

Many parallel real-time applications can be modeled as DAG tasks. Guaranteeing timing constraints of such applications executed on multicore systems is challenging, espec...Show More

Abstract:

Many parallel real-time applications can be modeled as DAG tasks. Guaranteeing timing constraints of such applications executed on multicore systems is challenging, especially for the applications with non-preemptive execution blocks. The existing approach for timing analysis of such tasks with sporadic release relies on computing a bound on the interfering workload on a task, which depends on the number of priority inversions the task may experience. The number of priority inversions, in turn, is a function of the total number of additional cores a task instance may request after each node spawning. In this paper, we show that the previously proposed polynomial-time algorithm to compute the maximum number of additional core requests of a DAG is not correct, providing a counter example. We show that the problem is in fact NP-hard. We then present an ILP formulation as an exact solution to the problem. Our evaluations show that the problem can be solved in a few minutes even for DAGs with hundreds of nodes.
Date of Conference: 14-23 March 2022
Date Added to IEEE Xplore: 19 May 2022
ISBN Information:

ISSN Information:

Conference Location: Antwerp, Belgium

I. Introduction

Multicore processors are increasingly employed in real-time applications. The workload of many real-time software running on multicore chips can be naturally modeled as directed acyclic graphs (DAG), where nodes represent sequential computation units, also called subtasks, and edges represent functional dependencies between subtasks. OpenMP [6] programs, robotic software running on ROS [3], and automotive task chains [10] are instances of such applications.

References

References is not available for this document.