Architecture independent parallel selection with applications to parallel priority queues

Alexandros V. Gerbessiotis, Constantinos J. Siniolakis

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

We present a randomized selection algorithm whose performance is analyzed in an architecture independent way on the bulk-synchronous parallel (BSP) model of computation along with an application of this algorithm to dynamic data structures, namely parallel priority queues. We show that our algorithms improve previous results upon both the communication requirements and the amount of parallel slack required to achieve optimal performance. We also establish that optimality to within small multiplicative constant factors can be achieved for a wide range of parallel machines. While these algorithms are fairly simple themselves, descriptions of their performance in terms of the BSP parameters is somewhat involved; the main reward of quantifying these complications is that it allows transportable software to be written for parallel machines that fit the model.

Original languageEnglish (US)
Pages (from-to)119-142
Number of pages24
JournalTheoretical Computer Science
Volume301
Issue number1-3
DOIs
StatePublished - May 14 2003

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Algorithms
  • BSP model
  • Heaps
  • Priority queues
  • Selection

Fingerprint Dive into the research topics of 'Architecture independent parallel selection with applications to parallel priority queues'. Together they form a unique fingerprint.

Cite this