CXL-ANNS: Software-Hardware Collaborative Memory Disaggregation and Computation for Billion-Scale Approximate Nearest Neighbor Search
| 缩略词 | 释义 |
|---|---|
| BI | Back Invalidation |
| DPA | Device Physical Address，设备物理地址 |
| DSP | Downstream Switch Port，Switch 的下行端口 |
| eRCD | Exclusive Restricted CXL Device，只支持 CXL 1.1 的 CXL Device |
| HDM | Host-managed Device Memory，由 Host 管理的 Device Memory |
| HPA | Host Physical Address，主机物理地址 |
| IG | Interleave Granularity，交织粒度 |
| IW | Interleave Way，交织路数 |
| RP | Root Port，根节点 |
| UIO | Unordered Input/Output，无序 IO |
| USP | Upstream Switch Port，Switch 的上行端口 |
# Introduction
不同的近似最近邻搜索（ANNS）系统在三个关键维度上的性能对比：可扩展性（Scalability）、性能（Performance） 和 准确性（Accuracy）。
可扩展性（Scalability）：指系统处理大规模数据集的能力。图中的可扩展性维度表示了系统在处理大规模 ANNS 任务时的有效性。
性能（Performance）：指系统执行 ANNS 任务的速度和效率。图中的性能维度表示了系统在实际操作中的效率。
准确性（Accuracy）：指 ANNS 任务的准确度，图中的准确性维度表示了系统在查询结果上的精度。
图 1 (a): 以前的研究
-
Oracle：代表理想化的基准系统，具有最优的可扩展性、性能和准确性。
-
Hierarchical（分层存储）：通过分层存储技术来处理大规模数据，但在某些维度上可能有所牺牲（例如，可能在性能或准确性上有所下降）。
-
Compression（压缩）：使用数据压缩方法来提高内存利用率，但可能会影响数据的准确性和性能。
图 1 (b): 基于 CXL 的方法
-
CXL：表示基于 Compute Express Link（CXL）技术的 ANNS 系统，展示了在可扩展性和性能上的显著改进，同时保持较高的准确性。
-
CXL-ANNS：论文中提出的系统，利用 CXL 技术的优势，通过软硬件协同优化，在可扩展性、性能和准确性三个维度上均表现出色。
# 贡献
-
关系感知图缓存：选择性地将图和特征向量放置在 CXL 内存网络的不同位置。具体而言，CXL-ANNS 将节点信息分配到靠近入口节点的本地附加 DRAM 中，而将其他数据集放置在 CXL 内存池中。
-
隐藏 CXL 内存池的延迟：提出了一种简单的预见技术，利用 ANNS 独特的图遍历特性，在当前 kNN 候选更新阶段预取下一个邻居的数据集。
-
CXL 中的协作 kNN 搜索设计：EP 控制器来计算距离，图遍历和候选更新。
-
减少依赖与调度
# 设计
# 节点级关系
将 enterpoint 的 2~3 跳图和节点数据放入 DRAM, 其余存入 CXL EPs
# 距离计算
# 减少数据传输
CXL EP 只传输计算后的距离
# CXLANNS 架构
CXLANNS 架构的高层次视图，主要由 i) RC 端软件栈和 ii) EP 端数据处理硬件栈构成。
# RC 端软件栈
此 RC 端软件栈由 i) 查询调度程序、ii) 池管理器和 iii) 内核驱动程序组成。在 CXL-ANNS 的顶部，查询调度程序处理来自其应用程序（如推荐系统）的所有 kNN 搜索请求。它将每个查询拆分为三个子任务（图遍历、距离计算和候选更新），并在不同的位置分配这些任务。具体而言，图遍历和候选更新子任务在 CXL CPU 端执行，而调度程序通过与底层池管理器协作将距离计算分配给底层 EP。池管理器处理 CXL 的 HPA，以考虑图形和数据向量的边缘跳数，从而可以根据节点级关系区分图形访问。最后，内核驱动程序管理底层 EP 及其地址空间；它枚举 EP 并将其 HDM 映射到系统内存的 HPA 中，供池管理器使用。由于对 HPA 的所有内存请求都在 CXL CPU 中缓存，驱动程序使用 CXL.io 而不是 CXL.mem 将 EP 端接口寄存器映射到 RC 的 PCIe 地址空间。请注意，由于存在内存映射寄存器的 PCIe 空间是在非缓存区域，底层 EP 可以立即识别主机端应用程序让 EP 知道的内容。
# 图形构建用于本地缓存
当池管理器将大部分图数据和所有数据向量分配给底层的 CXL 内存池时，它会将预计最常访问的节点在本地 DRAM 中缓存，尽可能地利用系统内存容量。为此，池管理器考虑从固定的入口节点到每个节点的边缘跳数（即，计算边缘跳数）以用于其关系感知图缓存。图 13 说明了池管理器如何将给定图中的节点分配到不同的位置（本地内存与 CXL 内存池）。在构建图时，池管理器利用 [[单源最短路径（SSSP）]] 算法计算每个节点的跳数；它首先让图中的所有节点具有负跳数（例如，-1）。从入口节点开始，池管理器检查一个边缘跳中的所有节点并增加其跳数。它访问每个节点并对其迭代此过程，直到没有节点可在广度优先搜索的方式中访问。一旦每个节点都有自己的跳数，池管理器根据跳数升序对它们进行排序，并将节点从顶部（具有最小跳数）分配到本地 DRAM 中，尽可能多地进行分配。本地 DRAM 的可用大小可以通过参考系统配置变量（sysconf ()）中的总页数（SC_AVPHYS_PAGES）和每页的大小（SC_PAGESIZE）简单估算。值得一提的是，在本研究中，池管理器在用户空间中使用多个线程执行 SSSP，旨在减少构建时间。
# 池管理对于向量 / 图
在 CXL arenas 中，CXL EP 的底层 HDM 直接暴露给用户级空间，因此需要很好地管理以适应所有十亿点数据集的内存使用行为。池管理器考虑到数据集的两个方面；数据向量（即嵌入表）应位于一个相当大且连续的内存空间中，而图结构需要处理许多长度可变的邻居列表（16B∼1KB）。池管理器采用类栈和伙伴式内存分配器，分别在每个 CXL arenas 中向上和向下增长。前者分配器具有一个范围指针，并管理嵌入表的内存，类似于栈。池管理器在多个 CXL arenas 以轮询方式分配数据向量，[[#^ac83ec | 向量分片]]。相反，伙伴式分配器采用级别指针，每个级别由一个链表组成，该链表连接不同大小的数据块（从 16B 到 1KB）。像 Linux 伙伴内存管理器一样，它根据每个邻居列表的确切需求分配 CXL 内存空间，并根据工作负载行为合并 / 拆分块。为了使每个 EP 保持平衡，池管理器以轮询方式跨不同 CXL arenas 分配每跳的邻居列表。
意思是 figure 13 第三步吗，但后面又说是把每个向量的不同部分存在 EP 中
# EP 端硬件栈
EP 端硬件堆栈包括一个用于距离计算的领域特定加速器（DSA），以及构建基于 CXL 的内存扩展器所需的所有基本硬件组件。在我们的 EP 前端，实现了物理层（PHY）控制器和 CXL 引擎，它们分别负责 PCIe/CXL 通信控制和突发到内存请求的转换。转换后的内存请求被转发到底层内存控制器，该控制器连接其后端的多个 DRAM 模块；在我们的原型中，一个 EP 有四个内存控制器，每个控制器都有一个 256GB DRAM 模块的 DIMM 通道。另一方面，DSA 位于 CXL 引擎和内存控制器之间。它可以使用内存控制器读取数据向量，同时通过 CXL 引擎的接口寄存器检查操作命令。这些接口寄存器被映射到主机的非缓存 PCIe 空间，以便主机写入的所有命令可以立即对 DSA 可见。DSA 使用多个处理元素（PE）计算多个数据向量的近似距离，每个处理元素具有简单的算术单元，如加法器 / 减法器和乘法器。
# 协作查询服务加速
# 距离计算加速
每个 EP 有许多 processing element (PE)，在论文中的原型中为 10 个。
向量分片。如果我们从 EP 的起始地址以连续的顺序定位嵌入表，EP 的后端 DRAM 带宽可能在我们的设计中成为瓶颈。这是因为嵌入表中的每个特征向量都是由高维信息编码的（约 256 维，约占 1KB）。（意思是每个 EP 的 DRAM 带宽连一个向量都取不出来？）为了解决这个问题，我们的池管理器按列对嵌入表进行分片，并将表的不同部分存储在不同的 EP 中。如图 15b 所示，这种向量分片根据每个 EP 的 I/O 粒度（256B）将每个向量分割成多个子向量。每个 EP 同时计算其所容纳的分割数据向量的子距离。随后，CXL CPU 累加子距离以获得最终的距离值。 ^ac83ec
与 EP 级加速的接口。接口寄存器仅处理命令到达的事件，称为门铃，而每个 EP 的 CXL 引擎以主动方式从 CPU 侧本地 DRAM（称为命令缓冲区）中获取相应的操作类型和邻居列表。CXL 引擎还将距离计算的结果推送到本地 DRAM，以便 RC 侧软件可以直接访问结果，而无需访问底层 CXL 内存池。
# CXL 内存池的预取
Graph read: cxl侧访问邻居表传给cpu
Graph trav: cpu将要计算的邻居节点传给cxl
Dist calc:ep计算距离传给cpu
Cand update:cpu累加子距离并排序更新
图 17a 展示了我们协作查询服务加速的基线，这让 EP 能够在 ANNS 的图遍历和候选更新（包括子距离累积）在 CPU 侧处理时计算子距离。该调度模式会不断迭代，直到没有更多的 kNN 候选需要访问（算法 1）。这种基线方法的挑战在于，一旦 CPU 侧所有节点信息准备就绪，才可以开始图遍历。虽然我们的池管理器的本地缓存解决了这个问题，但其性能仍然有限。需要通过 CXL 内存池获取节点，这些节点并不位于最内层的边缘跳跃中。由于访问底层内存池的延迟较长，图遍历可以相对被推迟。为此，我们的查询调度器在实际遍历子任务需要之前更早地预取图信息，如图 17b 所示。
查询调度器预测要访问的节点，并通过参考候选数组来获取其邻居信息。我们可以看到，总访问节点中有 82.3% 来自候选数组。意思就是取优先队列的第一个？
# 细粒度查询调度
RC-CPU 在 EP 距离计算时还是没事干，于是 Cand update 时先进行节点选择传给 CXL 再进行插入和排序。
但是你不排序怎么选择呢？不还是预测吗
# 实验分析
主要提升来自 DSA 和 cache (包括预取)
