The Contention Avoiding Concurrent Priority Queue
| Autor: | Kjell Winblad, Konstantinos Sagonas |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
020203 distributed computing
Multi-core processor Computer science 020207 software engineering 02 engineering and technology Parallel computing Data structure Bottleneck Scheduling (computing) Shortest path problem 0202 electrical engineering electronic engineering information engineering Cache Priority queue Queue |
| Zdroj: | Languages and Compilers for Parallel Computing ISBN: 9783319527086 LCPC |
| DOI: | 10.1007/978-3-319-52709-3_23 |
| Popis: | Efficient and scalable concurrent priority queues are crucial for the performance of many multicore applications, e.g. for task scheduling and the parallelization of various algorithms. Linearizable concurrent priority queues with traditional semantics suffer from an inherent sequential bottleneck in the head of the queue. This bottleneck is the motivation for some recently proposed priority queues with more relaxed semantics. We present the contention avoiding concurrent priority queue (CA-PQ), a data structure that functions as a linearizable concurrent priority with traditional semantics under low contention, but activates contention avoiding techniques that give it more relaxed semantics when high contention is detected. CA-PQ avoids contention in the head of the queue by removing items in bulk from the global data structure, which also allows it to often serve DelMin operations without accessing memory that is modified by several threads. We show that CA-PQ scales well. Its cache friendly design achieves performance that is twice as fast compared to that of state-of-the-art concurrent priority queues on several instances of a parallel shortest path benchmark. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|