License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2020.5
URN: urn:nbn:de:0030-drops-130831
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13083/
Blelloch, Guy E. ;
Wei, Yuanhao
LL/SC and Atomic Copy: Constant Time, Space Efficient Implementations Using Only Pointer-Width CAS
Abstract
When designing concurrent algorithms, Load-Link/Store-Conditional (LL/SC) is a very useful primitive since it avoids ABA problems. The full semantics of LL/SC are not supported in hardware by any modern architecture, so there has been a significant amount of work on simulations of LL/SC using CAS. However, all previous algorithms that are constant time either use unbounded sequence numbers (and thus base objects of unbounded size), or require Ω(MP) space to implement M LL/SC objects for P processes.
We present the first constant time implementation of LL/SC from bounded-sized CAS objects using only constant space overhead per LL/SC variable. In particular, our implementation uses Θ(M+kP²) space, where k is the number of outstanding LL operations per process, and only requires pointer-width CAS operations. In most algorithms that use LL/SC, k is a small constant which reduces our additive space overhead to Θ(P²). Our algorithm can also be extended to implement L word LL/SC objects in Θ(L) time for LL and SC, O(1) time for VL, and Θ((M+kP²)L) space.
To achieve these bounds, our main technical contribution is implementing a new primitive called Single-Writer Copy which takes a pointer to a word sized memory location and atomically copies its contents into another object. The restriction is that only one process is allowed to write/copy into the destination object at a time. The ability to read from one memory location and write to another atomically, and in constant-time, is very powerful and we believe this primitive will be useful in designing other algorithms.
BibTeX - Entry
@InProceedings{blelloch_et_al:LIPIcs:2020:13083,
author = {Guy E. Blelloch and Yuanhao Wei},
title = {{LL/SC and Atomic Copy: Constant Time, Space Efficient Implementations Using Only Pointer-Width CAS}},
booktitle = {34th International Symposium on Distributed Computing (DISC 2020)},
pages = {5:1--5:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-168-9},
ISSN = {1868-8969},
year = {2020},
volume = {179},
editor = {Hagit Attiya},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13083},
URN = {urn:nbn:de:0030-drops-130831},
doi = {10.4230/LIPIcs.DISC.2020.5},
annote = {Keywords: LL/SC, Atomic Copy, CAS, Constant Time}
}
|
Keywords: |
|
LL/SC, Atomic Copy, CAS, Constant Time |
|
Collection: |
|
34th International Symposium on Distributed Computing (DISC 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
07.10.2020 |
