Assigning real-time tasks on heterogeneous multiprocessors with two unrelated types of processors

A preliminary version of this paper appeared in Proceedings of the 31st IEEE Real-Time Systems Symposium, 2010, pp. 239–248.

Consider the problem of partitioned scheduling of an implicit-deadline sporadic task set on heterogeneous multiprocessors to meet all deadlines. Each processor is either of type-1 or type-2. We present a new algorithm, FF-3C, for this problem. FF-3C offers low time-complexity and provably good performance. Specifically, FF-3C offers (i) a time-complexity of O(n⋅max(m,logn)+m⋅logm), where n is the number of tasks and m is the number of processors and (ii) the guarantee that if a task set can be scheduled by an optimal partitioned-scheduling algorithm to meet all deadlines then FF-3C meets all deadlines as well if given processors at most 11−α times as fast (referred to as speed competitive ratio) and tasks are scheduled using EDF; where α is a property of the task set. The parameter α is in the range (0,0.5] and for each task, it holds that its utilization is no greater than α or greater than 1−α on each processor type. Thus, the speed competitive ratio of FF-3C can never exceed 2. We also present several extensions to FF-3C; these offer the same performance guarantee and time-complexity but with improved average-case performance. Via simulations, we compare the performance of our new algorithms and two state-of-the-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 that the algorithm needs, for a given task set, so as to succeed, compared to an optimal task assignment algorithm. Overall, we observed that our new algorithms perform significantly better than the state-of-the-art. We also observed that our algorithms perform much better in practice, i.e., the necessary multiplication factor of the algorithms is much smaller than their speed competitive ratio. Finally, we also present a clustered version of the new algorithm.