Efficient weighted multiselection in parallel architectures

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

We study parallel solutions to the problem of weighted multiselection to select r elements on given weighted-ranks from a set S of n weighted elements, where an element is on weighted rank k if it is the smallest element such that the aggregated weight of all elements not greater than it in S is not smaller than k. We propose efficient algorithms on two of the most popular parallel architectures, hypercube and mesh. For a hypercube with p < n processors, we present a parallel algorithm running in 0(n min{r, log p}) time for p = n1-∈, 0 < ∈ < 1, which is cost optimal when r ≥ p. Our algorithm on √p x √p- mesh runs in O(√p + p-n log3 p) time which is the same as multiselection on mesh when r ≥ logp, and thus has the same optimality as multiselection in this case.

Original languageEnglish
Title of host publicationProceedings - 5th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2002
EditorsWanlei Zhou, Andrzej Goscinski, Guo-jie Li, Xue-bin Chi
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2-8
Number of pages7
ISBN (Electronic)0769515126, 9780769515120
DOIs
Publication statusPublished - 2002
Externally publishedYes
Event5th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2002 - Beijing, China
Duration: 23 Oct 200225 Oct 2002

Publication series

NameProceedings - 5th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2002

Conference

Conference5th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2002
Country/TerritoryChina
CityBeijing
Period23/10/0225/10/02

Keywords

  • Hypercube
  • mesh
  • multiselection
  • parallel algorithm
  • weighted selection

Fingerprint

Dive into the research topics of 'Efficient weighted multiselection in parallel architectures'. Together they form a unique fingerprint.

Cite this