HomePublicationsPaper

Assigning Real-Time Tasks on Heterogeneous Multiprocessors with Two Unrelated Types of Processors
Ref: HURRAY-TR-100505       Publication Date: 30, Nov to 3, Dec, 2010

Abstract:
Consider the problem of scheduling a set of implicit deadline sporadic tasks on a heterogeneous multiprocessor so as to meet all the deadlines. Tasks cannot migrate and each processor is either of type-1 or type-2 (with each task having different execution speed on each processor type). We present a new algorithm, FF-3C, for this problem. FF-3C offers low-time complexity and provably good performance. Specifically, (i) it has the time-complexity O(n · max(m, log n)), where n is the number of tasks and m is the number of processors and (ii) it offers the guarantee that if a task set can be scheduled by an optimal task assignment scheme to meet deadlines then FF-3C meets deadlines as well if given processors twice as fast. We also present several extensions to FF-3C; these offer the same time-complexity and performance guarantee but in addition, they offer improved average-case performance. Via experiments with randomly generated task sets, we compare the performance of our new algorithms and two established state-of-art algorithms (and variations of the latter). We evaluate algorithms based on (i) running time and (ii) the necessary multiplication factor, i.e., the amount of extra speed of processors the algorithm needs, for a particular task set, in order to succeed as compared to an optimal task assignment scheme. Overall our new algorithms compare favorably to the state-of-art. One in particular (FF-4C-COMB), in our experimental evaluations, runs 13000 to 160000 times faster and has significantly smaller necessary multiplication factor than the prior state-of-art algorithms.

Björn Andersson

,

Gurulingesh Raravi

,

Konstantinos Bletsas

Document:

View
PDF Download
PDF