论文名称：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] 的工作提出了基于范围划分的有序索引：将键空间划分为 𝑃 个相等键数的子范围，每个 𝑃 PIM 模块存储一个子范围。每个 PIM 模块在其子范围内维护一个本地索引，而主机 CPU 则维护索引顶部直到局部索引的 𝑃 个根。这种方法适用于具有均匀随机键的数据和查询，即这些工作所研究的设置，但在数据或查询偏斜下容易出现负载不平衡。在更实际的工作负载中，查询/更新批次可能集中在少量分区的数据上，压倒了这些 PIM 模块，而其他模块处于空闲状态。在极端情况下，只有一个 PIM 模块处理查询，其余的模块处于空闲状态，在单个（微弱的）处理器上完全串行化整个查询批次。该方法还需要为保持分区（大致）平衡的所有数据移动付出代价。在最近的一篇论文[19]中，我们设计了一种 PIM-friendly 跳表，它在渐进意义下实现了负载平衡（详见第2.4节），但该解决方案不实用（如下所述）。

为了解决查询和数据偏斜的挑战，我们提出了 PIM-tree，一种实用的面向 PIM 的有序索引，它可以实现在数据和查询的任何偏斜程度下实现低通信成本和高负载平衡。我们的抗偏移索引基于主机 CPU 和 PIM 节点之间的新颖劳动分工，利用各自的优势。此外，它结合了 B+-树和跳表的特点来实现其目标。我们专注于以批处理同步的方式实现高吞吐量，处理查询批次。PIM-tree 支持广泛的批并行操作，包括点查询（Get，Predecessor）、更新（Insert，Delete）和范围扫描。

2 背景

2.1 PIM 系统架构和模型

处理内存中的模型。我们使用处理内存中的模型（PIM Model）（首次描述于[19]）作为通用 PIM 系统的抽象。它包括一个主机 CPU 前端（CPU 侧）和一组 𝑃 个 PIM 模块（PIM 侧）。CPU 侧是一个标准的多核处理器，具有 𝑀 个字的片上缓存。每个 PIM 模块由一个 DRAM 存储器（本地 PIM 存储器）、一台片上处理器（PIM 处理器）和 Θ(𝑛/𝑃) 个字的本地存储器（其中 𝑛 表示问题的规模）组成。PIM 处理器简单但通用（例如，能够运行 C 代码的单一按顺序核心）。主机 CPU 可以向 PIM 模块发送代码、启动代码，并检测代码完成的情况。它还可以向 PIM 存储器发送数据并接收来自 PIM 存储器的数据。该模型假设没有直接的 PIM 对 PIM 通信，尽管在支持此类通信的 PIM 系统上我们可以利用这种通信。

由于 PIM 模型结合了共享内存侧（CPU 和其缓存）和分布式侧（PIM 模块），因此算法使用共享内存指标（工作量、深度）和分布式指标（本地工作量、通信时间）进行分析。在 CPU 侧，该模型考虑了 CPU 工作量（所有核心的总工作量）和 CPU 深度（关键路径上的所有工作）。在 PIM 侧，该模型考虑了 PIM 时间，即任一 PIM 核上的最大本地工作量，以及 IO 时间，即任一 PIM 模块发送/接收的最大消息数。程序以批量同步轮次执行[31]，算法的整体复杂度指标是每一轮复杂度指标的总和。本文重点关注 IO 时间和 IO 轮次。

编程接口。为了具体起见，我们假设了我们通用 PIM 系统的以下编程接口，尽管我们的技术也可以与其他接口一起使用。程序由两部分组成：在主机 CPU 上执行的主机程序和在 PIM 模块上执行的 PIM 程序。主机程序具有附加功能（下文讨论），用于与 PIM 侧进行通信，包括调用 PIM 模块上的 PIM 程序和向 PIM 模块传输数据/从 PIM 模块接收数据的功能。PIM 程序是一个传统程序，在由主机程序启动时在所有 PIM 处理器上执行。它使用模块的本地存储器执行，对 CPU 侧或其他 PIM 模块没有可见性。具体函数为（命名为 MPI 风格[16]）：

• PIM_Load(PIM_Program_Binary)：将二进制文件加载到 PIM 模块。
• PIM_Launch()：在所有 PIM 上启动加载的 PIM 程序。
• PIM_Status()：检查 PIM 程序在所有 PIM 上是否已完成。
• PIM_Broadcast(src, length, PIM_Local_Address)：将固定长度的缓冲区复制到每个 PIM 的相同本地存储器地址。
• PIM_Scatter(srcs[], length[], PIM_Local_Address)：类似于 PIM_Broadcast，但每个 PIM 模块都有一个独立的缓冲区。 
• PIM_Gather(dsts[], length[], PIM_Local_Address)：与 PIM_Scatter 的相反操作，将读入缓冲区数组 dsts[]。

基于这个接口，我们的 PIM-friendly 有序索引以批量同步轮次处理操作批，如[28]中的步骤一样，使用算法1中的步骤。如第5节所讨论的，当实现我们的 PIM-friendly 程序时，我们使用流水线技术重叠 CPU 的步骤1和 PIM 模块的步骤3。

具体案例：UPMEM。我们在 UPMEM 的最新 PIM 系统[30]上评估了我们的技术。UPMEM 的架构（图1）是实例化 PIM 模型的一种方式。它的 PIM 模块是即插即用的 DRAM DIMM 替代品，因此可以配置为各种传统 DRAM 存储器和 PIM 设备的比例（目前最大可用配置有2560个 PIM 模块）。CPU 可以访问主存储器（传统 DRAM）和所有 PIM 存储器，但每个 PIM 处理器只能访问其本地存储器。每个 PIM 模块具有高达628 MB/s的本地 DRAM 带宽，因此配备2560个 PIM 模块的机器可以提供高达1.6 TB/s的总带宽[15]。为了在 PIM 模块之间传输数据，CPU 从源读取并写入目标。UPMEM 的 SDK 支持上述编程接口函数，但有一个限制，即散射/聚集函数必须传输相同长度的缓冲区到/从所有 PIM 模块（即，缓冲区被填充到相等长度）。UPMEM 的主存储器（PIM 模型中没有的一个组件）能够运行具有 CPU 侧内存占用超过 𝑀 个字的程序，但这些额外的内存访问带来了另一种类型的通信，即在 PIM 模型中不存在的 CPU-DRAM 通信。因此，对于主机程序来说，缓存效率非常重要。我们在 PIM-tree 中的解决方案是仅使用少量的 CPU 侧内存：Θ(𝑆) < 𝑀 个字，用于 𝑆 个操作的批处理。

UPMEM PIM系统的架构，这是我们通用PIM系统架构的一个具体例子。PIM模块被打包到通过普通内存通道连接到主机CPU的内存内存中。CPU端还包括传统的DRAM模块，这不是PIM模型的一部分。

