max planck institut
informatik
informatik
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.
Acknowledgement:
References to related material:
| To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |
|---|---|
| 274 KBytes | |
| Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView | |
BibTeX