Efficient Multi-word Compare and Swap
Efficient Multi-word Compare and Swap
复制标题
高效的多字比较和交换
DOI：
10.4230/lipics.disc.2020.4
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
I. Zablotchi
中科院分区：
文献类型：
--
作者：
R. Guerraoui;Alex Kogan;Virendra J. Marathe;I. Zablotchi
原子无锁多字比较交换（MCAS）是设计并发算法的一个有力工具。然而，它的广泛使用受到限制，因为MCAS的无锁实现大量使用昂贵的比较和交换（CAS）指令。现有的MCAS实现实际上每个k-CAS使用至少2k+1个CAS。这就导致了最大限度地减少实现MCAS所需的CAS数量的自然愿望。我们首先证明，在本文中，它是不可能的“包装”所需的信息，以执行一个K字CAS（K-CAS）在少于K个位置进行CAS。然后，我们提出了第一个算法，需要k+1个CAS每次调用k-CAS在常见的无竞争的情况下。我们实现了我们的算法，并表明它在大多数考虑的工作负载中的各种基准测试中优于最先进的基线。我们还提出了一个持久的线性化（持久内存友好）的版本，我们的MCAS算法，每次调用只使用2个持久性围栏，同时仍然只需要k+1个CAS每个k-CAS。
Atomic lock-free multi-word compare-and-swap (MCAS) is a powerful tool for designing concurrent algorithms. Yet, its widespread usage has been limited because lock-free implementations of MCAS make heavy use of expensive compare-and-swap (CAS) instructions. Existing MCAS implementations indeed use at least 2k+1 CASes per k-CAS. This leads to the natural desire to minimize the number of CASes required to implement MCAS. We first prove in this paper that it is impossible to "pack" the information required to perform a k-word CAS (k-CAS) in less than k locations to be CASed. Then we present the first algorithm that requires k+1 CASes per call to k-CAS in the common uncontended case. We implement our algorithm and show that it outperforms a state-of-the-art baseline in a variety of benchmarks in most considered workloads. We also present a durably linearizable (persistent memory friendly) version of our MCAS algorithm using only 2 persistence fences per call, while still only requiring k+1 CASes per k-CAS.
基于间隔的内存回收
DOI：
10.1145/3178487.3178488
发表时间：
2018
期刊：
Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
影响因子：
--
作者：
Wen, Haosen;Izraelevitz, Joseph;Cai, Wentao;Beadle, H. Alan;Scott, Michael L.
通讯作者：
Scott, Michael L.