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.
Guillaume, Frank
Seidel, Tillmann		dblp
dblp
dblp
Editor(s):
Bilardi, G.
Ferreira, Afonso
Lüling, R.
Rolim, J.		dblp
dblp
dblp
dblp
BibTeX cite key*:
SibeynGuillaumeSeidel1997
Title, Booktitle
Title*:
Practical Parallel List Ranking
Booktitle*:
Proceedings of the 4th Symposium on Solving Irregularly Structured Problems in Parallel (IRREGULAR-97)
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Paderborn, Germany
Language:
English
Event Date*
(no longer used):
June 12-13
Organization:
Event Start Date:
Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected
Event End Date:
Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected
Publisher
Name*:
Springer
URL:
Address*:
Berlin
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1253
Number:
Month:
Pages:
25-36
Year*:
1997
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
 Parallel list ranking is a hard problem due to its extreme degree
of irregularity. Also because of its linear sequential complexity,
it requires considerable effort to just reach speed-up one (break
even). In this paper, we address the question of how to solve the
list-ranking problem for lists of length up to $2 \cdot 10^8$
in practice: we consider implementations on the Intel Paragon,
whose PUs are laid-out as a grid.

It turns out that pointer jumping, independent-set removal and
sparse ruling sets, all have practical importance for current
systems. For the sparse-ruling-set algorithm the speed-up strongly
increases with the number $k$ of nodes per PU, to finally reach
$27$ with 100 PUs, for $k = 2 \cdot 10^6$.
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{SibeynGuillaumeSeidel1997,
AUTHOR = {Sibeyn, Jop F. and Guillaume, Frank and Seidel, Tillmann},
 EDITOR = {Bilardi, G. and Ferreira, Afonso and L{\"u}ling, R. and Rolim, J.},
 TITLE = {Practical Parallel List Ranking},
 BOOKTITLE = {Proceedings of the 4th Symposium on Solving Irregularly Structured Problems in Parallel (IRREGULAR-97)},
 PUBLISHER = {Springer},
 YEAR = {1997},
 VOLUME = {1253},
 PAGES = {25--36},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Paderborn, Germany},
}

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 Sibeyn		Created
03/18/1998 03:24:40 PM
Revisions
6.
5.
4.
3.
2.		Editor(s)
Christine Kiesel
Uwe Brahm
Uwe Brahm
Uwe Brahm
Uwe Brahm		Edit Dates
20.09.2006 15:46:30
04/01/98 11:59:09 AM
03/31/98 08:09:12 PM
03/31/98 03:31:36 PM
03/30/98 07:03:22 PM