Practical Parallel Algorithms for Dynamic Data Redistribution,
Median Finding, and Selection
Practical Parallel Algorithms for Dynamic Data Redistribution,
Median Finding, and Selection
Loading...
Files
Publication or External Link
Date
1998-10-15
Authors
Bader, David A.
JaJa, Joseph
Advisor
Citation
DRUM DOI
Abstract
A common statistical problem is that of finding the
median element in a set of data. This paper presents a fast and
portable 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 $i$, for an arbitrarily given integer $i$.
Practical algorithms needed by our selection algorithm for the dynamic
redistribution of data are also discussed. Our general framework is a
single-address space, distributed memory programming model that is
enhanced by a set of communication primitives. We use efficient
techniques for distributing, coalescing, and load balancing data as
well as efficient combinations of task and data parallelism. The
algorithms have been coded in Split-C and run on a variety of
platforms, including the Thinking Machines CM-5, IBM SP-1 and SP-2,
Cray Research T3D, Meiko Scientific CS-2, Intel Paragon, and
workstation clusters. Our experimental results illustrate the
scalability and efficiency of our algorithms across different
platforms and improve upon all the related experimental results known
to the authors. More efficient implementations of the communication
primitives will likely result in even faster execution times.
(Also cross-referenced as UMIACS-TR-95-44.)