HybriDS: Cache-Conscious Concurrent Data Structures for Near-Memory Processing Architectures

Jiwon Choe, Andrew Crotty, Tali Moreshet, Maurice Herlihy, R. Iris Bahar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

In recent years, the ever-increasing impact of memory access bottlenecks has brought forth a renewed interest in near-memory processing (NMP) architectures. In this work, we propose and empirically evaluate hybrid data structures, which are concurrent data structures custom-designed for these new NMP architectures. We focus on cache-optimized data structures, such as skiplists and B+ trees, that are often used as index structures in online transaction processing (OLTP) systems to enable fast key-based lookups. These data structures are hierarchical, where lookups begin at a small number of top-level nodes and diverge to many different node paths as they move down the hierarchy, such that nodes in higher levels benefit more from caching. Our proposed hybrid data structures split traditional hierarchical data structures into a host-managed portion consisting of higher-level nodes and an NMP-managed portion consisting of the remaining lower-level nodes, thus retaining and further enhancing the cache-conscious optimizations of their conventional implementations. Although the idea might seem relatively simple, the splitting of the data structure prompts new synchronization problems, and careful implementation is required to ensure high concurrency and correctness. We provide implementations of a hybrid skiplist and a hybrid B+ tree, and we empirically evaluate them on a cycle-accurate full-system architecture simulator. Our results show that the hybrid data structures have the potential to improve performance by more than 2x compared to state-of-the-art concurrent data structures.

Original languageEnglish (US)
Title of host publicationSPAA 2022 - Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures
PublisherAssociation for Computing Machinery
Pages321-332
Number of pages12
ISBN (Electronic)9781450391467
DOIs
StatePublished - Jul 11 2022
Event34th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2022 - Philadelphia, United States
Duration: Jul 11 2022Jul 14 2022

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures

Conference

Conference34th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2022
Country/TerritoryUnited States
CityPhiladelphia
Period7/11/227/14/22

Funding

We thank the anonymous reviewers for their helpful comments. This work was supported by NSF grant 1909715.

Keywords

  • concurrent data structures
  • near-memory processing

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'HybriDS: Cache-Conscious Concurrent Data Structures for Near-Memory Processing Architectures'. Together they form a unique fingerprint.

Cite this