ALGORITHMS FOR OPTIMIZATION OF RELAXED CONCURRENT PRIORITY QUEUES IN MULTICORE SYSTEMS

In designing the scalable concurrent data structures for shared-memory systems, one promising approach is the relaxation of operation execution order. Relaxed concurrent data structures are non-linearizable and don’t provide strong operation semantics (such as FIFO/LIFO for linear lists, delete max (min) element for priority queues, etc.). In the paper, use is made of the approach based on the design of concurrent data structures in the form of multiple simple data structures distributed among the threads. For the operation execution (insert, delete), a thread randomly chooses a subset of these simple structures and performs actions on them. An optimized relaxed concurrent priority queues based on this approach is proposed in the paper. The algorithms for optimization of priority queues selection for insert/delete operations and the algorithm for balancing the elements in queues have been designed. The algorithms consider the hierarchical structure of multicore systems, provide the data access localization and reduce the range of possible options for random selection. The optimized insertion algorithms increase the throughput by 22 % as compared with the original algorithms. The developed deletion algorithms improve the performance from 16 % up to 2 times.

Authors: A. V. Tabakov, A. A. Paznikov

Direction: Informatics and Computer Technologies

Keywords: Multithreading, threadsafe concurrent data structures, relaxed concurrent execution

---

View full article