MultiQueue：一种简单且快速的松弛并发优先队列

《ACM Transactions on Parallel Computing》：The MultiQueue: A Simple and Fast Relaxed Concurrent Priority Queue

优先队列在并行环境中常成为性能瓶颈，本文提出基于wait-free锁定技术的多队列结构MultiQueue，通过多内部队列协同和元素缓冲优化提升吞吐量。实验表明其质量-吞吐量权衡优于现有方案，支持灵活配置。

　　

摘要

优先队列在各种应用中都有广泛的使用，包括优先在线调度、离散事件模拟和贪心算法。在并行环境中，传统的优先队列往往成为性能瓶颈，导致吞吐量较低。因此，人们对具有宽松语义的并发优先队列产生了浓厚的兴趣。

在本文中，我们介绍了MultiQueue，这是一种高度可扩展且灵活的宽松优先队列。其设计基于利用“无等待锁定”这一看似矛盾的技术来实现多个内部优先队列的协同工作。通过元素缓冲、对内部队列进行批量操作以及优化缓存访问模式，进一步提升了MultiQueue的实际性能。

我们将MultiQueue与现有的最先进竞争方案进行了吞吐量与性能质量的对比评估。性能质量通过两个互补的指标来衡量：排名误差（被删除元素与最佳元素之间的距离）和延迟（在给定元素之前被删除的较低优先级元素的数量）。在微观基准测试以及基于实际应用的基准测试（如最短路径问题和分支定界法）中，大量实验表明MultiQueue始终优于其竞争对手。此外，其设计允许用户轻松调整吞吐量和性能质量之间的平衡，以满足特定应用的需求。我们认为，“无等待锁定”技术对于将顺序数据结构转换为高性能的并发数据结构具有更广泛的应用价值。