Optimal Deadlock-free Path-based Multicast Algorithms in Meshes

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) 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.
Document type :
Reports
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102049
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:12:54 AM
Last modification on : Wednesday, November 20, 2019 - 2:53:16 AM

File

RR1997-31.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102049, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

3

Files downloads

8