Scheduling malleable task trees

Loris Marchal (1, 2) , Frédéric Vivien (1, 2) , Bertrand Simon (1, 2)

1 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
2 LIP - Laboratoire de l'Informatique du Parallélisme

Solving sparse linear systems can lead to processing tree workflows on a platform of processors. In this study, we use the model of malleable tasks motivated in [Prasanna96,Beaumont07] in order to study tree workflow schedules under two contradictory objectives: makespan minimization and memory minization. First, we give a simpler proof of the result of [Prasanna96] which allows to compute a makespan-optimal schedule for tree workflows. Then, we study a more realistic speed-up function and show that the previous schedules are not optimal in this context. Finally, we give complexity results concerning the objective of minimizing both makespan and memory.

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Loris Marchal, Frédéric Vivien, Bertrand Simon. Scheduling malleable task trees. [Research Report] RR-8587, INRIA. 2014. ⟨hal-01059704⟩