[Zurück]

R. Bleuse, S. Hunold, S. Kedad-Sidhoum, F. Monna, G. Mounie, D. Trystram:
"Scheduling Independent Moldable Tasks on Multi-Cores with GPUs";
IEEE Transactions on Parallel and Distributed Systems, Volume 28 (2017), Issue 9; S. 2689 - 2702.

We present a new approach for scheduling independent tasks on multiple CPUs and multiple GPUs. The tasks are assumed to be parallelizable on CPUs using the moldable model: the final number of cores allotted to a task can be decided and set by the scheduler. More precisely, we design an algorithm aiming at minimizing the makespan-the maximum completion time of all tasks-for this scheduling problem. The proposed algorithm combines a dual approximation scheme with a fast integer linear program (ILP). It determines both the partitioning of the tasks, i.e., whether a task should be mapped to CPUs or a GPU, and the number of CPUs allotted to a moldable task if mapped to the CPUs. A worst-case analysis shows that the algorithm has an approximation ratio of 3/2+ϵ . Since the time complexity of the ILP-based algorithm could be non-polynomial, we also present a polynomial-time algorithm with an approximation ratio of 2+ϵ . We complement the theoretical analysis of our two novel algorithms with a simulation study. In these simulations, we compare our algorithms to a modified version of the classical HEFT algorithm, which we adapted to handle moldable tasks. The simulation results show that our algorithm with the (3/2+ϵ) -approximation ratio produces significantly shorter schedules than the modified HEFT for most of the instances. In addition, our results provide evidence that our ILP-based algorithm can solve larger problem instances in a reasonable amount of time.

Scheduling, heterogeneous computing, moldable tasks, dual approximation scheme, integer linear programming

http://dx.doi.org/10.1109/TPDS.2017.2675891