Optimal Deadlock-free Path-based Multicast Algorithms in Meshes

Vincent Bouchitte 1 Johanne Cohen Eric Fleury
1 RESEDAS - Software Tools for Telecommunications and Distributed Systems
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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) & \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 & \textsl{path-based} facility. All the algorithms are shown to be deadlock-free. Moreover, we generalize our algorithms to arbitrary Hamiltonian graphs.
Type de document :
Communication dans un congrès
5th International Colloquium on Structural Information & Communication Complexity (SIROCCO'98), 1998, Amalfi, Italy, 17 p, 1998
Liste complète des métadonnées

https://hal.inria.fr/inria-00098443
Contributeur : Publications Loria <>
Soumis le : lundi 25 septembre 2006 - 17:01:30
Dernière modification le : jeudi 11 janvier 2018 - 06:20:00

Identifiants

  • HAL Id : inria-00098443, version 1

Collections

Citation

Vincent Bouchitte, Johanne Cohen, Eric Fleury. Optimal Deadlock-free Path-based Multicast Algorithms in Meshes. 5th International Colloquium on Structural Information & Communication Complexity (SIROCCO'98), 1998, Amalfi, Italy, 17 p, 1998. 〈inria-00098443〉

Partager

Métriques

Consultations de la notice

87