A generalized parallel task model for recurrent real-time processes

Vincenzo Bonifaci, Andreas Wiese, Sanjoy K. Baruah, Alberto Marchetti-Spaccamela, Sebastian Stiller, Leen Stougie

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

A model is considered for representing recurrent precedence-constrained tasks that are to execute on multiprocessor platforms. A recurrent task is specified as a directed acyclic graph (DAG), a period, and a relative deadline. Each vertex of the DAG represents a sequential job, while the edges of the DAG represent precedence constraints between these jobs. All the jobs of the DAG are released simultaneously and need to complete execution within the specified relative deadline of their release. Each task may release jobs in this manner an unbounded number of times, with successive releases occurring at least the specified period apart. Conditional control structures are also allowed. The scheduling problem is to determine whether a set of such recurrent tasks can be scheduled to always meet all deadlines upon a specified number of identical processors. This problem is shown to be computationally intractable, but amenable to efficient approximate solutions. Earliest Deadline First (EDF) and Deadline Monotonic (DM) are shown to be good approximate global scheduling algorithms. Polynomial and pseudo-polynomial time schedulability tests, of differing effectiveness, are presented for determining whether a given task set can be scheduled by EDF or DM to always meet deadlines on a specified number of processors.

Original languageEnglish
Article number3
JournalACM Transactions on Parallel Computing
Volume6
Issue number1
DOIs
Publication statusPublished - 1 May 2019

Fingerprint

Task Model
Deadline
Directed Acyclic Graph
Polynomials
Real-time
Scheduling algorithms
Earliest Deadline First
Scheduling
Monotonic
Precedence Constraints
Multiprocessor
Scheduling Algorithm
Scheduling Problem
Polynomial time
Approximate Solution
Polynomial
Vertex of a graph

Keywords

  • Approximation algorithm
  • Conditional control-flow
  • Directed acyclic graph
  • Multiprocessor platform
  • Precedence constraints
  • Schedulability test

Cite this

Bonifaci, V., Wiese, A., Baruah, S. K., Marchetti-Spaccamela, A., Stiller, S., & Stougie, L. (2019). A generalized parallel task model for recurrent real-time processes. ACM Transactions on Parallel Computing, 6(1), [3]. https://doi.org/10.1145/3322809
Bonifaci, Vincenzo ; Wiese, Andreas ; Baruah, Sanjoy K. ; Marchetti-Spaccamela, Alberto ; Stiller, Sebastian ; Stougie, Leen. / A generalized parallel task model for recurrent real-time processes. In: ACM Transactions on Parallel Computing. 2019 ; Vol. 6, No. 1.
@article{d2fee36ffeb64263bffd42356ffea7c5,
title = "A generalized parallel task model for recurrent real-time processes",
abstract = "A model is considered for representing recurrent precedence-constrained tasks that are to execute on multiprocessor platforms. A recurrent task is specified as a directed acyclic graph (DAG), a period, and a relative deadline. Each vertex of the DAG represents a sequential job, while the edges of the DAG represent precedence constraints between these jobs. All the jobs of the DAG are released simultaneously and need to complete execution within the specified relative deadline of their release. Each task may release jobs in this manner an unbounded number of times, with successive releases occurring at least the specified period apart. Conditional control structures are also allowed. The scheduling problem is to determine whether a set of such recurrent tasks can be scheduled to always meet all deadlines upon a specified number of identical processors. This problem is shown to be computationally intractable, but amenable to efficient approximate solutions. Earliest Deadline First (EDF) and Deadline Monotonic (DM) are shown to be good approximate global scheduling algorithms. Polynomial and pseudo-polynomial time schedulability tests, of differing effectiveness, are presented for determining whether a given task set can be scheduled by EDF or DM to always meet deadlines on a specified number of processors.",
keywords = "Approximation algorithm, Conditional control-flow, Directed acyclic graph, Multiprocessor platform, Precedence constraints, Schedulability test",
author = "Vincenzo Bonifaci and Andreas Wiese and Baruah, {Sanjoy K.} and Alberto Marchetti-Spaccamela and Sebastian Stiller and Leen Stougie",
year = "2019",
month = "5",
day = "1",
doi = "10.1145/3322809",
language = "English",
volume = "6",
journal = "ACM Transactions on Parallel Computing",
issn = "2329-4949",
number = "1",

}

