Provably good task assignment on heterogeneous multiprocessor platforms for a restricted case but with a stronger adversary
Ref: HURRAY-TR-110901 Publication Date: 6 to 8, Jul, 2011
Provably good task assignment on heterogeneous multiprocessor platforms for a restricted case but with a stronger adversary
Ref: HURRAY-TR-110901 Publication Date: 6 to 8, Jul, 2011Abstract:
Abstract—Consider the problem of scheduling a set of implicit-deadline sporadic tasks to meet all deadlines on a heterogeneous multiprocessor platform. We consider a restricted case where the maximum utilization of any task on any processor in the system is no greater than one. We use an algorithm proposed in [1] (we refer to it as LP-EE) from state-of-the-art for assigning tasks to heterogeneous multiprocessor platform and (re-)prove its performance guarantee
for this restricted case but for a stronger adversary. We show that if a task set can be scheduled to meet deadlines on a heterogeneous multiprocessor platform by an optimal task assignment scheme that allows task migrations then LP-EE meets deadlines as well with no migrations if given processors twice as fast.
Gurulingesh Raravi
Björn Andersson
Konstantinos BletsasDocument:
View
DownloadPublished in 23rd Euromicro Conference on Real-Time Systems (ECRTS11), ACM SIGBED Review, Volume 8, Issue 3, pp 19-22.
Porto, Portugal.
DOI:10.1145/2038617.2038621.
Notes: Work-In-Progress Session
Record Date: 13, Sep, 2011