Scheduling Trees of Malleable Tasks for Sparse Linear Algebra

Abdou Guermouche 1, 2 Loris Marchal 3, 4, * Bertrand Simon 3, 4 Frédéric Vivien 3, 4
* Auteur correspondant
2 HiePACS - High-End Parallel Algorithms for Challenging Numerical Simulations
LaBRI - Laboratoire Bordelais de Recherche en Informatique, Inria Bordeaux - Sud-Ouest
3 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Scientific workloads are often described by directed acyclic task graphs. This is in particular the case for multifrontal factorization of sparse matrices —the focus of this paper— whose task graph is struc-tured as a tree of parallel tasks. Prasanna and Musicus advocated using the concept of malleable tasks to model parallel tasks involved in matrix computations. In this powerful model each task is processed on a time-varying number of processors. Following Prasanna and Musicus, we consider malleable tasks whose speedup is p α , where p is the fractional share of processors on which a task executes, and α (0 < α ≤ 1) is a task-independent parameter. Firstly, we use actual experiments on mul-ticore platforms to motivate the relevance of this model for our application. Then, we study the optimal time-minimizing allocation proposed by Prasanna and Musicus using optimal control theory. We greatly simplify their proofs by resorting only to pure scheduling arguments. Building on the insight gained thanks to these new proofs, we extend the study to distributed (homogeneous or heterogeneous) multicore platforms. We prove the NP-completeness of the corresponding scheduling problem, and we then propose some approximation algorithms.
Type de document :
Communication dans un congrès
International European Conference on Parallel and Distributed Computing (Euro-Par 2015), 2015, Vienna, Austria. 2015, 〈www.europar2015.org〉
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01160104
Contributeur : Equipe Roma <>
Soumis le : jeudi 4 juin 2015 - 14:54:14
Dernière modification le : mardi 11 décembre 2018 - 10:58:04
Document(s) archivé(s) le : mardi 25 avril 2017 - 03:08:28

Fichier

europar.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01160104, version 1

Citation

Abdou Guermouche, Loris Marchal, Bertrand Simon, Frédéric Vivien. Scheduling Trees of Malleable Tasks for Sparse Linear Algebra. International European Conference on Parallel and Distributed Computing (Euro-Par 2015), 2015, Vienna, Austria. 2015, 〈www.europar2015.org〉. 〈hal-01160104〉

Partager

Métriques

Consultations de la notice

416

Téléchargements de fichiers

150