A
common statistical problem is that of finding the median
element in a set of data. This paper presents an efficient
randomized high-level parallel algorithm for finding
the median given a set of elements distributed across
a parallel machine. In fact, our algorithm solves the
general selection problem that requires the determination
of the element of rank $k$, for an arbitrarily given
integer $k$. Our general framework is an SPMD distributed
memory programming model that is enhanced by a set of
communication primitives. We use efficient techniques
for distributing and coalescing data as well as efficient
combinations of task and data parallelism. The algorithms
have been coded in the message passing standard MPI,
and our experimental results from the IBM SP-2 illustrate
the scalability and efficiency of our algorithm and improve
upon all the related experimental results known to the
authors.
