A Lock-Free Priority Queue Design Based on Multi-Dimensional Linked Lists
A Lock-Free Priority Queue Design Based on Multi-Dimensional Linked Lists
复制标题
一种基于多维链表的无锁优先级队列设计
DOI：
--
复制
发表时间：
2016
影响因子：
5.3
通讯作者：
D. Dechev
中科院分区：
文献类型：
--
作者：
Deli Zhang;D. Dechev
并发优先级队列的吞吐量是离散事件模拟、最佳优先搜索和任务调度等多处理器应用的关键。现有的无锁优先级队列大多基于跳过列表，它可能会在有序列表中创建快捷方式，以快速插入元素。使用skiplists消除了平衡搜索树中全局重新平衡的需要，并确保平均对数顺序搜索时间，但最坏情况下的性能与输入大小呈线性关系。在本文中，我们提出了一个静态一致的无锁优先级队列的基础上的多维列表，保证最坏情况下的搜索时间为O（logN）的大小为N的关键字宇宙。新颖的多维列表（MDList）由节点组成，这些节点包含多个链接到按其维度排列的子节点。插入操作的工作原理是首先将标量键映射到一个高维向量，然后使用该向量作为坐标来唯一定位目标位置。MDList中的节点按其坐标前缀排序，并且在插入期间很容易维护数据结构的排序属性，而无需重新平衡或随机化。在我们的实验评估使用微基准，我们的优先级队列实现了平均50%的加速比在高并发的最先进的方法。
The throughput of concurrent priority queues is pivotal to multiprocessor applications such as discrete event simulation, best-first search and task scheduling. Existing lock-free priority queues are mostly based on skiplists, which probabilistically create shortcuts in an ordered list for fast insertion of elements. The use of skiplists eliminates the need of global rebalancing in balanced search trees and ensures logarithmic sequential search time on average, but the worst-case performance is linear with respect to the input size. In this paper, we propose a quiescently consistent lock-free priority queue based on a multi-dimensional list that guarantees worst-case search time of O(logN) for key universe of size N. The novel multi-dimensional list (MDList) is composed of nodes that contain multiple links to child nodes arranged by their dimensionality. The insertion operation works by first injectively mapping the scalar key to a high-dimensional vector, then uniquely locating the target position by using the vector as coordinates. Nodes in MDList are ordered by their coordinate prefixes and the ordering property of the data structure is readily maintained during insertion without rebalancing nor randomization. In our experimental evaluation using a micro-benchmark, our priority queue achieves an average of 50 percent speedup over the state of the art approaches under high concurrency.