MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Kaufmann, Michael
Meyer, Ulrich
Sibeyn, Jop F.		dblp
dblp
dblp
Editor(s):
BibTeX cite key*:
Kaufmann-Meyer-Sibeyn94
Title, Booktitle
Title*:
Towards Practical Permutation Routing on Meshes
Booktitle*:
Proceedings of the 6th IEEE Symposium on Parallel and Distributed Processing
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Dallas, Texas
Language:
English
Event Date*
(no longer used):
October, 26-29
Organization:
IEEE
Event Start Date:
3 October 2023
Event End Date:
3 October 2023
Publisher
Name*:
IEEE
URL:
Address*:
Los Alamitos, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
6
Month:
October
Pages:
656-663
Year*:
1994
VG Wort Pages:
ISBN/ISSN:
0-8186-6427-4
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We consider the permutation routing problem on two-dimensional
n x n meshes. To be practical, a routing algorithm is required
to ensure very small queue sizes Q, and very low running time T,
not only asymptotically but particularly also for the practically
important n up to 1000. With a technique inspired by a
scheme of Kaklamanis/Krizanc/Rao, we obtain a near-optimal
result: T = 2 n + O(1) with Q = 2. Although Q is very
attractive now, the lower order terms in T make this algorithm
highly impractical. Therefore we present simple schemes which are
asymptotically slower, but have T around 3 n for all n and Q
between 2 and 8.
Keywords:
Parallel Computing, Permutation Routing, Communication, Meshes
HyperLinks / References / URLs:
http://www.mpi-sb.mpg.de/~umeyer/pubs.cp.html
Download
Access Level:

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



BibTeX Entry:

@INPROCEEDINGS{Kaufmann-Meyer-Sibeyn94,
AUTHOR = {Kaufmann, Michael and Meyer, Ulrich and Sibeyn, Jop F.},
 TITLE = {Towards Practical Permutation Routing on Meshes},
 BOOKTITLE = {Proceedings of the 6th IEEE Symposium on Parallel and Distributed Processing},
 PUBLISHER = {IEEE},
 YEAR = {1994},
 ORGANIZATION = {IEEE},
 NUMBER = {6},
 PAGES = {656--663},
 ADDRESS = {Dallas, Texas},
 MONTH = {October},
 ISBN = {0-8186-6427-4},
}

Entry last modified by Ulrich Meyer, 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)
Ulrich Meyer		Created
06/04/1997 11:30:59
Revision
1.
0.


Editor
Ulrich Meyer
Ulrich Meyer


Edit Date
04/06/97 11:32:12
04/06/97 11:30:59