Lock Bypassing: An Efficient Algorithm for Concurrently Accessing 
Priority Heaps 

Y. Yan and X. Zhang    

ACM Journal on Experimental Algorithmics, Vol. 3, No. 3, 1998, pp. 1-29.   
 
Abstract
--------
The heap representation of priority queues is one of the most widely
used  data structures in the design of parallel algorithms.
Efficiently exploiting the parallelism of a priority heap has
significant influence on the efficiency of a wide range of
applications and  parallel algorithms.  In this paper, we propose an
aggressive priority heap operating algorithm,  called the lock
bypassing algorithm (LB) on shared memory systems.   This algorithm
minimizes interference of concurrent enqueue and dequeue operations
on priority heaps while keeping the strict priority property: a
dequeue  always returns the minimum of a heap.    The unique idea that
distinguishes the LB algorithm from previous concurrent  algorithms on
priority heaps is the use of locking-on-demand and lock-bypassing
techniques  to minimize locking granularity and to maximize
parallelism.   The LB algorithm allows an enqueue  operation to bypass
the locks along its insertion path until it reaches a  possible place
where it can perform the insertion.  Meanwhile a dequeue operation
also makes its locking range and locking   period as small as possible
by carefully tuning its execution procedure.  The LB algorithm is
shown to be correct  in terms of deadlock freedom and heap
consistency.   The performance of the LB algorithm was evaluated
analytically and experimentally  in comparison with previous
algorithms. Analytical results show  that the LB algorithm reduces by
half the number of locks waited for  in the worst case  by previous
algorithms. The experimental results show  that the LB algorithm
outperforms previously designed algorithms  by up to a factor of 2 in
hold time.