Lock Free Priority Queue
- Mingkang Li
- Yijun Chen
We are going to implement a coarse-grained, fine-grained, and lock-free priority queue based on heaps and compare their performance. We are then going to benchmark it against real-life workloads.
A priority queue is a specialized queue in which each element has an additional priority associated with it. It is usually implemented with a binary heap, a tree-like data structure that conforms to the heap property: if P is a parent node of C, then the priority of P is greater than or equal to the priority of C. Having a concurrent, high-performance priority queue makes it possible to parallelize algorithms such as Djikstra's or Prim’s, as well as task scheduling algorithms used by operating systems. It is relatively straightforward to implement a single-threaded priority queue with arrays, but it becomes a challenge to implement it in a multi-core environment.
We aim to implement different versions of parallel priority queues that support insertion and deleteMin in O(logN) time. Additionally, we will benchmark our implementation against varying workloads on devices with different core counts and architectures.
More concurrency should be possible by enabling processes to access the priority queue concurrently as long as they do not interact with one another, as insertion/deletion typically modify just a small portion of the nodes. This can be achieved by using a skip list, a probabilistic data structure that is built upon the general idea of a linked list, which achieves logarithmic sequential search time on average.
When implementing a lock-free priority queue with skip lists, the main challenge stems from the fact that the skip list is similar to a multi-level linked list. The upper-level nodes must be handled properly in order to insert or delete a node at the bottom, which introduces contention and limits concurrency. Improving the locality of skip lists could also be a challenge, as the nodes may not be allocated in adjacent chunks of memory.
If we take the multidimensional list approach in the research paper, the biggest challenge would be the complexity in its implementation. The difficulty increases with the dimensions, as can be deducted from the number of lines of pseudo-code in the research paper.
Fast and Lock-Free Concurrent Priority Queues for Multi-Thread Systems by Hakan Sundell and Philippas Tsigas, 2003 (for lock-free PQ)
The Art of Multiprocessor Programming by Maurice Herlihy and Nir Shavit, 2008 (for fine-grained PQ)
A Lock-free Priority Queue Design Based on Multi-dimensional Linked Lists by Deli Zhang and Damian Dechev, 2015 (for further investigation)
A C++ Implementation of a Lock-Free Priority Queue Based on Multi-Dimensional Linked List, 2019 (for implementation reference)
- Coarse-grained priority queue
- Fine-grained priority queue
- Lock-free priority queue using skip lists
- Analysis on the performance of different implementations against different input size and parallel conditions
- Lock-free priority queue using multidimensional lists
- Test different implementations on real scientific problems that uses priority queue
- Analyze the tradeoffs of different design on problems with different use pattern
- Figures comparing the different implementations of priority queue
We will implement different versions of the priority queue in C++ and test them on the GHC machines. If time permits, we will also try them on PSC Bridge 2 machines.
| Week | Task |
|---|---|
| Nov 7, 2022 | Read the paper on the implementation of the lock-free priority queue and discuss it |
| Nov 14, 2022 | Implement the coarse-grained and fine-grained versions of priority queue |
| Nov 21, 2022 | Implement the skip-list version of lock-free PQ and complete the milestone report |
| Nov 28, 2022 | Try to improve the lock-free implementation with multidimensional lists and evaluate the performance under different conditions and use cases |
| Dec 5, 2022 | Research on use cases in real scientific problems and analyze the performance |
| Dec 12, 2022 | Finalize the analysis & complete final report |