Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


From parallel to external list ranking

Sibeyn, Jop F.

MPI-I-97-1-021. October 1997, 15 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
Novel algorithms are presented for parallel and external memory
list-ranking. The same algorithms can be used for computing basic
tree functions, such as the depth of a node.

The parallel algorithm stands out through its low memory use, its
simplicity and its performance. For a large range of problem sizes,
it is almost as fast as the fastest previous algorithms. On a
Paragon with 100 PUs, each holding 10^6 nodes, we obtain speed-up 25.

For external-memory list-ranking, the best algorithm so far is
an optimized version of independent-set-removal. Actually,
this algorithm is not good at all: for a list of length N, the
paging volume is about 72 N. Our new algorithm reduces
this to 18 N. The algorithm has been implemented,
and the theoretical results are confirmed.

References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-97-1-021.ps274 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Sibeyn, Jop F.},
  TITLE = {From parallel to external list ranking},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-97-1-021},
  MONTH = {October},
  YEAR = {1997},
  ISSN = {0946-011X},