The partitioned multiprocessor scheduling of sporadic task systems

Sanjoy Baruah; Nathan Fisher

doi:10.1109/RTSS.2005.40

The partitioned multiprocessor scheduling of sporadic task systems

Sanjoy Baruah
, Nathan Fisher

Department of Computer Science & Engineering

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

109 Scopus citations

Abstract

A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks among the processors of an identical multiprocessor platform. Since the partitioning problem is NP-hard in the strong sense, this algorithm is unlikely to be optimal. A quantitative characterization of its worst-case performance is provided in terms of resource augmentation; it is shown that any set of sporadic tasks that can be partitioned among the processors of an m-processor identical multiprocessor platform will be partitioned by this algorithm on an m-processor platform in which each processor is (4 - 2/m) times as fast.

Original language	English
Title of host publication	Proceedings - 26th IEEE International Real-Time Systems Symposium, RTSS 2005
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	321-329
Number of pages	9
ISBN (Print)	0769524907, 9780769524900
DOIs	https://doi.org/10.1109/RTSS.2005.40
State	Published - 2005
Event	26th IEEE International Real-Time Systems Symposium, RTSS 2005 - Miami, FL, United States Duration: Dec 5 2005 → Dec 8 2005

Publication series

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

Conference

Conference	26th IEEE International Real-Time Systems Symposium, RTSS 2005
Country/Territory	United States
City	Miami, FL
Period	12/5/05 → 12/8/05

Access to Document

10.1109/RTSS.2005.40

Cite this

@inproceedings{449ce856df9c4a1c811529039b2aa673,

title = "The partitioned multiprocessor scheduling of sporadic task systems",

abstract = "A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks among the processors of an identical multiprocessor platform. Since the partitioning problem is NP-hard in the strong sense, this algorithm is unlikely to be optimal. A quantitative characterization of its worst-case performance is provided in terms of resource augmentation; it is shown that any set of sporadic tasks that can be partitioned among the processors of an m-processor identical multiprocessor platform will be partitioned by this algorithm on an m-processor platform in which each processor is (4 - 2/m) times as fast.",

author = "Sanjoy Baruah and Nathan Fisher",

year = "2005",

doi = "10.1109/RTSS.2005.40",

language = "English",

isbn = "0769524907",

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

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

pages = "321--329",

booktitle = "Proceedings - 26th IEEE International Real-Time Systems Symposium, RTSS 2005",

note = "26th IEEE International Real-Time Systems Symposium, RTSS 2005 ; Conference date: 05-12-2005 Through 08-12-2005",

}

Baruah, S & Fisher, N 2005, The partitioned multiprocessor scheduling of sporadic task systems. in Proceedings - 26th IEEE International Real-Time Systems Symposium, RTSS 2005., 1563119, Proceedings - Real-Time Systems Symposium, Institute of Electrical and Electronics Engineers Inc., pp. 321-329, 26th IEEE International Real-Time Systems Symposium, RTSS 2005, Miami, FL, United States, 12/5/05. https://doi.org/10.1109/RTSS.2005.40

The partitioned multiprocessor scheduling of sporadic task systems. / Baruah, Sanjoy; Fisher, Nathan.
Proceedings - 26th IEEE International Real-Time Systems Symposium, RTSS 2005. Institute of Electrical and Electronics Engineers Inc., 2005. p. 321-329 1563119 (Proceedings - Real-Time Systems Symposium).

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

TY - GEN

T1 - The partitioned multiprocessor scheduling of sporadic task systems

AU - Baruah, Sanjoy

AU - Fisher, Nathan

PY - 2005

Y1 - 2005

N2 - A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks among the processors of an identical multiprocessor platform. Since the partitioning problem is NP-hard in the strong sense, this algorithm is unlikely to be optimal. A quantitative characterization of its worst-case performance is provided in terms of resource augmentation; it is shown that any set of sporadic tasks that can be partitioned among the processors of an m-processor identical multiprocessor platform will be partitioned by this algorithm on an m-processor platform in which each processor is (4 - 2/m) times as fast.

AB - A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks among the processors of an identical multiprocessor platform. Since the partitioning problem is NP-hard in the strong sense, this algorithm is unlikely to be optimal. A quantitative characterization of its worst-case performance is provided in terms of resource augmentation; it is shown that any set of sporadic tasks that can be partitioned among the processors of an m-processor identical multiprocessor platform will be partitioned by this algorithm on an m-processor platform in which each processor is (4 - 2/m) times as fast.

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

U2 - 10.1109/RTSS.2005.40

DO - 10.1109/RTSS.2005.40

M3 - Conference contribution

AN - SCOPUS:84879338948

SN - 0769524907

SN - 9780769524900

T3 - Proceedings - Real-Time Systems Symposium

SP - 321

EP - 329

BT - Proceedings - 26th IEEE International Real-Time Systems Symposium, RTSS 2005

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 26th IEEE International Real-Time Systems Symposium, RTSS 2005

Y2 - 5 December 2005 through 8 December 2005

ER -

The partitioned multiprocessor scheduling of sporadic task systems

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this