English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Gossiping on meshes and tori

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.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-0014-A15A-8 Version Permalink: http://hdl.handle.net/11858/00-001M-0000-0027-A06A-2
Genre: Report

Files

show Files
hide Files
:
96-1-018.pdf (Any fulltext), 14MB
Name:
96-1-018.pdf
Description:
-
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Sibeyn, Jop Frederic1, Author              
Rao, P. Srinivasa1, Author              
Juurlink, Ben H. H.2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 1996
 Publication Status: Published in print
 Pages: 19 p.
 Publishing info: Saarbrücken : Max-Planck-Institut für Informatik
 Table of Contents: -
 Rev. Type: -
 Identifiers: URI: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1996-1-018
Report Nr.: MPI-I-1996-1-018
BibTex Citekey: SibeynRaoJuurlink96
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Research Report
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -