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 language | English (US) |
---|---|
Title of host publication | SPAA 2022 - Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures |
Publisher | Association for Computing Machinery |
Pages | 321-332 |
Number of pages | 12 |
ISBN (Electronic) | 9781450391467 |
DOIs | |
State | Published - Jul 11 2022 |
Event | 34th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2022 - Philadelphia, United States Duration: Jul 11 2022 → Jul 14 2022 |
Publication series
Name | Annual ACM Symposium on Parallelism in Algorithms and Architectures |
---|
Conference
Conference | 34th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2022 |
---|---|
Country/Territory | United States |
City | Philadelphia |
Period | 7/11/22 → 7/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