Assigning Real-Time Tasks on Heterogeneous Multiprocessors with Two Unrelated Types of Processors

Consider the problem of scheduling a set of implicit deadline sporadic tasks on a heterogeneous multiprocessor platform to meet all 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) its time-complexity is 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 as that of FF-3C 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 given task set, so as to succeed, 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 12000 to 160000 times faster and has significantly smaller necessary multiplication factor than state-of-art algorithms.