论文阅读-PIM-tree：一种面向内存处理的抗偏移索引

论文名称：PIM-tree: A Skew-resistant Index for Processing-in-Memory

摘要

当今的内存索引性能受到内存延迟/带宽瓶颈的限制。Processing-in-memory (PIM) 是一种新兴的方法，可能通过实现低延迟内存访问，其聚合内存带宽随 PIM 节点数量扩展，来缓解这种瓶颈。然而，在工作负载偏斜的情况下，PIM 系统在最小化节点间通信和实现负载平衡之间存在固有的张力。本文介绍了 PIM-tree，一种针对 PIM 系统的有序索引，它通过在数据和查询中实现加载平衡，实现了低通信成本和高负载平衡。我们的抗偏移索引基于主机 CPU 和 PIM 节点之间的劳动分工，利用各自的优势。我们引入了推-拉搜索，它可以根据工作负载的偏移程度动态地决定是将查询推送到 PIM-tree 节点还是将节点的键拉回到 CPU。结合其他 PIM-friendly 优化（如阴影子树和分块跳表），我们的 PIM-tree 可以为点查询、更新和范围扫描提供高吞吐量、（保证的）低通信成本和（保证的）高负载平衡。我们在最新的UPMEM PIM 系统上实现了 PIM-tree，除了先前提议的 PIM 索引外，该系统具有32个 CPU 核心和 2048 个 PIM 节点。在具有 5 亿个键和 100 万个查询批次的工作负载下，使用 PIM-tree 的吞吐量比两个最佳的先前基于 PIM 的方法高达 69.7× 和 59.1×。据我们所知，这是第一次在真正的 PIM 系统上实现有序索引。

1 引言

CPU 速度和内存速度之间的不匹配（即“内存墙”）使得内存访问成为当今数据密集型应用程序中的主要成本。传统的架构使用多级缓存来减少 CPU 和内存之间的数据移动，但如果应用程序表现出有限的局部性，大多数数据访问仍然由内存服务。这种过度的数据移动会产生巨大的能量成本，并且性能受到高内存延迟和/或有限内存带宽的限制。处理-in-memory (PIM) [25, 30]，也称为近数据处理，正在成为减少昂贵数据移动的关键技术。通过将计算资源集成在内存模块中，PIM 可以使数据密集计算在启用 PIM 的内存模块中执行，而不是将所有数据移动到 CPU 来进行处理。最近的研究表明，对于高数据密度和低缓存局部性的程序，PIM 可以通过减少数据移动来提高性能并降低功耗 [14, 15]。尽管处理-in-memory/processing-in-storage的提议可追溯至至少1970年[29]，包括数据库社区在主动磁盘[26]中的尝试，但由于3D堆叠内存[18, 22]的进步以及最近商业PIM系统原型的可用性[30]，PIM正在成为一种关键技术。典型的利用现代PIM体系结构的应用程序包括神经网络[3, 21, 23, 32]、图形处理[1, 17, 35]、数据库[6, 7]、稀疏矩阵乘法[13, 33]和基因组分析[2, 34]。

PIM 系统通常组织为一个主机（多核）CPU，它将计算任务推送到一组 PIM 模块（增强计算内存模块），并收集结果。因此，需要移动任务描述符和数据，这两个成本之和是 CPU 和 PIM 模块之间的通信成本。主机 CPU 可以是任何商品多核处理器，通常比 PIM 模块内的微小 CPU 更强大。因此，PIM 系统的一个有趣特征是潜在地利用两组资源（CPU 端和 PIM 端）。

在本文中，我们专注于为内存数据设计一种适合 PIM 的有序索引。有序索引（例如 B 树[11]）是数据库/数据存储的支柱组件之一，支持高效的搜索查询、范围扫描、插入和删除。以前针对 PIM [10, 24] 的工作提出了基于范围划分的有序索引：将键空间划分为