Arbres couvrants arête-disjoints dans les grilles toriques d-dimensionnelles pour la diffusion de messages longs

Eric Darrot 1
1 SLOOP - Simulation, Object Oriented Languages and Parallelism
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : La diffusion de messages longs est un schéma de communication globale dont l'optimisation est essentielle dans un contexte de calcul parallèle intensif. Après avoir exposé les arguments qui font préférer une approche \st{} plutôt que \wo{} (on montre alors qu'il est optimal de découper le message initial et de <> les tronçons obtenus sur des arbres couvrants disjoints), je donne les définitions, conventions et quelques résultats qui me permettent de poser le problème dans le cas général. Je décris ensuite brièvement les résultats connus dans le cas bidimensionnel. Puis, après avoir fixé un certain nombre de notations, je donne une construction du maximum d'arbres couvrants arête-disjo- ints dans les tores $d$-dimensionnels, pour tout $d > 2$, en traitant le cas tridimensionnel à part, pour des raisons de clarté de l'exposé. Tous les arbres sont obtenus par le même algorithme, qui utilise la structure récursive du graphe. Leur profondeur tend vers le double du diamètre quand le nombre de dimensions tend vers l'infini. Enfin, je conclus par une étude comparative des performances estimées de l'algorithme de diffusion issu de cette construction, dans une optique SPMD et pour une machine représentative des supercalculateurs modernes.
Type de document :
Rapport
RR-3424, INRIA. 1998
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00073266
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 12:22:55
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:40:27

Fichiers

Identifiants

  • HAL Id : inria-00073266, version 1

Collections

Citation

Eric Darrot. Arbres couvrants arête-disjoints dans les grilles toriques d-dimensionnelles pour la diffusion de messages longs. RR-3424, INRIA. 1998. 〈inria-00073266〉

Partager

Métriques

Consultations de la notice

203

Téléchargements de fichiers

272