2.2 负载平衡初步 PIM

系统面临的主要挑战之一是保持 PIM 模块之间的负载平衡，我们将其定义如下：

定义 2.1. 如果每个 PIM 程序执行的工作量（单位时间指令）为𝑂(𝑊 /𝑃)，并且每个 PIM 模块发送/接收的通信量为 𝑂(𝐶/𝑃)，则程序实现了负载平衡，其中 𝑊 和 𝐶 分别是所有𝑃个 PIM 模块的工作量和通信的总和。对于具有多个批量同步轮次的程序，如果每个轮次都实现了负载平衡，则程序实现了负载平衡。

实现负载平衡的挑战在于必须限制具有最大工作量或通信的 PIM 模块。需要注意的是，随机化并不直接导致负载平衡，例如，对相等工作量和通信的𝑃个任务进行随机散布到𝑃个 PIM 模块不能实现负载平衡。这是因为其中一个 PIM 模块在𝑃 [5]中以很高的概率接收 Θ(log 𝑃/log log 𝑃) 个任务，导致该模块的工作量和通信量是平衡量的 Θ(log 𝑃/log log 𝑃) 倍。

我们使用“球进箱子引理”来证明负载平衡，其中箱子是一个 PIM 模块，权重为𝑤的球对应于具有𝑤工作量或𝑤通信的任务。我们将使用以下引理：

引理 2.2 ([19, 27])。将总重量为𝑊 = 且每个𝑤𝑖 < 𝑊 /(𝑃 log 𝑃)的加权球均匀随机地放入𝑃个箱子中，则每个箱子中的重量均为𝑂(𝑊 /𝑃)，几乎肯定发生。

2.3 PIM 上索引的先前工作

有几项关于 PIM 系统上索引的先前工作。两项先前工作[10, 24]提出了 PIM-friendly 跳表。它们的跳表基于范围划分：它们通过不相交的键范围对跳表进行划分，并在每个部分上本地维护一个 PIM 模块。如第1节所述，这种范围划分在数据和查询倾斜的情况下可能会遇到严重的负载不平衡问题。

范围划分有序索引的负载不平衡问题在传统的分布式环境中也受到研究。Ziegler 等人[36]讨论了其他选择的基于树状有序索引，以避免负载不平衡问题，其中包括：(i) 按键的哈希值进行划分，(ii) 随机分布所有索引节点的精细划分，(iii) 在叶子节点进行精细划分，在内部节点进行范围划分的混合方法。他们还在一个8台机器的集群上进行了实验评估。然而，在具有数千个 PIM 模块的 PIM 系统中，这些选择每一种都在某种程度上存在问题：(i) 通过哈希进行划分会使范围操作成本增加，因为它们必须由所有 PIM 模块处理，(ii) 精细划分会导致太多的通信，因为所有访问都将是非本地的，(iii) 混合方法在其范围划分部分存在负载平衡问题。

2.4 先前工作：PIM 平衡跳表

最近的一篇论文[19]中，我们提出了第一个在 PIM 模型下对敌控工作负载具有可证明的负载平衡的批处理并行跳表索引，即 PIM 平衡跳表。一个关键的洞察是利用 CPU 端来解决负载平衡问题。PIM 平衡跳表将跳表水平分割为两部分，一个上部和一个下部，将上部在所有 PIM 模块中复制，并将下部节点随机分配给 PIM。如图 2 所示，不同 PIM 模块中的节点具有不同的颜色，复制的上部部分明确地绘制为多个副本。对于一个具有 𝑃 个 PIM 模块的系统，下部为 log 𝑃 层。我们可以复制（仅）顶部部分，因为 (i) 相对于跳表的其余部分来说它很小，而且 (ii) 它相对不经常更新（回忆一下，在跳表中插入关键字到达高度 ℎ 的概率为 1/2^ℎ）。

在一个4个PIM模块的系统上，使用上部部分复制的PIM平衡跳表[19]。不同PIM模块上的节点是不同的颜色。PIM指针为虚线。下部分是log𝑃层。

查询通过在跳表节点“树”中进行指针追踪来执行。首先将批处理的查询均匀分成若干份发送到所有 PIM 模块，每个模块在本地处理上部部分。然后跳表通过将查询逐个发送到搜索路径上每个下部节点的主机 PIM 模块来处理下部部分，直到达到叶子节点。我们称之为推送方法，因为查询被“推送”到 PIM 模块来执行。

仅使用推送执行一批并行查询可能导致严重的不平衡，尽管下部节点是随机分布的。对于倾斜的工作负载，许多查询可能共享搜索路径上的一个通用节点，这意味着它们都被发送到该节点的主机 PIM 模块，导致负载不平衡。这些节点被称为争用点。一个例子是当多个非重复的 Predecessor 查询返回相同的关键字时，搜索路径上的所有节点都成为争用点。

PIM 平衡跳表[19]通过避免争用点来解决这个问题，基于一个关键观察：一旦关键字 𝑙 和 𝑟 的搜索路径共享下部节点 𝑣，搜索任何关键字 𝑢 ∈ [𝑙, 𝑟] 也会到达节点 𝑣。因此，对于 𝑢 的搜索可以直接从这两个路径的最低公共祖先（LCA）开始。我们称之为跳推方法。跳推搜索具有一个预处理阶段来记录搜索路径。它是一个多轮样本搜索，从一个样本开始：在每一轮中，它将样本大小加倍，并使用前几轮记录的搜索路径来决定本轮样本查询的起始节点。这种方法限制了每个节点上的争用，并避免了负载不平衡。

然而，预处理成本很高。对于𝑃个 PIM 模块和一个批量为 𝑃 log2𝑃 的操作，需要 𝑂(log 𝑃) 个采样轮次，每个轮次需要 𝑂(log 𝑃) 步的模块间指针追踪来搜索下部部分。相比之下，主要阶段只需要 𝑂(log 𝑃) 步。此外，预处理阶段需要记录整个搜索路径，这也是 CPU 端的另一个开销。 我们的新有序索引（PIM 树）使用了与这项工作相同的一些思想，但包括了关键的新思想，使其在理论上和实践上更简单、更高效。

3 PIM-树设计

概述。PIM-树是为 PIM 系统设计的批处理并行抗倾斜有序索引。它支持基本的键-值操作，包括 Get(key)、Update(key, value)、Predecessor(key)、Insert(key, value)、Delete(key) 和 Scan(Lkey, Rkey)。它以相同类型的原子批次并行执行操作，类似于[28]。因此，该数据结构避免了不同类型操作引起的冲突。我们从 §2.4 中讨论的结构开始设计它。

在本节中，我们通过研究我们的技术/优化对 Predecessor 操作的影响来描述 PIM-树的设计。我们详细回顾了 §2.4 中讨论的基本数据结构设计，然后介绍我们的三个关键技术/优化，并最终分析由此产生的通信成本和负载平衡。稍后在第 4 节中，我们将描述 PIM-树的其他操作的设计。

