[Back]

S. Hunold:
"One Step towards Bridging the Gap between Theory and Practice in Moldable Task Scheduling with Precedence Constraints";
Talk: Wirtschaftswissenschaftliche Fakultät, Universität Augsburg, Augsburg, Deutschland (invited); 2015-05-12.

Due to the increasing number of cores of current parallel machines and the growing need for a concurrent execution of tasks, the problem of parallel task scheduling is more relevant than ever, especially under the moldable task model, in which tasks are allocated to a fixed number of processors before execution. Much research has been conducted to develop efficient scheduling algorithms for moldable tasks, both in theory and practice. The problem is that theoretical as well as practical approaches expose shortcomings, e.g., many approximation algorithms only guarantee bounds under assumptions, which are unrealistic in practice, or most heuristics have not been rigorously compared to competing approximation algorithms. In particular, it is often assumed that the speedup function of moldable tasks is either non-decreasing, sub-linear or concave. In practice, however, the resulting speedup of parallel programs on current hardware with deep memory hierarchies is most often neither non-decreasing nor concave.

I will present a new algorithm for the problem of scheduling moldable tasks with precedence constraints for the makespan objective and for arbitrary speedup functions. I will show through simulation that the algorithm not only creates competitive schedules for moldable tasks with arbitrary speedup functions, but also outperforms other published heuristics and approximation algorithms for non-decreasing speedup functions.