Efficient parallel multiselection on hypercubes

Research output: Contribution to conferencePaperpeer-review

5 Citations (Scopus)

Abstract

We study efficient parallel solutions to the problem of selecting r elements at specified ranks from a set of n arbitrary elements, known as multiselection, on a hypercube with p processors, p,rles/n. We propose two parallel algorithms based on different approaches, where one requires processors to operate in the SIMD mode, and the other in the MIMD mode. Our SIMD algorithm runs in time O((log n log log n) min{r, log n}) when p=Theta/(n), and O(n ϵ min{r, (1-ϵ) log n}) when p=n ϵ for any 0<ϵ<1, where the latter is cost optimal when r≥p. Our MIMD algorithm runs in O(log n log log n log r) time when p=Theta/(n), and in O(n ϵ log r) time when p=n ϵ for any 0<ϵ<1, which is cost optimal for any r. Both algorithms are more efficient than the possible straightforward solutions and that of direct simulation of the optimal EREW algorithm.

Original languageEnglish
Pages338-343
Number of pages6
DOIs
Publication statusPublished - 1997
Externally publishedYes
Event3rd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN 1997 - Taipei, Taiwan, Province of China
Duration: 18 Dec 199720 Dec 1997

Conference

Conference3rd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN 1997
Country/TerritoryTaiwan, Province of China
CityTaipei
Period18/12/9720/12/97

Keywords

  • Hypercube
  • Multiselection
  • Parallel algorithm
  • Selection
  • Sorting

Fingerprint

Dive into the research topics of 'Efficient parallel multiselection on hypercubes'. Together they form a unique fingerprint.

Cite this