符号。我们将 PIM 模块数量表示为 𝑃，索引中元素的总数表示为 𝑛，批处理大小表示为 𝑆，PIM-树节点的预期分支度表示为 𝐵。 关键思想。我们观察到 PIM 架构的两个组成部分，即 CPU 端和 PIM 端，偏好不同的工作负载。分布式的 PIM 端偏好均匀随机的工作负载，并且受到高度倾斜工作负载引起的负载不平衡的影响。与此同时，共享的 CPU 端偏好倾斜的工作负载，因为我们可以在这些工作负载中探索空间和时间的局部性，从而实现更好的缓存效率。这种差异显示了共享内存计算和分布式计算的互补性，以及它们在 PIM 架构中的共存激发了我们的混合方法：我们设计了一种动态劳动分工策略，自动在 CPU 端和 PIM 端之间切换使用更理想的平台。这种策略称为推拉搜索，是 PIM-树的核心技术。

通过推拉搜索实现负载平衡后，我们进一步提出了另外两种优化，称为影子子树和分块，以减少通信。这些优化分别由两个基本思想驱动：在 PIM 模块上缓存远程访问以构建本地快捷方式（从而消除通信），以及将节点分块（以获得更好的局部性）。我们将展示这些“传统”技术如何与推拉搜索优化相结合，将通信的渐近降低从𝑂(log 𝑃) 降低到 𝑂(log𝐵 log𝐵 𝑃)（𝐵 是分块节点的预期分支度），并且吞吐量增加高达 69.7 倍，与 §2.4 的 PIM 友好型跳表相比。

3.1 基本结构 PIM

PIM 平衡跳跃表是一种分布式跳跃表，水平地分成三个部分：上部、下部和数据节点（图 2）。数据节点是随机分布到 PIM 模块的键值对，以支持基于哈希的一轮查找和𝑂(1) 通信。每个上部节点都在所有 PIM 模块中进行复制，每个下部节点都存储在一个随机的 PIM 模块中。托远指针称为 PIM 指针，由（PIM ID，地址）对组成。图 2 中，PIM 指针由虚线箭头表示，而传统的（即 intra-PIM）指针则由实线箭头表示。为了在搜索过程中节省通信量，每个下部节点都存储相同层级的下一个跳跃表节点的键（称为右键）。每个键都有一个在最低层的节点，并且一个节点加入跳跃表下一个更高层次的概率被设置为 1/2。上部被复制以便在 PIM 模块上进行本地查询，但是复制带来了𝑃的开销，同时也增加了空间复杂性和更新成本。为了减轻这种开销，下部高度被设置为 𝐻low = log 𝑃，这样只有 1/2log 𝑃 = 1/𝑃 的键才会到达上部。通过复制上部，Predecessor 查询所需的远程访问次数从 𝑂(log𝑛) 降低到 𝑂(log 𝑃)。

在接下来的章节中，我们称上部为 L3，下部为 L2。在应用阴影子树优化（§3.3）后，我们将进一步将下部水平分成两部分，称为 L2 和 L1。

3.2 推拉搜索

推拉搜索是我们提出的搜索方法，它可以在工作负载不均衡的情况下保证负载平衡。在推方法中，CPU 将查询发送到沿着搜索路径的下一个节点的主机 PIM 模块，PIM 模块运行查询，然后 CPU 拉取结果；在拉方法中，CPU 检索沿路径的下一个节点返回到 CPU 端，自己运行查询。推拉搜索通过计算每个节点的查询数量来选择推或拉：当对一个节点的查询数量超过特定阈值（以下称为 𝐾）时，选择拉，否则推。 更具体地说，推拉搜索在三个阶段内对 §3.1 中提到的基本结构执行多轮指针跟踪，其中 CPU 在整个过程中将每个查询的下一个指针记录为 PIM 指针数组。

1. 使用复制的上部遍历 L3。CPU 平均分配查询给 PIM 模块。每个 PIM 模块使用其本地副本运行其查询，直到到达 L2 节点的指针。CPU 检索这些指针（使用 PIM_Gather）。
2. 使用感知竞争的推拉遍历 L2。CPU 执行多个推拉轮。在每一轮中，CPU 计算在每个 L2 节点上的查询数量。如果对一个节点的查询超过了 𝐾，则选择拉，通过向 PIM 端发送任务将该节点检索到 CPU 端，然后根据检索到的节点的指针在 CPU 端上并行地根据 PIM IDs 对查询进行分区。否则，选择推，向 PIM 发送查询任务并检索查询的下一个指针。
3. 当搜索到达数据节点时，返回数据。

我们可以记录 CPU 端查询路径上所有节点的地址，以获取每个查询的搜索跟踪。请注意，在执行更新时（在 §4 中），将使用这些跟踪。对于§3.1中提到的基本结构，我们选择 𝐾 = 1，因为它可以最小化大小恒定的节点的通信量。

讨论。推拉搜索最有趣的部分是它基于集成分布式计算和共享内存计算两种基本方法来实现可证明的负载平衡和低成本（见§3.5分析）。我们观察到推方法是一种分布式计算技术，因为它使用 CPU 作为路由器并始终在 PIM 模块上运行查询。同时，拉方法是一种共享内存技术，将 PIM 模块视为标准内存模块，并在 CPU 上运行查询。正如 §3 中所讨论的，将这两种基本方法相结合起来是有效的，因为 CPU 端和 PIM 端在负载平衡问题上具有互补性：引起争用的工作负载（因此不适合 PIM）与友好的 CPU 工作负载同时存在。作为解决负载平衡问题的解决方案，推拉搜索在最坏情况下的边界与仅采用推或拉方法相比没有渐近改进。我们的优化，阴影子树和分块，提供了这样的改进，我们将在接下来介绍。

3.3 影子子树

影子子树是L2中的辅助数据结构，作为快捷方式来缩短每个查询的通信从𝑂(log 𝑃)到𝑂(log log 𝑃)，同时确保空间复杂度仍为𝑂(𝑛)。影子子树优化基于跳表定义的搜索树的思想，跳表是由合并跳表的所有可能搜索路径生成的虚拟树。它包含跳表的所有节点和所有边缘，除了一些水平边缘。每个节点的影子子树是存储在该节点中的其搜索子树的影子副本。通过使用影子子树，PIM模块可以通过L2本地运行查询。虽然影子子树和复制树的顶部都涉及将节点在不同的PIM模块之间复制以减少通信，但它们实际上是非常不同的。当复制顶部时，单个树被复制𝑃次穿过模块。在影子子树中，每个节点的每个祖先都有该节点的副本作为其影子子树的一部分（在我们的情况下仅在L2中的祖先）。

在所有（𝑂(𝑛)) L2节点上构建影子子树将需要𝑂(𝑛 log 𝑃)的空间。为了保持𝑂(𝑛)的空间，我们仅在一小部分L2节点上构建它们。特别地，我们将L2分成两层，将上层称为新的L2，将下层称为L1。我们仅在新的L2上构建影子子树。我们将L1的高度设置为𝐻L1 = log log 𝑃，因此仅有（1/log 𝑃）的节点（𝑂(𝑛/log 𝑃)节点）位于新的L2中，并且所有影子子树的空间复杂度总和为𝑂(𝑛)。因此，PIM树现在具有三个层：完全复制的L3，具有影子子树的L2以及没有任何复制的随机分布的L1。每个层都需要𝑂(𝑛)的空间，因此总空间复杂度为𝑂(𝑛)。这在图3中显示。我们将原始树节点及其指针称为物理节点（指针），并用黑色标记它们。我们将影子树节点及其指针称为影子节点和指针，并用红色标记它们。

引入影子子树后，L2和L1的结构。 影子节点和影子指针用红色标记。请注意，蓝色的1没有3的影子树节点，因为节点3不在其搜索子树中。右键被省略。我们还省略了从影子节点到物理节点的指针，除了节点A。 L1部分（L2部分）分别为对数对数 𝑃 层（对数 𝑃 - 对数对数 𝑃 层）。

使用影子子树加速Predecessor。影子子树增强了Push-Pull搜索的Push侧：单个Push轮可以通过运行影子子树上的查询将查询发送到整个L2，而不仅仅是向前移动一级。因此，对于均匀随机工作负载，搜索过程仅需要𝑂(log log 𝑃)轮：在L3中进行一次Push，L2中进行一次Push和L1中的𝑂(𝐻L1) = 𝑂(log log 𝑃)次Push-Pull轮。但是，对于偏斜的工作负载，我们不能简单地通过L2执行单个Push轮，因为多个查询仍可能被推送到L2中的争用点并导致负载不平衡。我们通过Pull再次解决这个问题，通过引入多轮Pull过程来消除争用点。

更详细地说，在L2中的Push-Pull搜索有两个阶段：我们首先执行最多𝑂(𝐻L2) Pull轮以处理至少具有𝐾个查询的节点，直到不存在这样的节点为止，其中𝐻L2 = log 𝑃 - log log 𝑃表示新L2的高度，然后执行一轮“Push”以通过L2发送所有查询。我们将阈值𝐾设置为𝐾 = 𝐻L2而不是1，因为现在“Push”更强大，我们倾向于更多地使用它。这两个阶段每个查询需要𝑂(1)的平衡通信。这在引理3.2中部分证明，在完整的论文[20]中完全证明。

在实践中，我们使用另一种优化来减少Pull轮数。请注意，尽管争用点是负载不平衡的唯一来源，但在消除所有争用点之前，我们可能已经达到了合理的负载平衡水平。因此，为避免不必要的Pull轮，开始Pull轮之前，我们通过计算将发送到每个PIM模块的查询数量来衡量跨PIMs的负载平衡；如果具有最多查询的模块低于平均负载的3倍，则停止Pull轮并开始Push。

复制和空间/平衡权衡。与用于 L3 的完全复制和 (ii) 用于相关工作中不执行复制的范围分区相比，影子子树是一种新颖的方案，它通过改善分布式有序索引的本地性来支持具有 𝑂(1) 通信的查询。具体而言，影子子树是一种选择性复制方法，介于这两种先前的方案之间。如果我们将节点不仅复制到其 L2 祖先，而是复制到所有 PIM 模块，我们就会获得完全复制。另一方面，如果我们只保留 L2 根的影子子树，则会获得范围分区方案。

影子子树的成本和偏移抵消也介于其他两个方案之间。表1显示了将不同方案应用于高度为 log 𝑃，大小为 𝑃 的跳表时的界限。在完全复制方案中，我们可以以完美的负载平衡运行查询，但它会给空间复杂度和更新成本带来一个超额因子 𝑃。另一方面，对于分区方案，每个查询只能由一个 PIM 模块执行。我们仍然可以执行 Push-Pull 以避免与阈值 𝐾 = 𝑃 的争用：当查询数量超过整个部分的大小时，我们将选择仅拉取整个树。可能存在负载不平衡，因为某些部分最多有 𝑃 个查询，而其他部分则没有。对于这种方法，空间复杂度和更新都没有超额。最后，使用影子子树，超额因子为 𝑂(log 𝑃)，因为每个节点都在其所有 L2 搜索树祖先中复制，根据我们对 Push-Pull 阈值 𝐾 = 𝐻L2 的选择，最大查询数为 log 𝑃。

因此，影子子树在两种方案之间提供了一个平衡的折衷，为超额和偏移抵消提供了一个甜蜜的点。

3.4 块状跳表

块状或“阻塞”是一种经典思想，在本地感知数据结构中广泛使用，例如 B 树和 B+ 树。为了改善本地性，我们应用类似的块状方法来改善 PIM 计算的访问粒度，同时降低树高度。由于块状增加了访问粒度，因此每个 PIM 处理器获得更大的本地内存带宽，从而获得更好的性能。[15]详细讨论了 PIM 中访问粒度的影响。

我们将块状应用于 PIM 树的所有层。在 L3 中，我们使用批量并行多线程 B+-树 [28] 替换了多线程跳表。在 L2 和 L1 中，我们对跳表中的节点进行分块以获得块状跳表。我们首先将水平非枢轴节点（其键不进入上层）合并为单个块，然后删除冗余的影子子树。在 Figure 3 上应用这个两步过程首先给出 Figure 4 作为中间状态，最后给出 Figure 5 中的 PIM 树。

带有影子子树的结果看起来类似于 B+-树。不同之处在于，当较低层节点溢出时，B+-树会将节点发送到上层，而块状跳表使用在插入期间生成的随机高度，因此扇出期望保持不变。我们将跳表中达到下一层的概率从 1/2 减少到 1/𝐵，因此预期的扇出为 𝐵。L3、L2 和 L1 中选择相同的块大小 𝐵 是为了简化，但每个部分可以使用不同的因子。正如 §4.2 中讨论的那样，在 L2 中使用块状跳表而不是传统的 B+-树可以使批量并行分布式插入和删除更简单、更有效。在 L3 中使用 B+-树是因为该结构不是分布式的，使得批量并行插入和删除更容易。

块状减少了所有层的树高度，从而改善了我们设计的多个方面。我们将新的 L2（L1）高度表示为 𝐻' L2（𝐻' L1）。到每个节点的 L2 部分搜索路径从 𝑂(𝐻L2) = 𝑂(log 𝑃) 减少到 𝐻' L2 = log𝐵𝑃 - log𝐵log𝐵𝑃，因为不再有水平指针追踪过程。因此，影子子树的空间和复制开销从 𝑂(𝐻L2) 减少到 𝐻' L2，因为每个节点仅在其 L2 祖先中复制。此外，较低的开销使我们能够将 𝐻' L1 降低到 log𝐵log𝐵𝑃。在实践中，𝐻' L1 在实践中有效地为 1，因为我们选择 𝐵 = 16，要超过 1019 个 PIM 模块才能使 𝐻' L1 超过 1。

因此，在实践中，L2 的高度减少到 2 层，L1 的高度减少到 1 层。一个键达到 L3 的概率为 1/4096 < 1/𝑃，到达 L2 的概率为 1/16 < log16 𝑃。

实现 Chunking 后的 Predecessor。Chunking 对搜索过程只做了一个修改：将 Push-Pull 阈值 𝐾 从 𝐻L2 改变为 𝐵 · 𝐻'L2，因为我们现在“Pull” 预期大小为 𝑂(𝐵) 的块，而不是 𝑂(1)。详细算法解释见 §3.5。

Chunking 也改善了 Predecessor 的通信成本。首先，由于 L1 的高度从 log log 𝑃 降低到 log𝐵 log𝐵 𝑃，每次查询仅导致 L1 中的通信量为 𝑂(log𝐵 log𝐵 𝑃)。其次，Chunking 将 L2 中 Pull-only 轮次的最大可能数量从 𝑂(𝐻L2) = 𝑂(log 𝑃) 减少到完全为 𝐻'L2，即 log𝐵 𝑃 − log𝐵 log𝐵 𝑃。这有助于在工作负载倾斜情况下减少通信轮次的数量。

3.5 Predecessor 算法和界限

接下来，我们描述 Predecessor 的完整算法，并讨论其成本复杂度。我们为 Predecessor 查询的通信成本和负载平衡提供证明。为简便起见，在本文中，我们的成本分析假设哈希函数提供均匀随机映射到 PIM 模块，这样 §2.2 中的引理可以被应用。算法 2 总结了搜索过程。我们在图 5 中展示了一个在 PIM 树上进行四个查询的 Predecessor 批处理的迷你逐步示例（请注意，真实批处理应在此树上有更多查询以实现负载平衡）。这些查询请求键为 1、3、4 和 7 的 Predecessors。PIM 树首先均匀分配了四个 PIM 模块中的每个模块的一个查询来搜索 L3，返回三个查询落入 L2 节点 [−∞, 3]，一个落入节点 [5, 7]。由于黄色掩码的 PIM 模块存在较大争用，节点 [−∞, 3] 的上下文将被从该模块拉到 CPU，键 1、3 和 4 在 L2 上的指针追踪搜索将在 CPU 端执行。之后，查询 1、查询 (3, 4) 和查询 7 将被推送到包含蓝色掩码节点 [−∞, 1]、绿色掩码节点 [3] 和绿色掩码节点 [5, 7] 的 PIM 模块上的本地阴影子树中搜索 L2。最后，所有查询将以类似的 Push-Pull 方式执行，从 L1 和数据节点返回结果。

