1 Search Results for "Arbel-Raviv, Maya"

Document
DOI: 10.4230/LIPIcs.DISC.2017.4
Reuse, Don't Recycle: Transforming Lock-Free Algorithms That Throw Away Descriptors

Authors: Maya Arbel-Raviv and Trevor Brown

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
In many lock-free algorithms, threads help one another, and each operation creates a descriptor that describes how other threads should help it. Allocating and reclaiming descriptors introduces significant space and time overhead. We introduce the first descriptor abstract data type (ADT), which captures the usage of descriptors by lock-free algorithms. We then develop a weak descriptor ADT which has weaker semantics, but can be implemented significantly more efficiently. We show how a large class of lock-free algorithms can be transformed to use weak descriptors, and demonstrate our technique by transforming several algorithms, including the leading k-compare-and-swap (k-CAS) algorithm. The original k-CAS algorithm allocates at least k+1 new descriptors per k-CAS. In contrast, our implementation allocates two descriptors per process, and each process simply reuses its two descriptors. Experiments on a variety of workloads show significant performance improvements over implementations that reclaim descriptors, and reductions of up to three orders of magnitude in peak memory usage.
Cite as

Maya Arbel-Raviv and Trevor Brown. Reuse, Don't Recycle: Transforming Lock-Free Algorithms That Throw Away Descriptors. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{arbelraviv_et_al:LIPIcs.DISC.2017.4,
  author =	{Arbel-Raviv, Maya and Brown, Trevor},
  title =	{{Reuse, Don't Recycle: Transforming Lock-Free Algorithms That Throw Away Descriptors}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.4},
  URN =		{urn:nbn:de:0030-drops-80092},
  doi =		{10.4230/LIPIcs.DISC.2017.4},
  annote =	{Keywords: Concurrency, data structures, lock-free, synchronization, descriptors}
}
  • Refine by Author
  • 1 Arbel-Raviv, Maya
  • 1 Brown, Trevor

  • Refine by Classification

  • Refine by Keyword
  • 1 Concurrency
  • 1 data structures
  • 1 descriptors
  • 1 lock-free
  • 1 synchronization

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact