Optimal Deadlock-free Path-based Multicast Algorithms in Meshes - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1997

Optimal Deadlock-free Path-based Multicast Algorithms in Meshes

Résumé

Multicasting is an information dissemination problem which consists, for a node of a distributed memory parallel computer, of sending the same message to an arbitrary subset of nodes. The two major criteria to be considered in multicast communication are \textsl{traffic} (number of channels used) and \textsl{latency} (time required). In this paper, we proposed new polynomial algorithms giving optimal solutions in terms of traffic or latency for a mesh network using \textsl{wormhole} routing and \textsl{path-based} facility. All the algorithms are shown to be deadlock-free. Moreover, we generalize our algorithms to arbitrary Hamiltonian graphs.
Une diffusion partielle est une opération de communication sur une machine parallèle à mémoire distribuée dans laquelle un processeur veut envoyer un même message à un sous groupe de processeurs. Les deux critères dévaluation couramment employés sont le traffic (nombre de canaux utilisés) et la latence (temps requis). Dans ce rapport, nous proposons de nouveaux algorithmes polynomiaux calculant une solution optimale soit en terme de traffic, soit en terme de latence. Nous présentons ces algorithmes dans le cas d'une grille avec comme hypothèse que le mode de routage mis en {\oe}uvre est wormhole et utilise une facilité de routage nommée path-based. Tous les algorithmes sont sans interblocage. Nous généralisons nos algorithmes à la classe des graphes hamiltoniens.
Fichier principal
Vignette du fichier
RR1997-31.pdf (321.15 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02102049 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02102049 , version 1

Citer

Vincent Bouchitté, Johanne Cohen, Eric Fleury. Optimal Deadlock-free Path-based Multicast Algorithms in Meshes. [Research Report] LIP RR-1997-31, Laboratoire de l'informatique du parallélisme. 1997, 2+13p. ⟨hal-02102049⟩
11 Consultations
24 Téléchargements

Partager

Gmail Facebook X LinkedIn More