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 adversaryRef: HURRAY-TR-110901 Publication Date: 6 to 8, Jul, 2011
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  (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.
Published in 23rd Euromicro Conference on Real-Time Systems (ECRTS11), ACM SIGBED Review, Volume 8, Issue 3, pp 19-22.
Notes: Work-In-Progress Session