Dynamic Memory-Aware Task-Tree Scheduling

Guillaume Aupy 1, 2 Clément Brasseur 3 Loris Marchal 3, 4
2 TADAAM - Topology-Aware System-Scale Data Management for High-Performance Computing
LaBRI - Laboratoire Bordelais de Recherche en Informatique, Inria Bordeaux - Sud-Ouest
4 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Factorizing sparse matrices using direct multi-frontal methods generates directed tree-shaped task graphs, where edges represent data dependency between tasks. This paper revisits the execution of tree-shaped task graphs using multiple processors that share a bounded memory. A task can only be executed if all its input and output data can fit into the memory. The key difficulty is to manage the order of the task executions so that we can achieve high parallelism while staying below the memory bound. In particular, because input data of unprocessed tasks must be kept in memory, a bad scheduling strategy might compromise the termination of the algorithm. In the single processor case, solutions that are guaranteed to be below a memory bound are known. The multi-processor case (when one tries to minimize the total completion time) has been shown to be NP-complete. We present in this paper a novel heuristic solution that has a low complexity and is guaranteed to complete the tree within a given memory bound. We compare our algorithm to state of the art strategies, and observe that on both actual execution trees and synthetic trees, we always perform better than these solutions, with average speedups between 1.25 and 1.45 on actual assembly trees. Moreover, we show that the overhead of our algorithm is negligible even on deep trees, and would allow its runtime execution.
Keywords : scheduling memory tree
Type de document :
Communication dans un congrès
IPDPS 2017 - 31st IEEE International Parallel & Distributed Processing Symposium, May 2017, Orlando, United States. pp.10, 2017, proceedings of IPDPS 2017
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01472062
Contributeur : Equipe Roma <>
Soumis le : lundi 20 février 2017 - 15:05:29
Dernière modification le : mardi 16 janvier 2018 - 15:34:04
Document(s) archivé(s) le : dimanche 21 mai 2017 - 14:20:47

Fichier

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

Identifiants

  • HAL Id : hal-01472062, version 1

Collections

Citation

Guillaume Aupy, Clément Brasseur, Loris Marchal. Dynamic Memory-Aware Task-Tree Scheduling. IPDPS 2017 - 31st IEEE International Parallel & Distributed Processing Symposium, May 2017, Orlando, United States. pp.10, 2017, proceedings of IPDPS 2017. 〈hal-01472062〉

Partager

Métriques

Consultations de la notice

753

Téléchargements de fichiers

39