HybriDS: Cache-Conscious Concurrent Data Structures for Near-Memory Processing Architectures
HybriDS: Cache-Conscious Concurrent Data Structures for Near-Memory Processing Architectures
复制标题
DOI：
10.1145/3490148.3538591
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Jiwon Choe;Andrew Crotty;T. Moreshet;Maurice Herlihy;R. I. Bahar
中科院分区：
文献类型：
--
作者：
Jiwon Choe;Andrew Crotty;T. Moreshet;Maurice Herlihy;R. I. Bahar
近年来，存储器访问瓶颈的影响不断增加，带来了近存储器处理（NMP）体系结构的新的兴趣。在这项工作中，我们提出并经验评估混合数据结构，这是并发的数据结构定制设计这些新的NMP架构。我们重点介绍缓存优化的数据结构，如跳跃列表和B+树，它们通常用作联机事务处理（OLTP）系统中的索引结构，以实现基于键的快速查找。这些数据结构是分层的，其中查找开始于少量的顶层节点，并且随着它们沿层次结构向下移动而发散到许多不同的节点路径，使得较高级别中的节点从缓存中受益更多。我们提出的混合数据结构将传统的分层数据结构拆分为由较高级别节点组成的主机管理部分和由其余较低级别节点组成的NMP管理部分，从而保留并进一步增强其常规实现的缓存意识优化。虽然这个想法看起来相对简单，但数据结构的分裂会引发新的同步问题，并且需要仔细实现以确保高并发性和正确性。我们提供了一个混合跳跃列表和混合B+树的实现，我们凭经验评估他们的周期准确的全系统架构模拟器。我们的研究结果表明，混合数据结构有可能提高性能的2倍以上的最先进的并发数据结构相比。
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.