Show simple item record

Practical Parallel Algorithms for Dynamic Data Redistribution, Median Finding, and Selection

dc.contributor.authorBader, David A.en_US
dc.contributor.authorJaJa, Josephen_US
dc.description.abstractA 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.)en_US
dc.format.extent1170441 bytes
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3494en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-95-44.en_US
dc.titlePractical Parallel Algorithms for Dynamic Data Redistribution, Median Finding, and Selectionen_US
dc.typeTechnical Reporten_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US

Files in this item


This item appears in the following Collection(s)

Show simple item record