Memory-aware tree partitioning on homogeneous platforms

Résumé : Les applications scientifiques sont couramment modélisées par des graphes de tâches. Pour certaines d'entre elles, le graphe prend la forme particulière d'un arbre enraciné". Cet arbre détermine à la fois les dépendance entre tâches de calcul et les besoins en stockage. Le problème d'ordonnancer (ou parcourir) un tel arbre sur un seul processeur pour réduire son empreinte mémoire a déjà largement été étudié. Dans ce rapport, nous considérons le traitement parallèle d'un tel arbre et étudions comment le partitionner pour une plate-forme de calcul formée de processeurs homogènes disposant chacun de sa propre mémoire. Nous formalisons le problème du partitionnement de l'arbre en sous-arbres de telle sorte que chaque sous-arbre puisse être traité sur un seul processeur et que le temps de calcul total soit minimal. Nous montrons que ce problème est NP-complet et proposons des heuristiques polynomiales. Un ensemble exhaustif,de simulations permet de montrer l'utilité de ces heuristiques.
Type de document :
Rapport
[Research Report] RR-9115, Inria Grenoble Rhône-Alpes. 2017, pp.1-25
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01644352
Contributeur : Equipe Roma <>
Soumis le : jeudi 21 décembre 2017 - 16:37:46
Dernière modification le : samedi 15 septembre 2018 - 01:19:54

Fichier

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

Identifiants

  • HAL Id : hal-01644352, version 2

Citation

Changjiang Gou, Anne Benoit, Loris Marchal. Memory-aware tree partitioning on homogeneous platforms. [Research Report] RR-9115, Inria Grenoble Rhône-Alpes. 2017, pp.1-25. 〈hal-01644352v2〉

Partager

Métriques

Consultations de la notice

108

Téléchargements de fichiers

40