[Back]

S. Hunold:
"Scheduling Moldable Tasks with Precedence Constraints and Arbitrary Speedup Functions on Multiprocessors";
Talk: Workshop on Scheduling for Parallel Computing (SPC 2013) in conjunction with the 10th International Conference on Parallel Processing and Applied Mathematics, PPAM 2013, Warsaw, Poland; 2013-09-08 - 2013-09-11; in: "Parallel Processing and Applied Mathematics, 10th International Conference, PPAM 2013, Revised Selected Papers, Part II", R. Wyrzykowski, J. Dongarra, K. Karczewski, J. Wasniewski (ed.); Springer, LNCS 8385 (2014), ISBN: 978-3-642-55194-9; 13 - 25.

Due to the increasing number of cores of current parallel machines, the question arises to which cores parallel tasks should be mapped. Thus, 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. Scheduling algorithms
commonly assume 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.
We present a new algorithm for the problem of scheduling moldable
tasks with precedence constraints for the makespan objective and for
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.

Multiprocessor scheduling, Homogeneous processors, Moldable tasks, Makespan optimization, Speedup functions

http://dx.doi.org/10.1007/978-3-642-55195-6_2