• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Parallel and Distributed Systems, IEEE Transactions on >A Lock-Free Priority Queue Design Based on Multi-Dimensional Linked Lists
【24h】

A Lock-Free Priority Queue Design Based on Multi-Dimensional Linked Lists

机译：基于多维链表的无锁优先队列设计

获取原文
获取原文并翻译 | 示例
       
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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 for key universe of size . 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 percent speedup over the state of the art approaches under high concurrency.
机译：并发优先级队列的吞吐量对于多处理器应用至关重要，例如离散事件模拟，最佳优先搜索和任务调度。现有的无锁优先级队列主要基于跳过列表，跳过列表有可能在有序列表中创建快捷方式以快速插入元素。使用跳过列表消除了平衡搜索树中全局重新平衡的需要，并确保了平均对数顺序搜索时间，但最坏情况下的性能相对于输入大小是线性的。在本文中，我们提出了一个基于多维列表的静态一致的无锁优先级队列，该队列保证了对于大小为key的宇宙的最坏情况下的搜索时间。新颖的多维列表（MDList）由节点组成，这些节点包含到子节点的多个链接，这些子节点按其维度排列。插入操作的工作方式是：首先将标量键映射到高维向量，然后通过使用向量作为坐标来唯一地定位目标位置。 MDList中的节点按其坐标前缀排序，并且在插入过程中无需重新平衡或随机化即可轻松维护数据结构的排序属性。在我们使用微基准进行的实验评估中，我们的优先级队列在高并发性的情况下达到了比现有方法的平均提速百分比高。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号