[Zurück]

M. Wimmer, J. Gruber, J. Träff, P. Tsigas:
"The Lock-free k-LSM Relaxed Priority Queue";
Bericht für CoRR - Computing Research Repository; Berichts-Nr. arXiv:1503.05698, 2015; 18 S.

Priority queues are data structures which store keys in an ordered fashion to allow efficient access to the minimal (maximal) key. Priority queues are essential for many applications, e.g., Dijkstra's single-source shortest path algorithm, branch-and-bound algorithms, and prioritized schedulers.
Efficient multiprocessor computing requires implementations of basic data structures that can be used concurrently and scale to large numbers of threads and cores. Lock-free data structures promise superior scalability by avoiding blocking synchronization primitives, but the delete-min operation is an inherent scalability bottleneck in concurrent priority queues. Recent work has focused on alleviating this obstacle either by batching operations, or by relaxing the requirements to the delete-min operation.
We present a new, lock-free priority queue that relaxes the delete-min operation so that it is allowed to delete any of the ρ+1 smallest keys, where ρ is a runtime configurable parameter. Additionally, the behavior is identical to a non-relaxed priority queue for items added and removed by the same thread. The priority queue is built from a logarithmic number of sorted arrays in a way similar to log-structured merge-trees. We experimentally compare our priority queue to recent state-of-the-art lock-free priority queues, both with relaxed and non-relaxed semantics, showing high performance and good scalability of our approach.

Task-parallel programming, priority-queue, concurrent data structure relaxation, parallel singlesource shortest path