Determining the optimal redistribution

Résumé : Le problème de redistribution classique consiste à ordonnancer les communications de manière optimale lorsque l'on passe une distribution de données initiale \Dini à une distribution cible \Dtar où chaque processeur $P_{i}$ héberge un sous-ensemble $P(i)$ des données. Cependant, les plates-formes de calcul modernes sont équipées de puissants réseaux d'interconnexion programmables, et le coût d'une communication donnée est (presque) indépendant de l'emplacement de l'expéditeur et du récepteur. Cela conduit à généraliser le problème de redistribution comme suit: trouver la permutation optimale $\sigma$ de processeurs telle que $P_{i}$ héberge l'ensemble $P(\sigma(i))$, et telle que le coût de redistribution soit minimal. Ce rapport étudie la complexité de ce problème généralisé. Nous proposons des algorithmes optimaux et évaluons leur gain par rapport à la redistribution classique, via quelques simulations. Nous montrons aussi la NP-completude du problème consistant à trouver la partition de données optimale et la permutation des processeurs (définie par les nouveaux sous-ensembles $P(\sigma(i))$) qui minimise le coût de la redistribution suivie d'un noyau de calcul simple.
Type de document :
Rapport
[Research Report] RR-8499, INRIA. 2014
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00960452
Contributeur : Julien Herrmann <>
Soumis le : mercredi 19 mars 2014 - 15:41:49
Dernière modification le : mardi 16 janvier 2018 - 15:35:56
Document(s) archivé(s) le : lundi 10 avril 2017 - 01:25:06

Fichier

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

Identifiants

  • HAL Id : hal-00960452, version 2

Collections

Citation

Thomas Hérault, Julien Herrmann, Loris Marchal, Yves Robert. Determining the optimal redistribution. [Research Report] RR-8499, INRIA. 2014. 〈hal-00960452v2〉

Partager

Métriques

Consultations de la notice

418

Téléchargements de fichiers

126