The ACM Journal of Experimental Algorithmics

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 it 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 other algorithms. The experimental results show that the LB algorithm outperforms previously designed algorithms by up to a factor of 2 in hold time.

• Keywords: Priority Heap, Parallel Algorithm, Shared-Memory System, Aggressive Locking, Performance Evaluation
• Sources:
  
  • The LaTeX version of the article; this is a Unix tar file that contains the LaTeX sources; note that you must be a subscriber (institutional or individual) to access this file.
  • The Postscript version or PDF version of the article;
    note that you must be a subscriber (institutional or individual) to access these files.
  • The HTML version of the article;
    note that you must be a subscriber (institutional or individual) to access this file.
  • The software suite accompanying the article; this is a small Unix tar file, which includes the source code, a Makefile, and the test files used in the article.
  • The bibliography given in the article.

Last updated and validated August 3, 1998, by editor@jea.acm.org