Concurrent access of priority queues

Abstract

Contention for the shared heap limits the obtainable speedup in parallel algorithms using this data structure as a priority queue. An approach that allows concurrent insertions and deletions on the heap in a shared-memory multiprocessor is presented. The scheme 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. Experimental results on the BBN Butterfly parallel processor demonstrate that the use of concurrent-heap algorithms in parallel branch-and-bound improves its performance substantially.<>