Ultimate Parallel List Ranking?

Sibeyn, Jop F.

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Ultimate Parallel List Ranking?

MPS-Authors

Sibeyn, Jop F.
Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Sibeyn, J. F. (1999). Ultimate Parallel List Ranking? In P. Banerjee, V. K. Prasanna, & B. F. Sinha (Eds.), Proceedings of the 6th International Conference on High Performance Computing (HiPC-99) (pp. 197-201). Berlin: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-361D-4

Abstract

Two improved list-ranking algorithms are presented. The ``peeling-off'' algorithm leads to an optimal PRAM algorithm, but was designed with application on a real parallel machine in mind. It is simpler than earlier algorithms, and in a range of problem sizes, where previously several algorithms where required for the best performance, now this single algorithm suffices. If the problem size is much larger than the number of available processors, then the ``sparse-ruling-sets'' algorithm is even better. In previous versions this algorithm had very restricted practical application because of the large number of communication rounds it was performing. This weakness is overcome by adding two new ideas, each of which reduces the number of communication rounds by a factor of two.