Assigning Real-Time Tasks on Heterogeneous Multiprocessors with Two Types of Processors
Ref: HURRAY-TR-091104 Publication Date: 3, Nov, 2009
Assigning Real-Time Tasks on Heterogeneous Multiprocessors with Two Types of Processors
Ref: HURRAY-TR-091104 Publication Date: 3, Nov, 2009Abstract:
Consider the problem of scheduling a set of implicit deadline
sporadic tasks on a heterogeneous multiprocessor
so as to meet all deadlines. Tasks cannot migrate and
the platform is restricted in that each processor is either
of type-1 or type-2 (with each task characterized by a
different speed of execution upon each type of processor).
We present an algorithm for this problem with a time complexity
of O(n*m), where n is the number of tasks and
m is the number of processors. It offers the guarantee that
if a task set can be scheduled by any non-migrative algorithm
to meet deadlines then our algorithm meets deadlines
as well if given processors twice as fast. Although this result
is proven for only a restricted heterogeneous multiprocessor,
we consider it significant for being the first realtime
scheduling algorithm to use a low-complexity binpacking
approach to schedule tasks on a heterogeneous
multiprocessor with provably good performance.
Document:
Record Date: 3, Nov, 2009