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. 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. Index Terms: coarse-grained, hypercubes, load balancing, median finding, meshes, randomized algorithms, selection, parallel algorithms, parallel computers. 1 Introduction Given a set of N elements, a total order defined on the elements, and a number k, the selection problem is to find the k th smallest element in the given set of elements. The problem has several applications in computer science and stat..