A skip list for multicore
A skip list for multicore
复制标题
多核的跳过列表
DOI：
10.1002/cpe.3876
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Vincent Gramoli
中科院分区：
文献类型：
--
作者：
Ian Dick;A. Fekete;Vincent Gramoli
在本文中，我们介绍了旋转跳表，目前最快的并发跳表。现有的并发数据结构在核心数量不断增长的情况下可扩展性有限，这主要有两个原因：线程在访问相同的共享数据时会发生竞争，并且它们需要片外通信来同步。我们的解决方案结合了树的旋转来确定性地保持对数复杂度，跳跃列表结构来避免树根瓶颈，并且没有锁来限制缓存线反弹。这种组合要求我们将通常的跳表塔换成轮子，这是一种新颖的算法设计，有利于空间局部性，并允许恒定时间的重组操作。我们在AMD Opteron和Intel Xeon多核上评估了我们的跳表的性能，表明其旋转保证了其平衡，并使用四种不同的同步技术将其性能与七种最先进的跳表和树进行了比较。旋转跳跃列表显示了前所未有的峰值性能200 Mops/秒。版权所有© 2016约翰威利父子有限公司.
In this paper, we introduce the Rotating skip list, the fastest concurrent skip list to date. Existing concurrent data structures experience limited scalability with the growing core count for two main reasons: threads contend while accessing the same shared data, and they require off‐chip communication to synchronize. Our solution combines the rotation of a tree to maintain logarithmic complexity deterministically, a skip list structure to avoid the tree root bottleneck, and no locks to limit cache line bouncing. This combination requires us to trade usual skip list towers for wheels, a novel algorithmic design that favors spatial locality and allows for a constant‐time restructuring operation. We evaluate the performance of our skip list on AMD Opteron and Intel Xeon multicores, show that its rotations guarantee its balance and compare its performance against seven state‐of‐the‐art skip lists and trees using four different synchronisation techniques. The Rotating skip list shows an unprecedented peak performance of 200 Mops/second. Copyright © 2016 John Wiley & Sons, Ltd.