Parallelism and Locality in Priority Queues

Abhiram Ranade, Szu-Tsung Cheng, Etienne Deprit, Jeff Jones,
and Sun-Inn Shih

We explore two ways of incorporating parallelism into priority
queues.  The first is to speed up the execution of individual
priority operations so that they can be performed one operation
per time step, unlike sequential implementations which require
O(log N) time steps per operation for an N element heap.  We
give an optimal parallel implementation that uses a linear
array of O(log N) processors.

Second, we consider parallel operations on the priority queue.
We show that using a d-dimensional array (constant d) of P
processors we can insert or delete the smallest P elements from
a heap in time O( P^(1/d) (log P)^(1-1/d) ), where the number of
elements in the heap is assumed to be polynomial in P.  We also
show a matching lower bound, based on communication complexity
arguments, for a range of deterministic implementations.
Finally, using randomization, we show that the time can be
reduced to the optimal O( P^(1/d) ) time with high probability.