Task partitioning with replication upon heterogeneous multiprocessor systems

Sathish Gopalakrishnan, Marco Caccamo

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
Title of host publicationProceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2006
Pages199-207
Number of pages9
DOIs
StatePublished - 2006
Event12th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2006 - San Jose, CA, United States
Duration: Apr 4 2006Apr 7 2006

Publication series

NameReal-Time Technology and Applications - Proceedings
ISSN (Print)1080-1812

Conference

Conference12th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2006
Country/TerritoryUnited States
CitySan Jose, CA
Period4/4/064/7/06

Keywords

  • Approximation scheme
  • Fault tolerance
  • Multiprocessor scheduling
  • Partitioning
  • Recurring
  • tasks

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Task partitioning with replication upon heterogeneous multiprocessor systems'. Together they form a unique fingerprint.

Cite this