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.2017.53
URN: urn:nbn:de:0030-drops-80201
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8020/
Gelashvili, Rati ;
Keidar, Idit ;
Spiegelman, Alexander ;
Wattenhofer, Roger
Brief Announcement: Towards Reduced Instruction Sets for Synchronization
Abstract
Contrary to common belief, a recent work by Ellen, Gelashvili, Shavit, and Zhu has shown that computability does not require multicore architectures to support "strong" synchronization instructions like compare-and-swap, as opposed to combinations of "weaker" instructions like decrement and multiply. However, this is the status quo, and in turn, most efficient concurrent data-structures heavily rely on compare-and-swap (e.g. for swinging pointers).
We show that this need not be the case, by designing and implementing a concurrent linearizable Log data-structure (also known as a History object), supporting two operations: append(item), which appends the item to the log, and get-log(), which returns the appended items so far, in order. Readers are wait-free and writers are lock-free, hence this data-structure can be used in a lock-free universal construction to implement any concurrent object with a given sequential specification. Our implementation uses atomic read, xor, decrement, and fetch-and-increment instructions supported on X86 architectures, and provides similar performance to a compare-and-swap-based solution on today's hardware. This raises a fundamental question about minimal set of synchronization instructions that the architectures have to support.
BibTeX - Entry
@InProceedings{gelashvili_et_al:LIPIcs:2017:8020,
author = {Rati Gelashvili and Idit Keidar and Alexander Spiegelman and Roger Wattenhofer},
title = {{Brief Announcement: Towards Reduced Instruction Sets for Synchronization}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {53:1--53:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Andr{\'e}a W. Richa},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8020},
URN = {urn:nbn:de:0030-drops-80201},
doi = {10.4230/LIPIcs.DISC.2017.53},
annote = {Keywords: Consensus hierarchy, universal construction, synchronization instruction.}
}
Keywords: |
|
Consensus hierarchy, universal construction, synchronization instruction. |
Collection: |
|
31st International Symposium on Distributed Computing (DISC 2017) |
Issue Date: |
|
2017 |
Date of publication: |
|
12.10.2017 |