Bonifaci, V, Wiese, A, Baruah, SK, Marchetti-Spaccamela, A, Stiller, S & Stougie, L 2019, 'A generalized parallel task model for recurrent real-time processes' ACM Transactions on Parallel Computing, vol. 6, no. 1, 3. https://doi.org/10.1145/3322809

A generalized parallel task model for recurrent real-time processes. / Bonifaci, Vincenzo; Wiese, Andreas; Baruah, Sanjoy K.; Marchetti-Spaccamela, Alberto; Stiller, Sebastian; Stougie, Leen.

In: ACM Transactions on Parallel Computing, Vol. 6, No. 1, 3, 01.05.2019.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - A generalized parallel task model for recurrent real-time processes

AU - Bonifaci, Vincenzo

AU - Wiese, Andreas

AU - Baruah, Sanjoy K.

AU - Marchetti-Spaccamela, Alberto

AU - Stiller, Sebastian

AU - Stougie, Leen

PY - 2019/5/1

Y1 - 2019/5/1

N2 - A model is considered for representing recurrent precedence-constrained tasks that are to execute on multiprocessor platforms. A recurrent task is specified as a directed acyclic graph (DAG), a period, and a relative deadline. Each vertex of the DAG represents a sequential job, while the edges of the DAG represent precedence constraints between these jobs. All the jobs of the DAG are released simultaneously and need to complete execution within the specified relative deadline of their release. Each task may release jobs in this manner an unbounded number of times, with successive releases occurring at least the specified period apart. Conditional control structures are also allowed. The scheduling problem is to determine whether a set of such recurrent tasks can be scheduled to always meet all deadlines upon a specified number of identical processors. This problem is shown to be computationally intractable, but amenable to efficient approximate solutions. Earliest Deadline First (EDF) and Deadline Monotonic (DM) are shown to be good approximate global scheduling algorithms. Polynomial and pseudo-polynomial time schedulability tests, of differing effectiveness, are presented for determining whether a given task set can be scheduled by EDF or DM to always meet deadlines on a specified number of processors.

AB - A model is considered for representing recurrent precedence-constrained tasks that are to execute on multiprocessor platforms. A recurrent task is specified as a directed acyclic graph (DAG), a period, and a relative deadline. Each vertex of the DAG represents a sequential job, while the edges of the DAG represent precedence constraints between these jobs. All the jobs of the DAG are released simultaneously and need to complete execution within the specified relative deadline of their release. Each task may release jobs in this manner an unbounded number of times, with successive releases occurring at least the specified period apart. Conditional control structures are also allowed. The scheduling problem is to determine whether a set of such recurrent tasks can be scheduled to always meet all deadlines upon a specified number of identical processors. This problem is shown to be computationally intractable, but amenable to efficient approximate solutions. Earliest Deadline First (EDF) and Deadline Monotonic (DM) are shown to be good approximate global scheduling algorithms. Polynomial and pseudo-polynomial time schedulability tests, of differing effectiveness, are presented for determining whether a given task set can be scheduled by EDF or DM to always meet deadlines on a specified number of processors.

KW - Approximation algorithm

KW - Conditional control-flow

KW - Directed acyclic graph

KW - Multiprocessor platform

KW - Precedence constraints

KW - Schedulability test

UR - http://www.scopus.com/inward/record.url?scp=85068151584&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85068151584&partnerID=8YFLogxK

U2 - 10.1145/3322809

DO - 10.1145/3322809

M3 - Article

VL - 6

JO - ACM Transactions on Parallel Computing

JF - ACM Transactions on Parallel Computing

SN - 2329-4949

IS - 1

M1 - 3

ER -