Practical algorithms for selection on coarse-grained parallel computers

摘要

In this paper, we consider the problem of selection on coarse-grained distributed memory parallel computers. We discuss several deterministic and randomized algorithms for parallel selection. Experimental results on the CM-5 demonstrate that randomized algorithms are superior to their deterministic counterparts.