Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Efficient Multi-Word Compare and Swap
 
conference paper

Efficient Multi-Word Compare and Swap

Guerraoui, Rachid  
•
Kogan, Alex
•
Marathe, Virendra J.
Show more
October 7, 2020
Proceedings of the 34th International Symposium on Distributed Computing (DISC 2020)
34th International Symposium on Distributed Computing (DISC 2020)

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.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.4230/LIPIcs.DISC.2020.4
Author(s)
Guerraoui, Rachid  
Kogan, Alex
Marathe, Virendra J.
Zablotchi, Mihail Igor  
Date Issued

2020-10-07

Publisher

Schloss Dagstuhl, Leibniz-Zentrum

Publisher place

Dagstuhl

Published in
Proceedings of the 34th International Symposium on Distributed Computing (DISC 2020)
ISBN of the book

978-3-959771-68-9

Series title/Series vol.

Leibniz International Proceedings in Informatics (LIPIcs)

Subjects

lock-free

•

multi-word compare-and-swap

•

persistent memory

Note

Licensed under Creative Commons License CC-BY.

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCL  
Event nameEvent date
34th International Symposium on Distributed Computing (DISC 2020)

October 12-16, 2020

Available on Infoscience
October 7, 2020
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/172273
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés