Scheduling tree-shaped task graphs to minimize memory and makespan

Résumé : Dans ce rapport, nous nous intéressons au traitement d'arbres de tâches par plusieurs processeurs. Chaque arête d'un tel arbre représente un gros fichier d'entrée/sortie. Une tâche peut être traitée seulement si l'ensemble de ses fichiers d'entrée et de sortie peut résider en mémoire, et un fichier ne peut être retiré de la mémoire que lorsqu'il a été traité. De tels arbres surviennent, par exemple, lors de la factorisation de matrices creuses par des méthodes multifrontales. La quantité de mémoire nécessaire dépend de l'ordre de traitement des tâches. Avec un seul processeur, l'objectif est naturellement de minimiser la quantité de mémoire requise. Ce problème a déjà été étudié et des algorithmes polynomiaux ont été proposés. Nous étendons ce problème en considérant plusieurs processeurs, ce qui est d'un intérêt évident pour le problème de la factorisation de grandes matrices. Avec plusieurs processeurs se pose également le problème de la minimisation du temps nécessaire pour traiter l'arbre. Nous montrons que comme attendu, ce problème est bien plus compliqué que dans le cas séquentiel. Nous étudions la complexité de ce problème et nous fournissons des résultats d'inaproximabilité, même dans le cas de poids unitaires. Nous proposons plusieurs heuristiques pour obtenir un ordonnancement, qui se concentrent chacune sur un objectif différent. Nous analysons leurs performances par une large campagne de simulations utilisant des arbres réalistes.
Type de document :
Rapport
[Research Report] RR-8082, INRIA. 2012, pp.21


https://hal.inria.fr/hal-00740105
Contributeur : Loris Marchal <>
Soumis le : mardi 9 octobre 2012 - 15:53:47
Dernière modification le : samedi 17 septembre 2016 - 01:36:39

Fichier

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

Identifiants

  • HAL Id : hal-00740105, version 1

Collections

Citation

Loris Marchal, Oliver Sinnen, Frédéric Vivien. Scheduling tree-shaped task graphs to minimize memory and makespan. [Research Report] RR-8082, INRIA. 2012, pp.21. <hal-00740105>

Exporter

Partager

Métriques

Consultations de
la notice

155

Téléchargements du document

78