Memory tagging: Minimalist synchronization for scalable concurrent data structures

D.-A. Alistarh, T.A. Brown, N. Singhal, in:, Annual ACM Symposium on Parallelism in Algorithms and Architectures, ACM, 2020, pp. 37–49.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English

Scopus indexed
Department
Abstract
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? To 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.
Publishing Year
Date Published
2020-07-06
Proceedings Title
Annual ACM Symposium on Parallelism in Algorithms and Architectures
Issue
7
Page
37-49
Conference
SPAA: Symposium on Parallelism in Algorithms and Architectures
Conference Location
Virtual Event, United States
Conference Date
2020-07-15 – 2020-07-17
IST-REx-ID

Cite this

Alistarh D-A, Brown TA, Singhal N. Memory tagging: Minimalist synchronization for scalable concurrent data structures. In: Annual ACM Symposium on Parallelism in Algorithms and Architectures. ACM; 2020:37-49. doi:10.1145/3350755.3400213
Alistarh, D.-A., Brown, T. A., & Singhal, N. (2020). Memory tagging: Minimalist synchronization for scalable concurrent data structures. In Annual ACM Symposium on Parallelism in Algorithms and Architectures (pp. 37–49). Virtual Event, United States: ACM. https://doi.org/10.1145/3350755.3400213
Alistarh, Dan-Adrian, Trevor A Brown, and Nandini Singhal. “Memory Tagging: Minimalist Synchronization for Scalable Concurrent Data Structures.” In Annual ACM Symposium on Parallelism in Algorithms and Architectures, 37–49. ACM, 2020. https://doi.org/10.1145/3350755.3400213.
D.-A. Alistarh, T. A. Brown, and N. Singhal, “Memory tagging: Minimalist synchronization for scalable concurrent data structures,” in Annual ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, United States, 2020, no. 7, pp. 37–49.
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.
Alistarh, Dan-Adrian, et al. “Memory Tagging: Minimalist Synchronization for Scalable Concurrent Data Structures.” Annual ACM Symposium on Parallelism in Algorithms and Architectures, no. 7, ACM, 2020, pp. 37–49, doi:10.1145/3350755.3400213.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar
ISBN Search