NPAC Technical Report SCCS-743
Practical Algorithms for Selection on Coarse-Grained Parallel Computers
Ibraheem Al-Furaih, Srinivas Aluru, Sanjay Goil, Sanjay Ranka
Submitted September 22 1995
Abstract
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. We also consider
several algorithms for load balancing needed to keep a balanced
distribution of data across processors during the execution of the
selection algorithms. We have carried out detailed implementations of
all the algorithms discussed on the CM-5 and report on the experimental
results. We demonstrate that the randomized algorithms are superior to
their deterministic counterparts.