Skip to Main content Skip to Navigation
Reports

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 , Laboratoire I3S - 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.
Document type :
Reports
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00073266
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 12:22:55 PM
Last modification on : Monday, October 12, 2020 - 10:30:26 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:40:27 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

238

Files downloads

454