Assigning real-time tasks on heterogeneous multiprocessors with two unrelated types of processors
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 \(\frac{1}{1-\alpha}\) 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 exceed2.
heterogeneous multiprocessors bin packing real-time scheduling