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/
Go to the corresponding LIPIcs Volume Portal

Gelashvili, Rati ; Keidar, Idit ; Spiegelman, Alexander ; Wattenhofer, Roger

Brief Announcement: Towards Reduced Instruction Sets for Synchronization

pdf-format:
LIPIcs-DISC-2017-53.pdf (0.4 MB)

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI