MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


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: (274 KBytes)

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},