Parallel scheduling of DAGs under memory constraints

Résumé : Les applications de calcul scientifique sont souvent modélisées par des graphes de tâches orientés acycliques (DAG), qui représentent les tâches de calcul et leurs dépendances, sous la forme de données produites par une tâche et utilisées par une autre. Cette formulation permet l’utilisation d’API qui allouent dynamiquement les tâches sur les ressources de plateformes de calcul hétérogènes de plus en plus complexes. Cependant, pour certaines ap- plications, un tel ordonnancement dynamique peut manquer de mémoire en exploitant trop de parallélisme. Cet article porte sur le problème consistant à transformer un tel DAG pour empêcher toute pénurie de mémoire, en se con- centrant sur les plateformes à mémoire partagée. On propose tout d’abord un modèle simple de graphe qui est assez expressif pour émuler des comporte- ments mémoires complexes. On expose ensuite un algorithme polynomial qui calcule le pic mémoire maximum d’un DAG, qui représente la mémoire maxi- male requise par tout ordonnancement parallèle. On considère ensuite le prob- lème consistant à réduire ce pic mémoire maximal pour qu’il devienne plus pe- tit qu’une borne donnée en rajoutant des arêtes fictives, tout en essayant de minimiser le chemin critique du graphe. Après avoir prouvé ce problème NP- complet, on fournit un programme linéaire en nombres entiers le résolvant, ainsi que plusieurs stratégies heuristiques qui sont minitieusement comparées- sur des graphes synthétiques modélisant des applications de calcul réelles. On montre que sur la plupart des instances, on arrive à diminuer le pic mémoire maximal, au prix d’une légère augmentation du chemin critique, et donc avec peu d’impact sur la qualité de l’ordonnancement parallèle final.
Type de document :
Rapport
[Research Report] RR-9108, LIP - ENS Lyon. 2017
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01620255
Contributeur : Equipe Roma <>
Soumis le : mardi 24 octobre 2017 - 18:21:54
Dernière modification le : mardi 16 janvier 2018 - 16:06:58

Fichier

RR-9108.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01620255, version 2

Collections

Citation

Loris Marchal, Hanna Nagy, Bertrand Simon, Frédéric Vivien. Parallel scheduling of DAGs under memory constraints. [Research Report] RR-9108, LIP - ENS Lyon. 2017. 〈hal-01620255v2〉

Partager

Métriques

Consultations de la notice

42

Téléchargements de fichiers

15