TR-98-3.pdf
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.