Engineering MultiQueues: Fast Relaxed Concurrent Priority Queues
Engineering MultiQueues: Fast Relaxed Concurrent Priority Queues
复制标题
工程多队列：快速宽松的并发优先级队列
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Roman Dementiev
中科院分区：
文献类型：
--
作者：
Marvin Williams;P. Sanders;Roman Dementiev
具有并行访问的优先级队列是一种有吸引力的数据结构，适用于优先级在线调度、离散事件模拟或贪婪算法等应用。然而，一个经典的优先级队列构成了严重的瓶颈，在这种情况下，导致非常小的吞吐量。因此，人们对具有宽松语义的并发优先级队列产生了极大的兴趣。我们调查的互补质量标准排名误差（如何接近删除的元素到全局最小值）和延迟（对于每个元素x，有多少元素具有较低的优先级被删除之前x）。在本文中，我们介绍了多个顺序优先级队列的基础上放松优先级队列作为一种自然的方法。通过在顺序队列上使用三种正交的并行操作方式，进一步增强了它们自然的高理论可扩展性。实验表明，Multiplexes提出了一个非常好的性能质量的权衡，并大大优于竞争的方法，在这些方面中的至少一个。我们采用了一个看似矛盾的技术“无等待锁定”，可能是更普遍的兴趣，顺序数据结构转换为宽松的并发数据结构。
Priority queues with parallel access are an attractive data structure for applications like prioritized online scheduling, discrete event simulation, or greedy algorithms. However, a classical priority queue constitutes a severe bottleneck in this context, leading to very small throughput. Hence, there has been significant interest in concurrent priority queues with relaxed semantics. We investigate the complementary quality criteria rank error (how close are deleted elements to the global minimum) and delay (for each element x, how many elements with lower priority are deleted before x). In this paper, we introduce MultiQueues as a natural approach to relaxed priority queues based on multiple sequential priority queues. Their naturally high theoretical scalability is further enhanced by using three orthogonal ways of batching operations on the sequential queues. Experiments indicate that MultiQueues present a very good performance-quality tradeoff and considerably outperform competing approaches in at least one of these aspects. We employ a seemingly paradoxical technique of"wait-free locking"that might be of more general interest to convert sequential data structures to relaxed concurrent data structures.
顺序和并行算法和数据结构：基本工具箱
DOI：
10.1007/978-3-030-25209-0
发表时间：
2019
期刊：
Sequential and Parallel Algorithms and Data Structures
影响因子：
--
作者：
P. Sanders;K. Mehlhorn;M. Dietzfelbinger;R. Dementiev
通讯作者：
R. Dementiev