Task partitioning with replication upon heterogeneous multiprocessor systems

Sathish Gopalakrishnan; Marco Caccamo

doi:10.1109/RTAS.2006.43

Task partitioning with replication upon heterogeneous multiprocessor systems

Sathish Gopalakrishnan, Marco Caccamo

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

Abstract

The heterogeneous multiprocessor task partitioning with replication problem involves determining a mapping of recurring tasks upon a set consisting of different processing units in such a way that all tasks meet their timing constraints and no two replicas of the same task are assigned to the same processing unit. The replication requirement improves the resilience of the real-time system to a finite number of processor failures. This problem is NP-hard in the strong sense. We develop a Fully Polynomial-Time Approximation Scheme (FPTAS) for this problem.

Original language	English (US)
Title of host publication	Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium
Pages	199-207
Number of pages	9
DOIs	https://doi.org/10.1109/RTAS.2006.43
State	Published - Oct 17 2006
Event	12th IEEE Real-Time and Embedded Technology and Applications Symposium - San Jose, CA, United States Duration: Apr 4 2006 → Apr 7 2006

Publication series

Name	Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS
Volume	2006
ISSN (Print)	1545-3421

Other

Other	12th IEEE Real-Time and Embedded Technology and Applications Symposium
Country/Territory	United States
City	San Jose, CA
Period	4/4/06 → 4/7/06

Keywords

Approximation scheme
Fault tolerance
Multiprocessor scheduling
Partitioning
Recurring tasks

ASJC Scopus subject areas

Engineering(all)

Online availability

10.1109/RTAS.2006.43

Library availability

Discover UIUC Full Text

Cite this

Gopalakrishnan, S., & Caccamo, M. (2006). Task partitioning with replication upon heterogeneous multiprocessor systems. In Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium (pp. 199-207). [1613336] (Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS; Vol. 2006). https://doi.org/10.1109/RTAS.2006.43

Task partitioning with replication upon heterogeneous multiprocessor systems. / Gopalakrishnan, Sathish; Caccamo, Marco.
Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium. 2006. p. 199-207 1613336 (Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS; Vol. 2006).

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

Gopalakrishnan, S & Caccamo, M 2006, Task partitioning with replication upon heterogeneous multiprocessor systems. in Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium., 1613336, Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS, vol. 2006, pp. 199-207, 12th IEEE Real-Time and Embedded Technology and Applications Symposium, San Jose, CA, United States, 4/4/06. https://doi.org/10.1109/RTAS.2006.43

@inproceedings{993d2121abf345948abd3250e9137a78,

title = "Task partitioning with replication upon heterogeneous multiprocessor systems",

abstract = "The heterogeneous multiprocessor task partitioning with replication problem involves determining a mapping of recurring tasks upon a set consisting of different processing units in such a way that all tasks meet their timing constraints and no two replicas of the same task are assigned to the same processing unit. The replication requirement improves the resilience of the real-time system to a finite number of processor failures. This problem is NP-hard in the strong sense. We develop a Fully Polynomial-Time Approximation Scheme (FPTAS) for this problem.",

keywords = "Approximation scheme, Fault tolerance, Multiprocessor scheduling, Partitioning, Recurring tasks",

author = "Sathish Gopalakrishnan and Marco Caccamo",

year = "2006",

month = oct,

day = "17",

doi = "10.1109/RTAS.2006.43",

language = "English (US)",

isbn = "0769525164",

series = "Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS",

pages = "199--207",

booktitle = "Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium",

note = "12th IEEE Real-Time and Embedded Technology and Applications Symposium ; Conference date: 04-04-2006 Through 07-04-2006",

}

TY - GEN

T1 - Task partitioning with replication upon heterogeneous multiprocessor systems

AU - Gopalakrishnan, Sathish

AU - Caccamo, Marco

PY - 2006/10/17

Y1 - 2006/10/17

N2 - The heterogeneous multiprocessor task partitioning with replication problem involves determining a mapping of recurring tasks upon a set consisting of different processing units in such a way that all tasks meet their timing constraints and no two replicas of the same task are assigned to the same processing unit. The replication requirement improves the resilience of the real-time system to a finite number of processor failures. This problem is NP-hard in the strong sense. We develop a Fully Polynomial-Time Approximation Scheme (FPTAS) for this problem.

AB - The heterogeneous multiprocessor task partitioning with replication problem involves determining a mapping of recurring tasks upon a set consisting of different processing units in such a way that all tasks meet their timing constraints and no two replicas of the same task are assigned to the same processing unit. The replication requirement improves the resilience of the real-time system to a finite number of processor failures. This problem is NP-hard in the strong sense. We develop a Fully Polynomial-Time Approximation Scheme (FPTAS) for this problem.

KW - Approximation scheme

KW - Fault tolerance

KW - Multiprocessor scheduling

KW - Partitioning

KW - Recurring tasks

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

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

U2 - 10.1109/RTAS.2006.43

DO - 10.1109/RTAS.2006.43

M3 - Conference contribution

AN - SCOPUS:33749588167

SN - 0769525164

SN - 9780769525167

T3 - Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS

SP - 199

EP - 207

BT - Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium

T2 - 12th IEEE Real-Time and Embedded Technology and Applications Symposium

Y2 - 4 April 2006 through 7 April 2006

ER -

Task partitioning with replication upon heterogeneous multiprocessor systems

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this