MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Sibeyn, Jop F.dblp
Editor(s):
Prívara, Igor
Ruzicka, Peter		dblp
dblp
BibTeX cite key*:
Sibeyn97c
Title, Booktitle
Title*:
Routing with Finite Speeds of Memory and Network
Booktitle*:
Proceedings of the 22nd Symposium on the Mathematical Foundations of Computer Science (MFCS-97)
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Bratislava, Slovakia
Language:
English
Event Date*
(no longer used):
August 22-29
Organization:
Event Start Date:
22 August 1997
Event End Date:
29 August 1997
Publisher
Name*:
Springer
URL:
Address*:
Berlin
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1295
Number:
Month:
Pages:
488-497
Year*:
1997
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
 On practical parallel computers, the time for routing a distribution
of sufficiently large packets can be approximated by $\max\{T_f,
T_b\}$. Here $T_f$ is proportional to the maximum number of bytes a
PU sends and receives, and $T_b$ is proportional to the maximum
number of bytes a connection in the network has to transfer.
We show that several important routing patterns can be performed
by a sequence of balanced all-to-all routings and analyze how
to optimally perform these under the above cost-model. We concentrate
on dimension-order routing on meshes, and assume that the routing
pattern must be decomposed into a sequence of permutations.
The developed strategy has been implemented on the Intel Paragon.
In comparison with the trivial strategy, in which $\mi{PU}_i$ routes
to $\mi{PU}_{(i + t) \bmod P}$ in permutation~$t$, $1 \leq t < P$,
one gains between $10$ and $20\%$.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{Sibeyn97c,
AUTHOR = {Sibeyn, Jop F.},
 EDITOR = {Pr{\'i}vara, Igor and Ruzicka, Peter},
 TITLE = {Routing with Finite Speeds of Memory and Network},
 BOOKTITLE = {Proceedings of the 22nd Symposium on the Mathematical Foundations of Computer Science (MFCS-97)},
 PUBLISHER = {Springer},
 YEAR = {1997},
 VOLUME = {1295},
 PAGES = {488--497},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Bratislava, Slovakia},
}

Entry last modified by Uwe Brahm, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Jop Sibeyn		Created
03/18/1998 15:27:43
Revisions
5.
4.
3.
2.
1.		Editor(s)
Uwe Brahm
Uwe Brahm
Uwe Brahm
Uwe Brahm
Uwe Brahm		Edit Dates
02/14/2005 08:17:46 PM
04/01/98 04:58:06 PM
03/31/98 07:07:56 PM
03/31/98 02:56:46 PM
03/31/98 11:02:57 AM