Concurrent Access of Priority Queues

V. Nageshwara Rao, Vipin Kumar

Research output: Contribution to journalArticlepeer-review

58 Scopus citations

Abstract

The heap is an important data structure used as a priority queue in a wide variety of parallel algorithms (e.g., multiprocessor scheduling, branch-and-bound). In these algorithms, contention for the shared heap limits the obtainable speedup. This paper presents an approach to allow concurrent insertions and deletions on the heap in a shared-memory multiprocessor. The scheme also retains the strict priority ordering of the serial-access heap algorithms; i.e., a delete operation returns the best key of all keys that have been inserted or are being inserted at the time delete is started. Our experimental results on the BBN Butterfly parallel processor demonstrate that the use of the concurrentheap algorithms in parallel branch-and-bound improves its performance substantially.

Original languageEnglish (US)
Pages (from-to)1657-1665
Number of pages9
JournalIEEE Transactions on Computers
Volume37
Issue number12
DOIs
StatePublished - Dec 1988

Keywords

  • Branch-and-bound
  • concurrent data structures
  • deletions
  • insertions
  • priority queues
  • speedup

Fingerprint

Dive into the research topics of 'Concurrent Access of Priority Queues'. Together they form a unique fingerprint.

Cite this