MPI-I-97-1-021
From parallel to external list ranking
Sibeyn, Jop F.
October 1997, 15 pages.
.
Status: available - back from printing
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.
-
- Attachement: MPI-I-97-1-021.ps (274 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1997-1-021
BibTeX
@TECHREPORT{Sibeyn97,
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},
}