The partitioned multiprocessor scheduling of deadline-constrained sporadic task systems

Sanjoy Baruah; Nathan Fisher

doi:10.1109/TC.2006.113

The partitioned multiprocessor scheduling of deadline-constrained sporadic task systems

Sanjoy Baruah, Nathan Fisher

Department of Computer Science & Engineering

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

65 Scopus citations

Abstract

A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks, each constrained to have its relative-deadline parameter be no larger than its period parameter, among the processors of an identical multiprocessor platform. Since the partitioning problem is easily seen to be 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 (3-1/m) times as fast.

Original language	English
Pages (from-to)	918-923
Number of pages	6
Journal	IEEE Transactions on Computers
Volume	55
Issue number	7
DOIs	https://doi.org/10.1109/TC.2006.113
State	Published - Jul 2006

Keywords

Multiprocessors
Partitioned scheduling
Resource augmentation
Sporadic tasks

Access to Document

10.1109/TC.2006.113

Cite this

@article{cffb281ba3bd4d0d9bf2ee22b701cd6b,

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

abstract = "A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks, each constrained to have its relative-deadline parameter be no larger than its period parameter, among the processors of an identical multiprocessor platform. Since the partitioning problem is easily seen to be 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 (3-1/m) times as fast.",

keywords = "Multiprocessors, Partitioned scheduling, Resource augmentation, Sporadic tasks",

author = "Sanjoy Baruah and Nathan Fisher",

year = "2006",

month = jul,

doi = "10.1109/TC.2006.113",

language = "English",

volume = "55",

pages = "918--923",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

number = "7",

}

TY - JOUR

T1 - The partitioned multiprocessor scheduling of deadline-constrained sporadic task systems

AU - Baruah, Sanjoy

AU - Fisher, Nathan

PY - 2006/7

Y1 - 2006/7

N2 - A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks, each constrained to have its relative-deadline parameter be no larger than its period parameter, among the processors of an identical multiprocessor platform. Since the partitioning problem is easily seen to be 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 (3-1/m) times as fast.

AB - A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks, each constrained to have its relative-deadline parameter be no larger than its period parameter, among the processors of an identical multiprocessor platform. Since the partitioning problem is easily seen to be 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 (3-1/m) times as fast.

KW - Multiprocessors

KW - Partitioned scheduling

KW - Resource augmentation

KW - Sporadic tasks

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

U2 - 10.1109/TC.2006.113

DO - 10.1109/TC.2006.113

M3 - Article

AN - SCOPUS:33744818212

SN - 0018-9340

VL - 55

SP - 918

EP - 923

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 7

ER -

The partitioned multiprocessor scheduling of deadline-constrained sporadic task systems

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this