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):
BibTeX cite key*:
F.Sibeyn-IPPS-1999
Title, Booktitle
Title*:
Better Deterministic Routing on Meshes
Booktitle*:
Proceedings of the 13th International Parallel Processing Symposium, and 10th Symposium on Parallel and Distributed Processing (IPPS/SPDP-99)
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
St Juan, Puerto Rico
Language:
English
Event Date*
(no longer used):
April, 12-16, 1999
Organization:
Event Start Date:
12 April 1999
Event End Date:
16 April 1999
Publisher
Name*:
IEEE
URL:
Address*:
Los Alamitos, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
May
Pages:
420-425
Year*:
1999
VG Wort Pages:
ISBN/ISSN:
0-7695-0143-5
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
 Optimal randomized and deterministic algorithms have been given for $k$-$k$
routing on two-dimensional $n \times n$ meshes. The deterministic algorithm
is based on ``column-sort'' and exploits only part of the
features of the mesh. For small $n$ and moderate $k$, the lower-order terms
of this algorithm make it considerably more expensive than the
randomized algorithm. In this paper, we present a novel deterministic
algorithm, which, by exploiting the topology of the mesh, has lower-order
terms that are almost negligible, even smaller than those of the randomized
algorithm. An additional advantage of the new algorithm is that it routes
average-case packet distributions twice as fast as worst-case distributions.
In earlier algorithms this required additional steps for globally probing the
distribution.
Keywords:
Algorithms, Routing, Meshes
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{F.Sibeyn-IPPS-1999,
AUTHOR = {Sibeyn, Jop F.},
 TITLE = {Better Deterministic Routing on Meshes},
 BOOKTITLE = {Proceedings of the 13th International Parallel Processing Symposium, and 10th Symposium on Parallel and Distributed Processing (IPPS/SPDP-99)},
 PUBLISHER = {IEEE},
 YEAR = {1999},
 PAGES = {420--425},
 ADDRESS = {St Juan, Puerto Rico},
 MONTH = {May},
 ISBN = {0-7695-0143-5},
}

Entry last modified by Christine Kiesel, 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 F. Sibeyn		Created
02/19/2000 03:40:29 PM
Revisions
8.
7.
6.
5.
4.		Editor(s)
Christine Kiesel
Uwe Brahm
Uwe Brahm
Christine Kiesel
Christine Kiesel		Edit Dates
30.05.2005 16:39:21
02/14/2005 08:09:37 PM
04/04/2001 07:46:02 PM
04/04/2000 12:37:48
30.03.2000 12:26:01