PIM-trie: A Skew-resistant Trie for Processing-in-Memory
PIM-trie: A Skew-resistant Trie for Processing-in-Memory
复制标题
DOI：
10.1145/3558481.3591070
复制
发表时间：
2023-06
期刊：
影响因子：
--
通讯作者：
H. Kang;Yiwei Zhao;G. Blelloch;Laxman Dhulipala;Yan Gu;Charles McGuffey;Phillip B. Gibbons
中科院分区：
文献类型：
--
作者：
H. Kang;Yiwei Zhao;G. Blelloch;Laxman Dhulipala;Yan Gu;Charles McGuffey;Phillip B. Gibbons
内存延迟和带宽是设计内存索引的重要瓶颈。内存处理（PIM）是一种新兴的硬件设计方法，它通过在内存模块中嵌入处理器来解决这个问题，从而实现低延迟的内存访问，其聚合带宽与PIM模块的数量线性缩放。尽管最近在PIM系统上进行了基于平衡比较的索引的工作，但由于尝试固有的不平衡形状，为PIM构建有效的尝试仍然是一个开放的挑战。本文介绍了PIM trie，第一批并行的基于基数的PIM系统，提供负载平衡和低通信下的敌对控制的工作负载的索引。我们介绍了特里匹配匹配一批查询特里对压缩数据特里作为一个关键的构建块PIM友好的索引操作。我们的算法结合了（i）基于散列的粗粒度工作分配/消除比较和（ii）逐位比较的细粒度匹配。结合其他技术（元块分解，选择性递归复制，差异化验证），PIM-trie支持LongestCommonPrefix，插入和删除，每批O（logP）通信轮和O（l/w）通信量每个字符串，其中P是PIM模块的数量，l是以位为单位的字符串长度，w是机器字大小。此外，即使在最坏的情况下，工作和通信在模块whp之间也是负载平衡的。
Memory latency and bandwidth are significant bottlenecks in designing in-memory indexes. Processing-in-memory (PIM), an emerging hardware design approach, alleviates this problem by embedding processors in memory modules, enabling low-latency memory access whose aggregated bandwidth scales linearly with the number of PIM modules. Despite recent work in balanced comparison-based indexes on PIM systems, building efficient tries for PIMs remains an open challenge due to tries' inherently unbalanced shape. This paper presents the PIM-trie, the first batch-parallel radix-based index for PIM systems that provides load balance and low communication under adversary-controlled workloads. We introduce trie matching-matching a query trie of a batch against the compressed data trie-as a key building block for PIM-friendly index operations. Our algorithm combines (i) hash-based comparisons for coarse-grained work distribution/elimination and (ii) bit-by-bit comparisons for fine-grained matching. Combined with other techniques (meta-block decomposition, selective recursive replication, differentiated verification), PIM-trie supports LongestCommonPrefix, Insert, and Delete in O(logP) communication rounds per batch and O(l/w) communication volume per string, where P is the number of PIM modules, l is the string length in bits, and w is the machine word size. Moreover, work and communication are load-balanced among modules whp, even under worst-case skew.