TY - GEN
T1 - Task partitioning upon heterogeneous multiprocessor platforms
AU - Baruah, Sanjoy
PY - 2004
Y1 - 2004
N2 - Given, a collection of recurring tasks or processes that comprise the software for a real-time system, and a collection of available processing units of different kinds upon which to execute them, the heterogeneous multiprocessor partitioning problem is concerned with determining whether the given tasks can be partitioned among the available processing units in such a manner that all timing constraints are met. It is shown that this problem is intractable (NP-hard in the strong sense). Efficient implementations of sufficient (albeit not necessary) partitioning algorithms are presented, and proved correct.
AB - Given, a collection of recurring tasks or processes that comprise the software for a real-time system, and a collection of available processing units of different kinds upon which to execute them, the heterogeneous multiprocessor partitioning problem is concerned with determining whether the given tasks can be partitioned among the available processing units in such a manner that all timing constraints are met. It is shown that this problem is intractable (NP-hard in the strong sense). Efficient implementations of sufficient (albeit not necessary) partitioning algorithms are presented, and proved correct.
KW - Approximation algorithms
KW - Multiprocessor scheduling
KW - Partitioning
KW - Periodic tasks
UR - https://www.scopus.com/pages/publications/7744240459
M3 - Conference contribution
AN - SCOPUS:7744240459
SN - 0769521487
SN - 9780769521480
T3 - Proceedings - IEEE Real-Time and Embedded Technology and Applications Symposium
SP - 536
EP - 543
BT - Proceedings - RTAS 2004 10th IEEE Real-Time and Embedded Technology and Applications Symposium
T2 - Proceedings - RTAS 2004 10th IEEE Real-Time and Embedded Technology and Applications Symposium
Y2 - 25 May 2004 through 28 May 2004
ER -