Generic algorithms for scheduling applications on heterogeneous platforms

摘要

We study the problem of executing an application represented by a precedence task graph ona parallel machine composed of standard computing cores and accelerators. Both off-line andon-line settings are addressed by proposing generic scheduling approaches. In the first case, weestablish strong lower bounds on the worst-case performance of a known approach based onLinear Programming and replace the greedy List Scheduling policy used in this approach by abetter task ordering. Although this modification leads to the same approximability guarantees,it performs much better in practice. We also extend this algorithm to more types of computingunits, achieving an approximation ratio which depends on the number of different types. In theon-line case, tasks arrive in any order which respects the precedence relations and the schedulerhas to take irrevocable decisions about their allocation and execution.We propose the firston-line scheduling algorithm taking into account precedences, which is based on adequate rulesfor selecting the type of processorwhere to allocate the tasks. Finally, all the previous algorithmshave been experimented on a large number of simulations built on actual libraries, assessing theirgood practical behavior with respect to the state-of-the-art solutions and baseline algorithms.