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
Distribution Statement : APPROVED FOR PUBLIC RELEASE