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.9
URN: urn:nbn:de:0030-drops-79958
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7995/
Go to the corresponding LIPIcs Volume Portal

Brown, Trevor ; Ravi, Srivatsan

Cost of Concurrency in Hybrid Transactional Memory

pdf-format:
LIPIcs-DISC-2017-9.pdf (2 MB)

Abstract

State-of-the-art software transactional memory (STM) implementations achieve good performance by carefully avoiding the overhead of incremental validation (i.e., re-reading previously read data items to avoid inconsistency) while still providing progressiveness (allowing transactional aborts only due to data conflicts). Hardware transactional memory (HTM) implementations promise even better performance, but offer no progress guarantees. Thus, they must be combined with STMs, leading to hybrid TMs (HyTMs) in which hardware transactions must be instrumented (i.e., access metadata) to detect contention with software transactions.

We show that, unlike in progressive STMs, software transactions in progressive HyTMs cannot avoid incremental validation. In fact, this result holds even if hardware transactions can read metadata non-speculatively. We then present opaque HyTM algorithms providing progressiveness for a subset of transactions that are optimal in terms of hardware instrumentation. We explore the concurrency vs. hardware instrumentation vs. software validation trade-offs for these algorithms. Our experiments with Intel and IBM POWER8 HTMs seem to suggest that (i) the cost of concurrency also exists in practice, (ii) it is important to implement HyTMs that provide progressiveness for a maximal set of transactions without incurring high hardware instrumentation overhead or using global contending bottlenecks and (iii) there is no easy way to derive more efficient HyTMs by taking advantage of non-speculative accesses within hardware.

BibTeX - Entry

@InProceedings{brown_et_al:LIPIcs:2017:7995,
  author =	{Trevor Brown and Srivatsan Ravi},
  title =	{{Cost of Concurrency in Hybrid Transactional Memory}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{9:1--9:16},
  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/7995},
  URN =		{urn:nbn:de:0030-drops-79958},
  doi =		{10.4230/LIPIcs.DISC.2017.9},
  annote =	{Keywords: Transactional memory, Lower bounds, Opacity}
}

Keywords: Transactional memory, Lower bounds, Opacity
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