Back to Search Start Over

An efficient algorithm for concurrent priority queue heaps

Authors :
Maged M. Michael
Galen C. Hunt
Michael L. Scott
Srinivasan Parthasarathy
Source :
Information Processing Letters. 60:151-157
Publication Year :
1996
Publisher :
Elsevier BV, 1996.

Abstract

We present a new algorithm for concurrent access to array-based priority queue heaps. Deletions proceed top-down as they do in a previous algorithm due to Rao and Kumar [1988 (IEEE Trans. Computers 37(12))], but insertions proceed bottom-up, and consecutive insertions use a bit-reversal technique to scatter accesses across the fringe of the tree, to reduce contention. Because insertions do not have to traverse the entire height of the tree (as they do in previous work), as many as O(M) operations can proceed in parallel, rather than O(log M) on a heap of size M. Experimental results on a Silicon Graphics Challenge multiprocessor demonstrate good overall performance for the new algorithm on small heaps, and significant performance improvements over known alternatives on large heaps with mixed insertion/deletion workloads.

Details

ISSN :
00200190
Volume :
60
Database :
OpenAIRE
Journal :
Information Processing Letters
Accession number :
edsair.doi...........0aadf797a6283cf61cea6bac6dbd924b