学术研究报告：UPANNS——基于真实PIM架构提升十亿级近似最近邻搜索效率

一、作者与发表信息
本研究的核心作者团队包括：香港浸会大学的Sitian Chen、Amelie Chi Zhou（通讯作者）、Yucheng Shi，南开大学的Yusen Li，以及华为的Xin Yao。该研究以《UPANNS: Enhancing Billion-Scale ANNS Efficiency with Real-World PIM Architecture》为题，发表于2025年ACM国际高性能计算、网络、存储与分析会议（SC ‘25），全文共13页，DOI编号为10.¹¹⁴⁵⁄_3712285.3759777。

二、学术背景
1. 研究领域：本研究属于高性能计算与人工智能交叉领域，聚焦于近似最近邻搜索（Approximate Nearest Neighbor Search, ANNS）算法的硬件加速。ANNS是现代AI系统的关键组件，广泛应用于推荐引擎和检索增强型大语言模型（RAG-LLMs）。
2. 研究动机：随着数据集规模增至十亿级别，传统CPU和GPU架构的瓶颈凸显：CPU受限于内存带宽，而GPU因硬件资源利用率不足导致性能与能效低下。
3. 技术背景：现有ANNS算法（如基于图的HNSW、基于压缩的IVFPQ）在十亿级数据下面临内存需求爆炸（如HNSW需450GB内存）或计算效率不足的问题。IVFPQ虽通过聚类过滤（IVF）和乘积量化（PQ）压缩数据，但其四阶段流水线（聚类过滤、查找表构建、距离计算、Top-K选择）在CPU/GPU上存在内存带宽与并行化瓶颈。
4. 研究目标：提出UPANNS框架，利用商用内存内处理（Processing-in-Memory, PIM）硬件（如UPmem）解决上述瓶颈，实现高吞吐、低能耗的十亿级ANNS。

三、研究流程与方法
1. 硬件基础：采用UPmem PIM架构，其特点包括：
- 每个DIMM含16个PIM芯片，每芯片含8个DPU（350 MHz RISC核心，24硬件线程）；
- 三级内存层次（64MB MRAM、64KB WRAM、24KB IRAM）；
- 聚合带宽达7.2 TB/s，远超CPU（85 GB/s）和GPU（1.9 TB/s）。

1. 核心创新：UPANNS整合四项关键技术：

   • 架构感知数据布局（Opt1）：通过动态复制和分布IVF聚类，平衡DPU负载。算法1基于聚类访问频率（𝑓𝑖）和大小（𝑠𝑖）计算副本数（𝑛𝑐𝑝𝑦），并采用阈值调整策略（𝑡ℎ𝑙𝑑）避免热点（图4显示真实数据集存在500倍访问偏差）。
     
   • PIM资源管理（Opt2）：
     
     • *线程调度*：利用DPU的14级流水线，11线程并发（图6），重叠MRAM传输与计算，屏障同步确保正确性；
       
     • *内存管理*：复用WRAM缓冲区（如代码本与查找表共用48KB空间），优化MRAM读取大小（图7显示256字节为性能拐点）。
       
   • 共现优化编码（Opt3）：基于元素共现图（ECG）识别高频组合（如SIFT1B中的三元组(1,15,26)出现率5.7%），预计算部分距离和并重编码数据（图8），减少25%内存访问。
     
   • Top-K剪枝（Opt4）：将线程局部最大堆转为最小堆，通过信号量（sem_take/sem_give）实现早期终止，跳过68%冗余比较（图9）。
     

2. 实验设计：

   • 基线对比：与CPU-based FAISS、GPU-based FAISS及PIM-naive（未优化PIM实现）对比；
     
   • 数据集：Deep1B（96维）、SIFT1B（128维）、SpaceV1B（100维）十亿级数据集；
     
   • 评估指标：每秒查询数（QPS）、能效（QPS/瓦）、扩展性（DPU数量与性能关系）。
     

四、主要结果
1. 性能提升（图10, 12a）：
- 相比CPU-based FAISS，UPANNS在Deep1B、SIFT1B、SpaceV1B上分别实现1.6–3.8倍、2.3–4.3倍、2.1–4.0倍QPS提升；
- 与GPU-based FAISS性能相当，但在IVF=16384时因Top-K并行度差异稍逊。

1. 能效优势（图12b）：

   • 7个UPmem DIMM（162W峰值）的QPS/瓦比NVIDIA A100（300W）高2.3倍，单位成本QPS达9.3倍。
     

2. 扩展性验证（图20）：

   • 2560个DPU时预测QPS为GPU的2.6倍，且功耗相同时（1654 DPU vs. A100）仍具优势。
     

3. 技术贡献分解（图14-19）：

   • 共现编码减少距离计算时间占比（从99.5%降至75.5%）；
     
   • Top-K剪枝加速3.1倍，线程调度提升11倍并行效率。
     

五、结论与价值
1. 科学价值：首次在真实PIM硬件上实现十亿级ANNS优化，为内存密集型计算提供新范式。
2. 应用价值：适用于实时LLM服务、大规模检索系统，其近线性扩展性（图20）支持持续增长的数据需求。
3. 方法论创新：融合数据分布、资源管理、编码优化与剪枝策略，系统性解决PIM适配难题。

六、研究亮点
1. 硬件创新：利用商用UPmem PIM的分布式DPU架构，突破传统冯·诺依曼瓶颈；
2. 算法协同：Opt3与Opt4通过数据特性（共现性）与硬件特性（有限DPU算力）深度耦合，实现“以空间换时间”；
3. 可复现性：开源实现与详细参数（如𝑛𝑐𝑝𝑦=⌈𝑠𝑖∗𝑓𝑖/𝑊⌉）为后续研究提供基准。

七、其他价值
研究揭示了PIM在非均匀负载（如偏斜查询）下的动态平衡必要性（算法2），为异构计算资源调度提供了新思路。