Accession Number : ADA299952

Title :   An Efficient Algorithm for Concurrent Priority Queue Heaps.

Descriptive Note : Technical rept.,

Corporate Author : ROCHESTER UNIV NY DEPT OF COMPUTER SCIENCE

Personal Author(s) : Hunt, Galen C. ; Michael, Maged M. ; Parthasarathy, Srinivasen ; Scott, Michael L.

PDF Url : ADA299952

Report Date : DEC 1994

Pagination or Media Count : 12

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, 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. (AN)

Descriptors :   *ALGORITHMS, *QUEUEING THEORY, *CONCURRENT ENGINEERING, COMPUTER PROGRAM DOCUMENTATION, OPTIMIZATION, COMPUTER PROGRAMMING, EFFICIENCY, PARALLEL PROCESSING, HEURISTIC METHODS, MULTIPROCESSORS, SUBROUTINES, WORKLOAD, CONTROL SEQUENCES.

Subject Categories : Computer Programming and Software
      Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE