RISC-V上实现高效近似最近邻搜索,提升速度与能效。
RVANNS: Mixed-Precision Indexing and Locality-Aware Graph Traversal on RISC-V

- 采用混合精度表示与局部性优化图遍历,减少数据移动开销。
- 在真实RISC-V处理器上实现最高4.94倍加速,能效比提升2.27倍。
- 适合高并发向量检索场景,尤其适用于资源受限的嵌入式系统。
CPU上的近似最近邻搜索(ANNS)正日益受候选向量移动和解码开销制约,而非峰值算力。尽管RISC-V向量扩展(RVV)支持向量长度无关执行和基于LMUL的寄存器分组,但通用低精度解码仍存在转换开销,而不规则图遍历导致访问分散,降低缓存局部性和内存级并行性。我们提出RVANNS,一种面向RVV的ANNS引擎,联合优化向量表示与图局部性。其混合精度多层索引(MPMI)以8位仿射基和稀疏FP16/FP32残差表示每个向量,融合重构与距离累加,并对齐扩展与LMUL大小的寄存器组。ROrder将可能共访问的图节点共置,并重映射邻接表排序,将散乱的数据探查转化为更密集、主要向前的地址流。集成至Milvus后,相比标量执行,在128位和256位真实RVV处理器上分别实现3.39倍和4.94倍加速。在控制的HNSW配置下,较RVV SIMD+FP32提升2.27–2.76倍吞吐,较对应AVX-512和SVE基线提升1.18–1.59倍。在Cohere10M数据集上,进一步实现1.82–2.27倍更高的每瓦查询率(QPS/W)优于评估的GPU基线。
原文摘要 · Abstract (English)
Approximate nearest neighbor search (ANNS) on CPUs is increasingly constrained by candidate-vector movement and decoding rather than peak arithmetic throughput. Although the RISC-V Vector Extension (RVV) provides vector-length-agnostic execution and LMUL-based register grouping, generic low-precision decoding still incurs conversion overhead, while irregular graph traversal generates scattered accesses that degrade cache locality and memory-level parallelism. We present RVANNS, an RVV-oriented ANNS engine that jointly optimizes vector representation and graph locality. Its Mixed-Precision Multi-Layer Index (MPMI) represents each vector with a dense 8-bit affine base and sparse FP16/FP32 residuals, fusing reconstruction with distance accumulation and aligning widening with LMUL-sized register groups. ROrder co-locates likely co-visited graph nodes and sorts remapped adjacency lists, transforming scattered payload probes into denser, predominantly forward-moving address streams. Integrated into Milvus, RVANNS achieves 3.39x and 4.94x speedups over scalar execution on real 128-bit and 256-bit RVV processors, respectively. Under controlled HNSW configurations, it improves throughput by 2.27--2.76x over RVV SIMD+FP32 and by 1.18--1.59x over the corresponding AVX-512 and SVE baselines. On Cohere10M, it further delivers 1.82--2.27x higher QPS/W than the evaluated GPU baselines.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。