hide
Free keywords:
-
Abstract:
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.
