Malleable task-graph scheduling with a practical speed-up model

Abstract : Scientific workloads are often described by Directed Acyclic task Graphs. Indeed, DAGs represent both a model frequently studied in theoretical literature and the structure employed by dynamic runtime schedulers to handle HPC applications. A natural problem is then to compute a makespan-minimizing schedule of a given graph. In this paper, we are motivated by task graphs arising from multifrontal factorizations of sparsematrices and therefore work under the following practical model. We focus on malleable tasks (i.e., a single task can be allotted a time-varying number of processors) and specifically on a simple yet realistic speedup model: each task can be perfectly parallelized, but only up to a limited number of processors. We first prove that the associated decision problem of minimizing the makespan is NP-Complete. Then, we study a widely used algorithm, PropScheduling, under this practical model and propose a new strategy GreedyFilling. Even though both strategies are 2-approximations, experiments on real and synthetic data sets show that GreedyFilling achieves significantly lower makespans.
Type de document :
[Research Report] RR-8856, ENS de Lyon. 2016
Liste complète des métadonnées

Littérature citée [40 références]  Voir  Masquer  Télécharger
Contributeur : Equipe Roma <>
Soumis le : lundi 15 février 2016 - 13:57:49
Dernière modification le : mardi 11 décembre 2018 - 10:58:13
Document(s) archivé(s) le : samedi 12 novembre 2016 - 20:50:34


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01274099, version 1



Loris Marchal, Bertrand Simon, Oliver Sinnen, Frédéric Vivien. Malleable task-graph scheduling with a practical speed-up model. [Research Report] RR-8856, ENS de Lyon. 2016. 〈hal-01274099〉



Consultations de la notice


Téléchargements de fichiers