The federated scheduling of systems of conditional sporadic DAG tasks

Sanjoy Baruah

doi:10.1109/EMSOFT.2015.7318254

The federated scheduling of systems of conditional sporadic DAG tasks

Sanjoy Baruah

Department of Computer Science & Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

76 Scopus citations

Abstract

A federated approach to the multiprocessor scheduling of systems of independent recurrent tasks is considered, in which each task is either restricted to execute preemptively upon a single processor, or may execute upon multiple processors but gets exclusive access to all these processors. Efficient polynomial-time algorithms are derived here for the federated schedulability analysis and run-time scheduling of re-current task systems that are represented by the conditional sporadic DAG tasks model. The performance of these algorithms is characterized via a speedup factor metric, which quanti es the combined cost of both restricting oneself to the federated scheduling paradigm, and of requiring the scheduling algorithms to run in polynomial time.

Original language	English
Title of host publication	2015 Proceedings of the International Conference on Embedded Software, EMSOFT 2015
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1-10
Number of pages	10
ISBN (Electronic)	9781467380799
DOIs	https://doi.org/10.1109/EMSOFT.2015.7318254
State	Published - Nov 4 2015
Event	13th International Conference on Embedded Software, EMSOFT 2015 - Amsterdam, Netherlands Duration: Oct 4 2015 → Oct 9 2015

Publication series

Name	2015 Proceedings of the International Conference on Embedded Software, EMSOFT 2015

Conference

Conference	13th International Conference on Embedded Software, EMSOFT 2015
Country/Territory	Netherlands
City	Amsterdam
Period	10/4/15 → 10/9/15

Keywords

conditional constructs
constrained deadline
federated scheduling
Intra-task parallelism
sporadic DAG tasks

Access to Document

10.1109/EMSOFT.2015.7318254

Cite this

Baruah, S. (2015). The federated scheduling of systems of conditional sporadic DAG tasks. In 2015 Proceedings of the International Conference on Embedded Software, EMSOFT 2015 (pp. 1-10). Article 7318254 (2015 Proceedings of the International Conference on Embedded Software, EMSOFT 2015). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/EMSOFT.2015.7318254

@inproceedings{02b09f889f7543829cc2cb130644a3f1,

title = "The federated scheduling of systems of conditional sporadic DAG tasks",

abstract = "A federated approach to the multiprocessor scheduling of systems of independent recurrent tasks is considered, in which each task is either restricted to execute preemptively upon a single processor, or may execute upon multiple processors but gets exclusive access to all these processors. Efficient polynomial-time algorithms are derived here for the federated schedulability analysis and run-time scheduling of re-current task systems that are represented by the conditional sporadic DAG tasks model. The performance of these algorithms is characterized via a speedup factor metric, which quanti es the combined cost of both restricting oneself to the federated scheduling paradigm, and of requiring the scheduling algorithms to run in polynomial time.",

keywords = "conditional constructs, constrained deadline, federated scheduling, Intra-task parallelism, sporadic DAG tasks",

author = "Sanjoy Baruah",

note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 13th International Conference on Embedded Software, EMSOFT 2015 ; Conference date: 04-10-2015 Through 09-10-2015",

year = "2015",

month = nov,

day = "4",

doi = "10.1109/EMSOFT.2015.7318254",

language = "English",

series = "2015 Proceedings of the International Conference on Embedded Software, EMSOFT 2015",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1--10",

booktitle = "2015 Proceedings of the International Conference on Embedded Software, EMSOFT 2015",

}

Baruah, S 2015, The federated scheduling of systems of conditional sporadic DAG tasks. in 2015 Proceedings of the International Conference on Embedded Software, EMSOFT 2015., 7318254, 2015 Proceedings of the International Conference on Embedded Software, EMSOFT 2015, Institute of Electrical and Electronics Engineers Inc., pp. 1-10, 13th International Conference on Embedded Software, EMSOFT 2015, Amsterdam, Netherlands, 10/4/15. https://doi.org/10.1109/EMSOFT.2015.7318254

The federated scheduling of systems of conditional sporadic DAG tasks. / Baruah, Sanjoy.
2015 Proceedings of the International Conference on Embedded Software, EMSOFT 2015. Institute of Electrical and Electronics Engineers Inc., 2015. p. 1-10 7318254 (2015 Proceedings of the International Conference on Embedded Software, EMSOFT 2015).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - The federated scheduling of systems of conditional sporadic DAG tasks

AU - Baruah, Sanjoy

PY - 2015/11/4

Y1 - 2015/11/4

N2 - A federated approach to the multiprocessor scheduling of systems of independent recurrent tasks is considered, in which each task is either restricted to execute preemptively upon a single processor, or may execute upon multiple processors but gets exclusive access to all these processors. Efficient polynomial-time algorithms are derived here for the federated schedulability analysis and run-time scheduling of re-current task systems that are represented by the conditional sporadic DAG tasks model. The performance of these algorithms is characterized via a speedup factor metric, which quanti es the combined cost of both restricting oneself to the federated scheduling paradigm, and of requiring the scheduling algorithms to run in polynomial time.

AB - A federated approach to the multiprocessor scheduling of systems of independent recurrent tasks is considered, in which each task is either restricted to execute preemptively upon a single processor, or may execute upon multiple processors but gets exclusive access to all these processors. Efficient polynomial-time algorithms are derived here for the federated schedulability analysis and run-time scheduling of re-current task systems that are represented by the conditional sporadic DAG tasks model. The performance of these algorithms is characterized via a speedup factor metric, which quanti es the combined cost of both restricting oneself to the federated scheduling paradigm, and of requiring the scheduling algorithms to run in polynomial time.

KW - conditional constructs

KW - constrained deadline

KW - federated scheduling

KW - Intra-task parallelism

KW - sporadic DAG tasks

UR - https://www.scopus.com/pages/publications/84962268648

U2 - 10.1109/EMSOFT.2015.7318254

DO - 10.1109/EMSOFT.2015.7318254

M3 - Conference contribution

AN - SCOPUS:84962268648

T3 - 2015 Proceedings of the International Conference on Embedded Software, EMSOFT 2015

SP - 1

EP - 10

BT - 2015 Proceedings of the International Conference on Embedded Software, EMSOFT 2015

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 13th International Conference on Embedded Software, EMSOFT 2015

Y2 - 4 October 2015 through 9 October 2015

ER -

The federated scheduling of systems of conditional sporadic DAG tasks

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this