---
_id: '8191'
abstract:
- lang: eng
  text: "There has been a significant amount of research on hardware and software
    support for efficient concurrent data structures; yet, the question of how to
    build correct, simple, and scalable data structures has not yet been definitively
    settled. In this paper, we revisit this question from a minimalist perspective,
    and ask: what is the smallest amount of synchronization required for correct and
    efficient concurrent search data structures, and how could this minimal synchronization
    support be provided in hardware?\r\n\r\nTo address these questions, we introduce
    memory tagging, a simple hardware mechanism which enables the programmer to \"tag\"
    a dynamic set of memory locations, at cache-line granularity, and later validate
    whether the memory has been concurrently modified, with the possibility of updating
    one of the underlying locations atomically if validation succeeds. We provide
    several examples showing that this mechanism can enable fast and arguably simple
    concurrent data structure designs, such as lists, binary search trees, balanced
    search trees, range queries, and Software Transactional Memory (STM) implementations.
    We provide an implementation of memory tags in the Graphite multi-core simulator,
    showing that the mechanism can be implemented entirely at the level of L1 cache,
    and that it can enable non-trivial speedups versus existing implementations of
    the above data structures."
article_processing_charge: No
author:
- first_name: Dan-Adrian
  full_name: Alistarh, Dan-Adrian
  id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
  last_name: Alistarh
  orcid: 0000-0003-3650-940X
- first_name: Trevor A
  full_name: Brown, Trevor A
  id: 3569F0A0-F248-11E8-B48F-1D18A9856A87
  last_name: Brown
- first_name: Nandini
  full_name: Singhal, Nandini
  last_name: Singhal
citation:
  ama: 'Alistarh D-A, Brown TA, Singhal N. Memory tagging: Minimalist synchronization
    for scalable concurrent data structures. In: <i>Annual ACM Symposium on Parallelism
    in Algorithms and Architectures</i>. Association for Computing Machinery; 2020:37-49.
    doi:<a href="https://doi.org/10.1145/3350755.3400213">10.1145/3350755.3400213</a>'
  apa: 'Alistarh, D.-A., Brown, T. A., &#38; Singhal, N. (2020). Memory tagging: Minimalist
    synchronization for scalable concurrent data structures. In <i>Annual ACM Symposium
    on Parallelism in Algorithms and Architectures</i> (pp. 37–49). Virtual Event,
    United States: Association for Computing Machinery. <a href="https://doi.org/10.1145/3350755.3400213">https://doi.org/10.1145/3350755.3400213</a>'
  chicago: 'Alistarh, Dan-Adrian, Trevor A Brown, and Nandini Singhal. “Memory Tagging:
    Minimalist Synchronization for Scalable Concurrent Data Structures.” In <i>Annual
    ACM Symposium on Parallelism in Algorithms and Architectures</i>, 37–49. Association
    for Computing Machinery, 2020. <a href="https://doi.org/10.1145/3350755.3400213">https://doi.org/10.1145/3350755.3400213</a>.'
  ieee: 'D.-A. Alistarh, T. A. Brown, and N. Singhal, “Memory tagging: Minimalist
    synchronization for scalable concurrent data structures,” in <i>Annual ACM Symposium
    on Parallelism in Algorithms and Architectures</i>, Virtual Event, United States,
    2020, no. 7, pp. 37–49.'
  ista: 'Alistarh D-A, Brown TA, Singhal N. 2020. Memory tagging: Minimalist synchronization
    for scalable concurrent data structures. Annual ACM Symposium on Parallelism in
    Algorithms and Architectures. SPAA: Symposium on Parallelism in Algorithms and
    Architectures, 37–49.'
  mla: 'Alistarh, Dan-Adrian, et al. “Memory Tagging: Minimalist Synchronization for
    Scalable Concurrent Data Structures.” <i>Annual ACM Symposium on Parallelism in
    Algorithms and Architectures</i>, no. 7, Association for Computing Machinery,
    2020, pp. 37–49, doi:<a href="https://doi.org/10.1145/3350755.3400213">10.1145/3350755.3400213</a>.'
  short: D.-A. Alistarh, T.A. Brown, N. Singhal, in:, Annual ACM Symposium on Parallelism
    in Algorithms and Architectures, Association for Computing Machinery, 2020, pp.
    37–49.
conference:
  end_date: 2020-07-17
  location: Virtual Event, United States
  name: 'SPAA: Symposium on Parallelism in Algorithms and Architectures'
  start_date: 2020-07-15
date_created: 2020-08-02T22:00:58Z
date_published: 2020-07-06T00:00:00Z
date_updated: 2024-02-28T12:56:32Z
day: '06'
department:
- _id: DaAl
doi: 10.1145/3350755.3400213
external_id:
  isi:
  - '000744436200004'
isi: 1
issue: '7'
language:
- iso: eng
month: '07'
oa_version: None
page: 37-49
publication: Annual ACM Symposium on Parallelism in Algorithms and Architectures
publication_identifier:
  isbn:
  - '9781450369350'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Memory tagging: Minimalist synchronization for scalable concurrent data structures'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2020'
...