Arbres couvrants arête-disjoints dans les grilles toriques d-dimensionnelles pour la diffusion de messages longs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport Année : 1998

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

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-3424.pdf (561.87 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00073266 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00073266 , version 1

Citer

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⟩
112 Consultations
432 Téléchargements

Partager

Gmail Facebook X LinkedIn More