[Back]

S. Hunold:
"On the Scalability of Moldable Task Scheduling Algorithms";
Talk: Dagstuhl Seminar 13381: Algorithms and Scheduling Techniques for Exascale Systems, Schloss Dagstuhl, Wadern, Germany (invited); 2013-09-15 - 2013-09-20.

Parallel task scheduling is now more relevant than ever, especially under the moldable task model, in which tasks are allocated a fixed number of processors before execution. A common assumption for scheduling algorithms is that the speedup function of moldable tasks is either non-decreasing, sub-linear or concave. However, in practice the resulting speedup of parallel programs on current hardware with deep memory hierarchies is most often neither non-decreasing nor
concave. We present an algorithm for scheduling moldable tasks with precedence constraints for the makespan objective and arbitrary speedup functions. We 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.