CS-TR-3494, UMIACS-TR-95-74
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.
HTML
or
PostScript
or
Compressed PostScript
Version of this report.
Release 3.0 of the software
(Send e-mail request
for latest version)
For more infomation on any of the these topics, click on the hotlink.
Any queries, comments, or inquiries to:
David A. Bader (Click here for personal info!)
E-mail: dbader@umiacs.umd.edu
Office phone: (301)405-6755
FAX: (301)314-9658
Return to the Experimental Parallel Algorithmics page.