Loading [MathJax]/extensions/MathMenu.js
Timing-Anomaly Free Dynamic Scheduling of Periodic DAG Tasks with Non-Preemptive Nodes | IEEE Conference Publication | IEEE Xplore

Timing-Anomaly Free Dynamic Scheduling of Periodic DAG Tasks with Non-Preemptive Nodes


Abstract:

Designing timing-anomaly free multiprocessor scheduling algorithms is a notoriously hard problem, especially for parallel tasks with non-preemptive execution regions. In ...Show More

Abstract:

Designing timing-anomaly free multiprocessor scheduling algorithms is a notoriously hard problem, especially for parallel tasks with non-preemptive execution regions. In this paper, we first propose a simple yet expressive model which abstracts a parallel task as a single computation unit, and then, present a sufficient condition for timing-anomaly free scheduling of such units. On top of this, we design an algorithm for scheduling a set of periodic parallel tasks, represented as DAG with non-preemptive subtasks, on multicore processors. The algorithm has several desirable properties, including timing-anomaly freedom, high resource utilization, and low memory requirement. Timing-anomaly freedom enables an exact schedulability test for the algorithm, which, as shown in our evaluations, provides a significantly high schedulability ratio compared to those state-of-the-art methods that suffer from timing anomalies.
Date of Conference: 18-20 August 2021
Date Added to IEEE Xplore: 27 September 2021
ISBN Information:

ISSN Information:

Conference Location: Houston, TX, USA

I. Introduction

With the end of Moore’s Law, the computer world has been rapidly developing in the direction of multi-core systems. Modern applications have to support parallel execution in order to exploit the computational resources provided by multicore systems thoroughly. Many parallel applications, such as OpenMP [11], and robotic software executed on ROS [10], can be naturally modeled as directed acyclic graphs (DAGs), in which nodes represent sequential execution units, also called subtasks, and edges represent precedence constraints between subtasks. Branches in a DAG characterize the parallelism in applications. Researchers have proposed various real-time scheduling algorithms and schedulability analysis methods for DAG-based task models.

References

References is not available for this document.