Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Gossiping on meshes and tori

Sibeyn, Jop F. and Rao, P. S. and Juurlink, Ben H. H.

MPI-I-96-1-018. November 1996, 19 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
Algorithms for performing gossiping on one- and higher dimensional
meshes are presented. As a routing model, we assume the
practically important worm-hole routing.

For one-dimensional arrays and rings, we give a novel lower bound
and an asymptotically optimal gossiping algorithm for all choices of
the parameters involved.

For two-dimensional meshes and tori, several simple algorithms
composed of one-dimensional phases are presented. For an important
range of packet and mesh sizes it gives clear improvements upon
previously developed algorithms. The algorithm is analyzed
theoretically, and the achieved improvements are also convincingly
demonstrated by simulations and by an implementation on the Paragon.
For example, on a Paragon with $81$ processors and messages of size
32 KB, relying on the built-in router requires $716$ milliseconds,
while our algorithm requires only $79$ milliseconds.

For higher dimensional meshes, we give algorithms which are based
on a generalized notion of a diagonal. These are analyzed
theoretically and by simulation.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
96-1-018.pdf96-1-018.pdfMPI-I-96-1-018.ps250 KBytes; 13642 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Sibeyn, Jop F. and Rao, P. S. and Juurlink, Ben H. H.},
  TITLE = {Gossiping on meshes and tori},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-96-1-018},
  MONTH = {November},
  YEAR = {1996},
  ISSN = {0946-011X},