DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2020.4

Efficient Multi-Word Compare and Swap

Authors: Rachid Guerraoui, Alex Kogan, Virendra J. Marathe, and Igor Zablotchi

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract

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.

Cite as

Rachid Guerraoui, Alex Kogan, Virendra J. Marathe, and Igor Zablotchi. Efficient Multi-Word Compare and Swap. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{guerraoui_et_al:LIPIcs.DISC.2020.4,
  author =	{Guerraoui, Rachid and Kogan, Alex and Marathe, Virendra J. and Zablotchi, Igor},
  title =	{{Efficient Multi-Word Compare and Swap}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.4},
  URN =		{urn:nbn:de:0030-drops-130827},
  doi =		{10.4230/LIPIcs.DISC.2020.4},
  annote =	{Keywords: lock-free, multi-word compare-and-swap, persistent memory}
}

Search Results

Documents authored by Kogan, Alex

Efficient Multi-Word Compare and Swap

Abstract

Cite as

Thanks for your feedback!

Could not send message