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 ProcessorsRef: HURRAY-TR-091104 Publication Date: 3, Nov, 2009
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.