English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

Gossiping on meshes and tori

MPS-Authors
/persons/resource/persons45478

Sibeyn,  Jop Frederic
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45260

Rao,  P. Srinivasa
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)

96-1-018.pdf
(Any fulltext), 14MB

Supplementary Material (public)
There is no public supplementary material available
Citation

Sibeyn, J. F., Rao, P. S., & Juurlink, B. H. H.(1996). Gossiping on meshes and tori (MPI-I-1996-1-018). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-A15A-8
Abstract
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.