Global EDF-Based Scheduling of Multiple Independent Synchronous Dataflow Graphs

Abhishek Singh; Sanjoy Baruah

doi:10.1109/RTSS.2017.00036

Global EDF-Based Scheduling of Multiple Independent Synchronous Dataflow Graphs

Abhishek Singh
, Sanjoy Baruah

Department of Computer Science & Engineering

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

6 Scopus citations

Abstract

The global scheduling of systems that can be modeled as collections of multiple independent recurrent real-time tasks, each represented as a synchronous dataflow graph (SDFG), upon an identical multiprocessor platform is considered. An EDF-based scheduling algorithm is proved optimal under the speedup factor metric, and a speedup-optimal sufficient schedulability test is derived.

Original language	English
Title of host publication	Proceedings - 2017 IEEE Real-Time Systems Symposium, RTSS 2017
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	307-318
Number of pages	12
ISBN (Electronic)	9781538614143
DOIs	https://doi.org/10.1109/RTSS.2017.00036
State	Published - Jul 2 2017
Event	38th IEEE Real-Time Systems Symposium, RTSS 2017 - Paris, France Duration: Oct 5 2017 → Oct 8 2017

Publication series

Name	Proceedings - Real-Time Systems Symposium
Volume	2018-January
ISSN (Print)	1052-8725

Conference

Conference	38th IEEE Real-Time Systems Symposium, RTSS 2017
Country/Territory	France
City	Paris
Period	10/5/17 → 10/8/17

Keywords

constrained-deadline recurrent tasks
global multiprocessor scheduling
pseudo-polynomial time schedulability analysis
SDF Graphs
speedup-optimal scheduling

Access to Document

10.1109/RTSS.2017.00036

Cite this

@inproceedings{a2e0bc5bce9e489da22874e38d9589d4,

title = "Global EDF-Based Scheduling of Multiple Independent Synchronous Dataflow Graphs",

abstract = "The global scheduling of systems that can be modeled as collections of multiple independent recurrent real-time tasks, each represented as a synchronous dataflow graph (SDFG), upon an identical multiprocessor platform is considered. An EDF-based scheduling algorithm is proved optimal under the speedup factor metric, and a speedup-optimal sufficient schedulability test is derived.",

keywords = "constrained-deadline recurrent tasks, global multiprocessor scheduling, pseudo-polynomial time schedulability analysis, SDF Graphs, speedup-optimal scheduling",

author = "Abhishek Singh and Sanjoy Baruah",

note = "Publisher Copyright: {\textcopyright} 2017 IEEE.; 38th IEEE Real-Time Systems Symposium, RTSS 2017 ; Conference date: 05-10-2017 Through 08-10-2017",

year = "2017",

month = jul,

day = "2",

doi = "10.1109/RTSS.2017.00036",

language = "English",

series = "Proceedings - Real-Time Systems Symposium",

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

pages = "307--318",

booktitle = "Proceedings - 2017 IEEE Real-Time Systems Symposium, RTSS 2017",

}

Singh, A & Baruah, S 2017, Global EDF-Based Scheduling of Multiple Independent Synchronous Dataflow Graphs. in Proceedings - 2017 IEEE Real-Time Systems Symposium, RTSS 2017. Proceedings - Real-Time Systems Symposium, vol. 2018-January, Institute of Electrical and Electronics Engineers Inc., pp. 307-318, 38th IEEE Real-Time Systems Symposium, RTSS 2017, Paris, France, 10/5/17. https://doi.org/10.1109/RTSS.2017.00036

Global EDF-Based Scheduling of Multiple Independent Synchronous Dataflow Graphs. / Singh, Abhishek; Baruah, Sanjoy.
Proceedings - 2017 IEEE Real-Time Systems Symposium, RTSS 2017. Institute of Electrical and Electronics Engineers Inc., 2017. p. 307-318 (Proceedings - Real-Time Systems Symposium; Vol. 2018-January).

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

TY - GEN

T1 - Global EDF-Based Scheduling of Multiple Independent Synchronous Dataflow Graphs

AU - Singh, Abhishek

AU - Baruah, Sanjoy

PY - 2017/7/2

Y1 - 2017/7/2

N2 - The global scheduling of systems that can be modeled as collections of multiple independent recurrent real-time tasks, each represented as a synchronous dataflow graph (SDFG), upon an identical multiprocessor platform is considered. An EDF-based scheduling algorithm is proved optimal under the speedup factor metric, and a speedup-optimal sufficient schedulability test is derived.

AB - The global scheduling of systems that can be modeled as collections of multiple independent recurrent real-time tasks, each represented as a synchronous dataflow graph (SDFG), upon an identical multiprocessor platform is considered. An EDF-based scheduling algorithm is proved optimal under the speedup factor metric, and a speedup-optimal sufficient schedulability test is derived.

KW - constrained-deadline recurrent tasks

KW - global multiprocessor scheduling

KW - pseudo-polynomial time schedulability analysis

KW - SDF Graphs

KW - speedup-optimal scheduling

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

U2 - 10.1109/RTSS.2017.00036

DO - 10.1109/RTSS.2017.00036

M3 - Conference contribution

AN - SCOPUS:85046361044

T3 - Proceedings - Real-Time Systems Symposium

SP - 307

EP - 318

BT - Proceedings - 2017 IEEE Real-Time Systems Symposium, RTSS 2017

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 38th IEEE Real-Time Systems Symposium, RTSS 2017

Y2 - 5 October 2017 through 8 October 2017

ER -

Global EDF-Based Scheduling of Multiple Independent Synchronous Dataflow Graphs

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this