定理 3.1。一批 Predecessor 查询可以在 𝑂(log𝐵 𝑃) 通信轮次内执行，每个操作总体的通信成本为 𝑂(log𝐵 log𝐵 𝑃)，并且如果批处理大小 𝑆 = Ω(𝑃 log 𝑃 · 𝐵 · 𝐻'L2) = Ω(𝑃 log 𝑃 · 𝐵 · log𝐵 𝑃)，则执行是负载平衡的。CPU 端内存占用为 𝑂(𝑆)。我们在这里提供部分证明，并在完整论文 [20] 中给出所有细节的完整证明。关键挑战在于证明通信界限和负载平衡，我们通过为算法 2 的每个阶段分别证明来实现这一点。我们以引理 3.2，L2 Push 阶段（第3阶段）的证明为例。

引理 3.2（L2 的 Push 轮）。使用阴影子树进行 Push（第3阶段）需要 1 轮，每个查询的通信成本为 𝑂(1)，并且是负载平衡的。

证明。在这个阶段，我们将每个查询作为任务发送到相应的 PIM 模块，每个查询产生 𝑂(1) 的通信成本，总共 1 轮。对于负载平衡，我们将其分析为一个加权球放入箱子的游戏，其中将目标节点视为球，目标节点上的查询数量视为权重，PIMs 视为箱子。根据假设，权重限制为 𝐾 = 𝐵 · 𝐻'L2，因为每个节点最多获得 𝐾 个查询，并且权重总和最多为 𝑆。应用引理 2.2，每个 PIM 模块产生 𝑂(𝑆/𝑃) 的通信成本。

4 PIM-TREE: 其他操作

在第3节中描述了PIM-tree数据结构的设计，以Predecessor操作为运行示例，我们现在简要介绍其他PIM-tree操作的实现方式。更多细节请参考全文 [20]。

4.1 哈希获取和更新

Get 和 Update 是根据给定键进行的操作。这些操作也不会修改数据结构的形态。因此，我们通过基于哈希的方法解决这些操作，每次操作耗费 𝑂(1) 的通信。首先使用固定的哈希函数将键映射到PIM模块，然后在每个PIM模块上构建本地哈希表，将键映射到其数据节点的本地内存地址。

由于数据节点是由哈希函数分布的，即使工作负载倾斜，我们也能实现良好的负载平衡，假设没有重复操作指向相同的键。如果存在这样的冗余操作，我们可以通过预处理在CPU端组合操作，使用用户定义的组合机制来解决这个问题。在实践中，我们在PIM端使用线性探测哈希表，但也可以使用其他哈希表变体。

4.2 插入

Insert(key,value) 操作将键插入到其搜索路径上的节点中，主要挑战在于避免多个批量插入操作同时到达相同节点时的争用和冲突。我们通过预处理来解决这个问题：并行进行搜索，并记录每次搜索的轨迹，然后使用这些轨迹来检测和处理争用点。我们的算法分为三个阶段：（1）执行搜索以记录搜索轨迹，（2）根据搜索轨迹修改物理跳表，（3）更新影子子树。

更新物理跳表。在获得每次插入的搜索轨迹之后，我们根据在更新PIM-tree之前生成的随机高度，将其插入这些节点。图6是我们解决争用的策略示例。根据它们预生成的高度，3的插入是进入黄色节点，6和8的插入将会分裂该节点。插入分为三步：在(b)中，我们将节点的右侧部分提取到CPU端，并在随机PIM模块中生成空的新节点；在(c)中，我们在CPU端确定要插入到每个节点的正确元素；最后在(d)中，我们将它们插入。

选择跳表而不是B+-树作为L1和L2的基础有助于减少轮数，因为我们可以并行地向所有节点插入，而不是像B+-树那样从叶子节点逐层自底向上插入。向L3插入也与L2的插入并行执行，通过将达到L3的插入广播到所有PIM来执行。

更新影子子树。为了保持影子子树是搜索子树的副本这一不变性，我们在更新物理跳表后更新影子子树。有三种类型的更新：（1）为新节点构建新的影子子树，（2）将新节点插入到其祖先的影子子树中，（3）在节点分裂后修剪影子子树。

我们的影子子树更新技术很简单。对于构建，我们提取L2搜索树并将其发送到新节点。对于插入和修剪，我们观察到只有搜索轨迹上的节点的影子子树需要更新，所以我们将新插入的节点发送到所有这些节点。

讨论：插入中的负载平衡。在我们的影子子树更新算法中存在负载平衡问题：为了保持影子子树的最新状态，一个L2节点可能需要大小为 𝑂(𝑃/log𝐵 𝑃) 的更新。例如，一个新的L2根需要构建其预期大小为 𝑂(𝑃/log𝐵 𝑃) 的影子子树（给定 𝐻 ′ 𝐿2 = log𝐵 𝑃 − log𝐵 log𝐵 𝑃）。这种争用因子 𝑂(𝑃/log𝐵 𝑃) 会随着 𝑃 的增长比 Predecessor 的因子 𝐾 = 𝐵 · log𝐵 𝑃 增长得更快。目前这种争用影响较小，但我们提出了一个算法来解决这个问题（目前尚未实施）。

解决方法不是保持所有影子子树的最新状态，而是将一些节点标记为未完成，在将来的轮数逐渐更新它们的影子子树，并避免在其最新状态之前使用影子子树。这有助于平衡负载。当这些节点的数量低于一个阈值时，Predecessor的界限仍然成立，我们通过额外的更新轮数来实现这一点，当这些节点的数量很多时，负载也是平衡的。

定理 4.1. 一批插入操作可以在 𝑂(log𝐵 𝑃) 的IO轮中执行，每个操作产生 𝑂(log𝐵 log𝐵 𝑃) 的通信。如果批量大小 𝑆 = Ω(𝑃 log 𝑃 · 𝐵 · 𝐻 ′ L2) = Ω(𝑃 log 𝑃 · 𝐵 · log𝐵 𝑃)，则执行是负载平衡的。CPU端的内存占用为 𝑂(𝑆)。

Delete的实现。我们处理删除与插入类似：首先获得搜索轨迹，然后从搜索轨迹上的节点中删除键，最后对影子子树应用更新。当插入导致节点分裂时，删除会导致在从节点中移除枢纽键时节点合并。详情请见全文 [20]。

4.3 扫描

Scan(LKey, Rkey) 操作（又称范围查询）返回所有键值对，其键落入[Lkey, Rkey]范围内。其算法类似于Predecessor。

在运行一批扫描查询时，我们首先在CPU上将所有批处理的重叠范围合并为不相交范围组。然后PIM树为每个范围的两个边界节点（树的当前搜索层上Lkey和Rkey的前驱）标记为SearchReqired，并将所有中间节点标记为FetchAll。FetchAll 节点需要返回它们所有的叶子数据节点。需要注意的是所有范围都是不相交的，因此在FetchAll节点中不存在争用。所有FetchAll节点被推送到PIM，并递归地返回所有子节点。与此同时，每个范围的SearchReqired节点在每个级别上都类似于Predecessor进行维护，使用推拉式搜索来处理潜在的争用。这可能会生成新的FetchAll节点。详细内容请参见完整论文[20]。

5 实现

CPU-PIM 管道。到目前为止，我们介绍了CPU和PIM在每一轮以同步的tick-tock方式运行的算法，如算法1所示。该方法的总执行时间包括三个不重叠的组件：仅CPU时间、仅PIM时间和通信时间。通信需要CPU和PIM，但其他两个组件只利用系统的一部分，这提供了通过对CPU和PIM的管道化来减少执行时间的机会。

对于管道化，我们考虑在PIM树中并行运行多个批次的执行。如图7所示，“CPU”代表仅CPU执行所花费的时间，“IO & PIM”代表在CPU-PIM通信和PIM程序中花费的时间。在我们的UPMEM系统上，CPU-PIM通信需要独占PIM端的控制，并且对PIM端的任何并发使用都会导致硬件故障。因此，一个批次需要等待PIM端完成当前的执行任务。在我们的实验中，我们只对查询进行了管道化，因为更新批次无法同时进行。对于混合操作，我们通过读写锁保护PIM树，以防止更新批次与其他批次同时运行。

PIM程序。PIM树的PIM程序是从CPU发送的缓冲区中任务的并行执行器。它设计用于解决UPMEM当前PIM处理器的两个特性。首先，PIM处理器是一个细粒度的多线程计算单元[15]，需要至少11个线程来填充管道，因此我们以12个线程的形式编写PIM程序。其次，UPMEM的系统仅支持指令少于4K的PIM程序，但PIM-tree的实现超过了这一限制。为了绕过这一限制，我们将PIM程序编写为多个独立的模块，并在需要时加载每个模块。只有插入和删除操作需要交换模块；目前，程序加载大约占执行时间的25%。在PIM树上的其余操作符合4K指令限制。

6 评估

在本节中，我们在UPMEM提供的PIM设备上评估了我们的新的PIM优化索引，并在性能相似的计算机上评估了两种传统的最新索引。

我们总结了本节的实验结果如下： （1）在偏斜工作负载下，PIM-tree在吞吐量、内存总线通信和能耗方面优于范围分区跳表。 （2）与没有PIM的传统索引相比，PIM-tree在内存总线上引起较低的通信。 （3）所有优化，包括Push-Pull搜索、影子子树、分块跳表和CPU-PIM管道化，都使（某些）PIM-tree操作的性能提高。

6.1 实验设置

UPMEM 的 PIM 平台。我们在由 UPMEM 提供的一台装备有 PIM 技术的服务器上测试 PIM-tree。该服务器配备两个 Intel(R) Xeon(R) Silver 4126 CPU，每个 CPU 都有 16 个核心，主频为 2.10 GHz，缓存为 22 MB。每个插槽都有 6 个内存通道：其中 2 个通道实现了 4 个传统 DRAM DIMM，而另外 4 个通道则使用了 8 个 UPMEM DIMM。每个 UPMEM DIMM 都有 2 个 rank，每个 rank 有 8 个芯片，每个芯片有 8 个 PIM 模块。总共有2048 个 PIM 模块。

不带 PIM 的传统机器。我们在一台具有两个 Intel(R) Xeon(R) CPU E5-2630 v4 CPU 的机器上评估传统索引，每个 CPU 都有 10 个核心，主频为 2.20 GHz，缓存为 25 MB。每个插槽有 4 个内存通道。没有带 PIM 的 DIMM。我们不能在 UPMEM 的服务器上评估传统索引，因为其 2/3 的内存通道被 PIM 带的 DIMM 使用，这些 DIMM 不能用作主内存。直接在服务器上运行传统索引将导致主存带宽不公平。在我们的实验中，我们选择了最先进的二叉搜索树[8]和（a，b）树[9]作为竞争对手。这两种实现都来自于 SetBench[4]。

基于范围划分和 Jump-Push 的基准线。我们实现了一种基于范围划分的有序 PIM 索引作为我们的基准线，其中数据节点和索引节点都基于关键字的范围分配到 PIM 模块上[10, 24]。我们在 CPU 端记录范围拆分，并使用这些拆分来找到每个操作的目标 PIM 模块。点操作被发送到相应的 PIM 模块并在其上执行。扫描操作的运行方式类似，只是在将任务发送到 PIMs 之前，需要根据范围拆分在查询中运行额外的拆分。我们还在所有 PIM 模块上构建了一个本地哈希表，用于获取。我们还实现了§2.4 中描述的 PIM 平衡跳表[19]作为另一个基准线。在讨论本文中提出的优化的影响时，我们在图 11 中通过称为“Jump-Push based”的算法实验评估了这种方法。

测试框架。我们在 PIM-tree、我们实现的基于范围划分的跳表和最先进的传统索引上运行多种类型的操作。在所有实验中，我们首先通过运行初始化集来插入键值对，然后通过评估集合内的多个操作来评估索引。所有操作都从预生成的测试文件中加载。PIM 算法（PIM-tree 和基于范围划分）以批处理方式运行操作，而传统索引则直接使用多线程并行运行它们。在所有实验中，键和值的大小都设置为 8 个字节。

为了研究算法，我们测量了时间和内存总线流量。内存总线通信是通过添加 CPU-PIM 和 CPU-DRAM 通信来测量的，前者是通过每次调用 PIM 函数（例如 PIM_Broadcast）增加计数器来测量的，后者是通过 PAPI 测量缓存未命中来测量的。我们将程序绑定到单个 NUMA 节点，并在测量缓存未命中时禁用 CPU-PIM 管道，以获得准确的流量测量。由于 PIM 带的机器的每个 CPU 都有两个 NUMA 节点，因此在此设置下，PIM 算法的有效缓存被减少到 11 MB，即完整缓存的一半。时间是以全互锁方式测量的。

目前的 PIM 硬件性能不稳定。我们在实验中观察到，上述测量指标的波动大约为 ±15%。

6.2 微基准测试

工作负载设置。每个测试首先通过插入 5 亿个均匀随机的键-值对来预热索引；然后进行以下测试：(i) 执行 1 亿个点操作或 (ii) 执行 100 万次扫描操作，每次期望检索 100 个元素。点操作使用批处理大小 𝑆 = 100 万，扫描操作使用批处理大小 𝑆 = 1 万。

我们使用 Zipfian 分布生成偏斜的工作负载 [37]。然而，通过 Zipfian 分布生成的偏斜工作负载并不适合评估批处理并行有序索引，因为这种偏斜可以在 CPU 端的预处理中轻松处理，通过将相同键的操作合并为一次操作。为了更好地表示空间偏差，在某些范围内的键更可能在同一批次中被访问，我们稍微修改了生成 Zipfian 工作负载的方式，具体如下：(i) 我们将键空间均匀地分成 𝑃 = 2048 部分；(ii) 对于每个操作，我们首先根据 Zipfian 分布选择一个部分，然后在该部分中选择一个均匀随机的元素。对于现有键的操作（Get、Delete），我们将键空间划分并从索引中当前存在的键中进行选择；对于任意键的操作（Predecessor、Insert、Scan），键空间由所有 64 位整数组成。我们周期性地重新洗牌 Zipfian 分布的每个部分的概率。这有助于缓解但无法消除由于 Insert 在高概率部分累积导致的基于范围分区的基准线的 PIM 内存溢出问题。PIM 树不会受益于这种洗牌。为了展示不同程度偏斜的结果，我们评估了 Zipfian 分布中不同 𝛼 值下的算法，范围从 0（均匀随机）到 1.2。通过这种偏斜生成方法，在最偏斜的情况下（𝛼 = 1.2），小于 10% 的操作由于重复键而被消除。

性能。图 8 展示了基于范围分区的跳表和 PIM 树在微基准测试中的吞吐量。当查询偏斜增加时，基于范围分区的基准线性能急剧下降，而 PIM 树则表现出对查询偏斜的强大抵抗力。事实上，在所有操作中，观察到 PIM 树基本不受数据偏斜的影响，在 𝛼 = 0 和 𝛼 = 1.2 时获得类似的运行时间。对于 𝛼 = 1.2，PIM 树的性能优于基于范围分区的基准线 3.87–59.1 倍。

观察到 Get 操作明显更简单且吞吐量更高，因为使用散列表作为快捷方式（对于 Update 操作也是如此），而 Predecessor 和 Scan 操作必须遍历整个有序索引。在图 8(c) 中，基于范围分区的基准线在 𝛼 = 1.2 时插入操作崩溃，因为偏斜的插入导致 PIM 模块数据不平衡分布，进而导致某些 PIM 模块的本地内存溢出。尽管这个问题可以通过重新平衡方案解决，重新平衡过程本身会导致负载不均衡，因为它需要将溢出的 PIM 模块的数据发送到负载较轻的 PIM 模块。观察到即使对基准线进行了这种改进（文献中现有的范围分区解决方案未配备此功能），PIM 树的吞吐量仍然明显大于范围分区，因为这将是基准线在执行过程中必须执行的额外工作。

图 9 展示了 PIM 树在我们的工作负载下与最先进的二叉搜索树 [8] 和 (a,b)-tree [9] 的性能对比。在所有测试案例中，PIM 树都优于传统索引，除了 Predecessor 的吞吐量比 (a,b)-tree 低外。

执行分解。图 10 展示了第 5 节提到的每个组件花费的时间比例。这些结果是在关闭我们的流水线优化的情况下得出的，因为流水线会导致不同组件的重叠。我们选取基于范围分区的跳表和 PIM 树上 Predecessor 和 Insert 的吞吐量，对均匀随机工作负载和 𝛼 = 0.6 的 Zipfian 偏斜工作负载进行了典型示例。在其他 𝛼 值的情况下，类似的结果也存在。

对于基于范围分区的跳表，PIM 执行和 CPU-PIM 通信主要占据了偏斜工作负载的时间成本，主要是因为整个执行的瓶颈——最繁忙的 PIM 模块——正在接收越来越多的任务。

对于均匀随机工作负载，PIM 执行仅占总时间成本的一小部分，尽管几乎所有比较都是在 PIM 模块中执行的。我们推断，在这种情况下，当大量的 PIM 模块参与时，已充分利用了并行性。我们相信这意味着基于 PIM 的系统是并行索引结构的理想平台。 在执行过程中，PIM 树插入花费时间加载 PIM 程序模块，因为完整程序大小超过了旨在存储 PIM 程序的 PIM 的指令内存的当前大小。有关此限制的讨论请参见第 5 节。

优化效果。图 11 展示了不同优化对我们的有序索引的影响。在这里，我们从我们的 Jump-Push 基准线开始（参见 [19] 中的 PIM 平衡跳表）。将 Jump-Push 替换为 Push-Pull 在所有测试案例中提供了高达 6.8 倍的吞吐量改进。添加 Chunking 提供了最大的改进，跨所有测试案例高达 9.0 倍，同时添加 shadow subtrees 对无偏斜的 Predecessor 有所裨益。（Insert 获得了较小的好处，因为它需要维护这种辅助数据结构。）最后，添加流水线——实现完整的 PIM 树算法——为 Predecessor 提供了额外的好处。（对于 Insert，并不支持我们的实现中不支持交错的插入批处理。）与 Jump-Push 基准线相比，在研究的设置中，PIM 树的吞吐量高达 69.7 倍。

内存总线通信。图 12 展示了 PIM 树、基于范围分区的跳表和传统非 PIM 索引的平均通信量。PIM 树的通信量比所有传统索引都少。在均匀随机工作负载下，基于范围分区的跳表在通信量上胜过所有竞争对手，但在偏斜工作负载下表现得更差。

另一个观察结果是，虽然 PIM 树存储所有数据并在 PIM 模块中执行大多数比较，但大部分内存总线流量是在 CPU 和 DRAM 之间。这是因为尽管 PIM 树算法对于一批操作需要 𝑂(𝑆) 的 CPU 端内存，但 11 MB 缓存的可用设置对于一百万次操作的批处理来说太小了。因此，CPU 端数据溢出到 DRAM 并导致显著的 CPU-DRAM 通信。为了展示这种溢出的影响，图 13 中我们研究了随着批处理大小从 1M 减小到 50K，我们运行 1 亿次均匀随机的 Predecessor 操作时 CPU 端通信的效果。结果显示，随着批处理大小的减小，CPU-DRAM 通信减少了 67%。我们不能直接使用较小的批处理大小，因为需要负载平衡，但这个结果暗示了当在具有更大缓存大小的机器上运行 PIM 树时，我们可以获得更少的 CPU-DRAM 通信。

推拉阈值选择 我们研究了在不同推拉阈值下 PIM 树的前趋性能。在我们的微基准测试中，当 𝛼 = 1 时，我们发现选择较低的阈值会导致吞吐量下降约 10%，CPU-PIM 通信增加高达 28%。较高的阈值带来轻微性能提升。更多细节请参考完整论文 [20]。

能量评估。与基于范围分区的基准 PIM 相比，在偏斜情况下，PIM 树的能耗大约降低了 5×–10×。详细信息请参考本文的完整版本 [20]。

YCSB 工作负载。与基于范围分区的基准 PIM 相比，在偏斜情况下，PIM 树的吞吐量大约提高了 9.5×–32×。详细信息请参考本文的完整版本 [20]。

6.3 现实世界偏斜工作负载

在本节中，我们使用公开可用的维基百科数据集 [12] 对 PIM 树进行了在具有真实世界偏斜性的工作负载上的测试，该数据集是来自维基百科的一组文档。为了在我们的测试框架中使用这个数据集，我们需要将其转换为一组 8 字节的键值对，然后对其进行操作。具体来说，我们首先从每个文档中提取单词，并将它们转换为小写形式，然后将 (单词，文档 ID) 对作为键，随机生成一个 8 字节整数作为值。由于我们的索引只支持 8 字节整数键，因此我们需要将 (单词，文档 ID) 对转换为 8 字节整数。转换过程如图 14 所示。我们使用 40 位来表示单词，23 位来存储文档 ID（因为文档数量少于 2^23）。在单词部分，我们使用前 5 个字母中的每个字母的 5 位，然后在接下来的 15 位中存储整个单词的哈希值，以避免冲突。经过这种转换，生成的整数保留了英语单词的两种偏斜性：(i) 单词频率偏斜（某些单词比其他单词更常用）和 (ii) 在字典顺序空间中的单词分布偏斜（具有某些前缀的单词更常用）。在这个测试中，我们选择了前 12 亿个键：前 10 亿个单词用于初始化，接下来的 2 亿个用于评估。这些键涵盖了前 510 万个文档，占数据集的 63%。有 390 万个唯一单词，将单词和文档 ID 进行配对生成了 5.29 亿个唯一键。我们仅对相同单词在同一文档中生成重复键。由于键的重复率约为 2𝑋，我们还将 PIM 树的批处理大小增加到 两百万。结果如图 15 所示，吞吐量显示为柱状图，通信（每次操作传输的字节数）显示为标记点。在这个工作负载中，所有索引的吞吐量都比微基准测试中更高，通信量更低，这是因为存在复制的键。比较不同的索引得到了与微基准测试类似的结果：PIM 树的前趋吞吐量低于 (a,b)-树，但在所有其他指标上均优于传统索引。

7 讨论

在大多数情况下，PIM 树在吞吐量上优于传统索引，但在某些情况下却不能胜过，比如我们论文中与 (a,b)-树的前趋性能相比。我们在这里解释了当前 PIM 系统的三个硬件限制，并描述了未来对硬件的改进将为 PIM 优化的数据结构带来更好性能。

第一个因素是 UPMEM 新开发的硬件上 CPU-PIM 带宽有限。在执行 50% 读取 - 50% 写入任务时，UPMEM 机器上获得的带宽为 16GB/s，比我们在相同工作负载下使用的具有 31GB/s 带宽的共享内存机器慢 1.9×。即使在如此显著的带宽限制下，PIM 树仍然比仅使用 DRAM 的索引实现了更好或相当的性能，主要是因为它大大减少了模块间通信。设计硬件以改善 CPU-PIM 带宽因此是一个重要方向，我们期待未来的改进。因此，我们相信 PIM 树将来将在吞吐量方面在所有情况下胜过传统索引。

另一个问题是 PIM 程序的有限大小限制了我们进行更复杂设计。目前的解决方法——动态程序加载——成本太高。我们相信未来的硬件将通过更大的指令内存来解决这个问题。

最后一个限制是不足的 CPU 缓存，正如第 6.2 节所述。由于缓存溢出造成的 CPU-DRAM 通信占据了大部分内存总线通信，通过更大的缓存可以缓解这一问题。我们认为充分的缓存在未来的 PIM 系统中将是重要的。

8 结论

本文介绍了 PIM 树，这是 PIM 系统中第一个有序索引，能够在数据和查询偏斜存在的情况下实现低通信和高负载平衡。我们对真实 PIM 系统上的有序索引进行了首次实验评估，表明其吞吐量比前两种最佳 PIM 方法高出 69.7× 和 59.1×，通信量比两种最先进的传统索引低至 0.3×。关键思想包括推拉搜索和影子子树——这些技术可能对 PIM 系统上的其他应用有用，因为它们在降低通信成本和管理偏斜方面非常有效。我们未来的工作将探索这些应用（例如基于基数的索引、图分析）。