Partitioned EDF scheduling on a few types of unrelated multiprocessors

Andreas Wiese; Vincenzo Bonifaci; Sanjoy Baruah

doi:10.1007/s11241-012-9164-y

Partitioned EDF scheduling on a few types of unrelated multiprocessors

Andreas Wiese
, Vincenzo Bonifaci
, Sanjoy Baruah

Universita La Sapienza
IMM-CNR
University of North Carolina

Research output: Contribution to journal › Article › peer-review

19 Scopus citations

Abstract

A polynomial-time approximation scheme (PTAS) is derived for the partitioned EDF scheduling of implicit-deadline sporadic task systems upon unrelated multiprocessor platforms that are comprised of a constant number of distinct types of processors. This generalizes earlier results showing the existence of polynomial-time approximation schemes for the partitioned EDF scheduling of implicit-deadline sporadic task systems on (1) identical multiprocessor platforms, and (2) unrelated multiprocessor platforms containing a constant number of processors.

Original language	English
Pages (from-to)	219-238
Number of pages	20
Journal	Real-Time Systems
Volume	49
Issue number	2
DOIs	https://doi.org/10.1007/s11241-012-9164-y
State	Published - Mar 2013
Externally published	Yes

Keywords

Multiprocessor scheduling
Polynomial-time approximation scheme
Unrelated multiprocessors

Access to Document

10.1007/s11241-012-9164-y

Cite this

@article{0b5a50aa1d0d49a5956f4407bfb95b0f,

title = "Partitioned EDF scheduling on a few types of unrelated multiprocessors",

abstract = "A polynomial-time approximation scheme (PTAS) is derived for the partitioned EDF scheduling of implicit-deadline sporadic task systems upon unrelated multiprocessor platforms that are comprised of a constant number of distinct types of processors. This generalizes earlier results showing the existence of polynomial-time approximation schemes for the partitioned EDF scheduling of implicit-deadline sporadic task systems on (1) identical multiprocessor platforms, and (2) unrelated multiprocessor platforms containing a constant number of processors.",

keywords = "Multiprocessor scheduling, Polynomial-time approximation scheme, Unrelated multiprocessors",

author = "Andreas Wiese and Vincenzo Bonifaci and Sanjoy Baruah",

note = "Funding Information: This work was partially supported by a fellowship within the Postdoc-Programme of the German Academic Exchange Service (DAAD).",

year = "2013",

month = mar,

doi = "10.1007/s11241-012-9164-y",

language = "English",

volume = "49",

pages = "219--238",

journal = "Real-Time Systems",

issn = "0922-6443",

publisher = "Springer Netherlands",

number = "2",

}

TY - JOUR

T1 - Partitioned EDF scheduling on a few types of unrelated multiprocessors

AU - Wiese, Andreas

AU - Bonifaci, Vincenzo

AU - Baruah, Sanjoy

N1 - Funding Information: This work was partially supported by a fellowship within the Postdoc-Programme of the German Academic Exchange Service (DAAD).

PY - 2013/3

Y1 - 2013/3

N2 - A polynomial-time approximation scheme (PTAS) is derived for the partitioned EDF scheduling of implicit-deadline sporadic task systems upon unrelated multiprocessor platforms that are comprised of a constant number of distinct types of processors. This generalizes earlier results showing the existence of polynomial-time approximation schemes for the partitioned EDF scheduling of implicit-deadline sporadic task systems on (1) identical multiprocessor platforms, and (2) unrelated multiprocessor platforms containing a constant number of processors.

AB - A polynomial-time approximation scheme (PTAS) is derived for the partitioned EDF scheduling of implicit-deadline sporadic task systems upon unrelated multiprocessor platforms that are comprised of a constant number of distinct types of processors. This generalizes earlier results showing the existence of polynomial-time approximation schemes for the partitioned EDF scheduling of implicit-deadline sporadic task systems on (1) identical multiprocessor platforms, and (2) unrelated multiprocessor platforms containing a constant number of processors.

KW - Multiprocessor scheduling

KW - Polynomial-time approximation scheme

KW - Unrelated multiprocessors

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

U2 - 10.1007/s11241-012-9164-y

DO - 10.1007/s11241-012-9164-y

M3 - Article

AN - SCOPUS:84876287164

SN - 0922-6443

VL - 49

SP - 219

EP - 238

JO - Real-Time Systems

JF - Real-Time Systems

IS - 2

ER -

Partitioned EDF scheduling on a few types of unrelated multiprocessors

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this