Parallel scheduling of task trees with limited memory

Lionel Eyraud-Dubois 1, 2 Loris Marchal 3, 4 Oliver Sinnen 5 Frédéric Vivien 3, 4
2 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
3 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
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 qui obtiennent différents compromis entre mémoire et temps d'exécution. Certaines d'entre elles sont capables de traiter l'arbre tout en gardant la consommation mémoire inférieure à une limite donnée. Nous analysons les performances de toutes ces heuristiques par une large campagne de simulations utilisant des arbres réalistes.
Type de document :
Rapport
[Research Report] RR-8606, INRIA. 2014, pp.37
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01070356
Contributeur : Equipe Roma <>
Soumis le : mercredi 1 octobre 2014 - 10:35:59
Dernière modification le : mardi 11 décembre 2018 - 10:58:05
Document(s) archivé(s) le : vendredi 2 janvier 2015 - 10:41:21

Fichiers

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

Identifiants

  • HAL Id : hal-01070356, version 1
  • ARXIV : 1410.0329

Citation

Lionel Eyraud-Dubois, Loris Marchal, Oliver Sinnen, Frédéric Vivien. Parallel scheduling of task trees with limited memory. [Research Report] RR-8606, INRIA. 2014, pp.37. 〈hal-01070356〉

Partager

Métriques

Consultations de la notice

766

Téléchargements de fichiers

286