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*:
Sibeyn97a
Title, Booktitle
Title*:
Better Trade-offs for Parallel List Ranking
Booktitle*:
Proceedings of the 9th Symposium on Parallel Algorithms and Architectures (SPAA-97)
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
New-Port Beach
Language:
English
Event Date*
(no longer used):
June 22-25
Organization:
ACM Press
Event Start Date:
22 June 1997
Event End Date:
25 June 1997
Publisher
Name*:
ACM Press
URL:
Address*:
New York
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
221-230
Year*:
1997
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
 An earlier parallel list ranking algorithm performs well for
problem sizes $N$ that are extremely large in comparison to the
number of PUs $P$. However, no existing algorithm gives good
performance for reasonable loads.

We present a novel family of algorithms, that achieve a better
trade-off between the number of start-ups and the routing volume.
We have implemented them on an Intel Paragon, and they turn out to
considerably outperform all earlier algorithms: with $P = 2$ the
sequential algorithm is already beaten for $N = \mbox{25,000}$; for
$P = 100$ and $N = 10^7$, the speed-up is 21, and for $N = 10^8$ it
even reaches 30.

A modification of one of our algorithms solves a theoretical
question: we show that on one-dimensional processor arrays, list
ranking can be solved with a number of steps equal to the diameter
of the network.
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{Sibeyn97a,
AUTHOR = {Sibeyn, Jop F.},
 TITLE = {Better Trade-offs for Parallel List Ranking},
 BOOKTITLE = {Proceedings of the 9th Symposium on Parallel Algorithms and Architectures (SPAA-97)},
 PUBLISHER = {ACM Press},
 YEAR = {1997},
 ORGANIZATION = {ACM Press},
 PAGES = {221--230},
 ADDRESS = {New-Port Beach},
}

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:21:44
Revisions
7.
6.
5.
4.
3.		Editor(s)
Uwe Brahm
Uwe Brahm
Uwe Brahm
Uwe Brahm
Uwe Brahm		Edit Dates
02/14/2005 08:16:34 PM
02/14/2005 08:15:59 PM
04/02/98 06:53:21 PM
03/31/98 07:47:02 PM
03/31/98 05:53:54 PM