![]() ![]() For benchmark purposes, our fine-grained and coarse-grained PQ's were implemented as traditional heaps.Ī skiplist lowers contention from multiple inserts and deletes for two main reasons. We got this idea from the paper cited in the Resources Section. In order to implement the lock-free PQ, a skiplist was used rather than the traditional heap data structure. The improved solution is to remove the overhead of obtaining and releasing mutexes and to use a data structure less prone to contention that heaps face. In particular, these locks can slow down insertion and deletion operations as they sift nodes up and down through the heap to maintain the heap invariant. Traditional lock-based concurrent priority queues are implemented as heaps and rely primarily on lock-based mechanisms for synchronization. This is cirtical for parallelized algorithms such as A* or Djikstra's as well as for the scheduler at the operating system level. BackgroundĪn effective concurrent priority queue should be able to quickly handle multiple simultaneous insert and deleteMin operations over a sustained period of time. These traces were run on the GHC 8-core hyper-threaded machines. This includes traces with heavy insertion, deletion, and a mix of the operations. We implemented a lock-free priority queue that is better than a fine-grained and coarse-grained priority queue for various high-contention traces using more than 3 threads. ![]() Finalwriteup PQ Unlocked: Lock-Free Priority Queue Summary ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |