Practical parallel algorithms for dynamic data redistribution, median finding, and selection

David A. Bader, Joseph JaJa

Research output: Contribution to journalConference articlepeer-review

22 Scopus citations

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 distributed memory programming model 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.

Original languageEnglish (US)
Pages (from-to)292-301
Number of pages10
JournalIEEE Symposium on Parallel and Distributed Processing - Proceedings
StatePublished - 1996
Externally publishedYes
EventProceedings of the 1996 10th International Parallel Processing Symposium - Honolulu, HI, USA
Duration: Apr 15 1996Apr 19 1996

All Science Journal Classification (ASJC) codes

  • General Engineering

Fingerprint

Dive into the research topics of 'Practical parallel algorithms for dynamic data redistribution, median finding, and selection'. Together they form a unique fingerprint.

Cite this