Algorithms for Optimization of Relaxed Concurrent Priority Queues in Multicore Systems
Andrey V. Tabakov, Alexey A. Paznikov · 2019
Design of scalable concurrent data structures for shared memory systems is one of promising approach to relaxation of operation execution order. Relaxed concurrent data structures are non-linearizable and do not provide strong operation semantics (such as FIFO/LIFO for linear lists, delete max (min) element for priority queues, etc.). In the paper, we use the approach based on design of concurrent data structure as multiple simple data structures distributed among the threads. For operation execution (insert, delete), a thread randomly chooses a subset of these simple structures and make actions on them. We propose optimized relaxed concurrent priority queues based on this approach. We designed algorithms for optimization of priority queues selection for insert/delete operations and algorithm for balancing of elements in queues.