Next: Problem Overview
Practical Parallel Algorithms for Dynamic Data Redistribution,
Median Finding, and Selection
( Preliminary Draft)
David A. Bader
dbader@umiacs.umd.edu
Joseph JáJá
joseph@umiacs.umd.edu
Institute for Advanced Computer Studies, and
Department of Electrical Engineering,
University of Maryland, College Park, MD 20742
Fri Jul 14 09:30:16 EDT 1995
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.
Keywords: Parallel Algorithms, Communication Primitives, Median
Finding, Selection, Load Balancing, Data Redistribution, Parallel
Performance.
Next: Problem Overview
David A. Bader
dbader@umiacs.umd.edu