背景信息
在信息爆炸的时代，如何快速、准确地获取所需信息是信息检索领域一直以来的关注点。向量空间模型是信息检索领域中常用的一种检索模型，其基本思想是将文本转化为向量形式，并通过计算向量之间的相似度来实现信息检索。然而，向量空间模型在应对大规模数据集和高维数据时存在一定的局限性。为了解决这一问题，近年来图索引技术逐渐成为了信息检索领域的研究热点。
图索引技术是一种基于图形结构的信息检索方法，通过建立图形结构来描述文本的语义信息，从而实现文本的快速检索。与传统的向量检索技术相比，图索引技术具有更好的扩展性和适应性，能够有效地应对大规模数据集和高维数据的检索需求。因此，优化图索引技术成为了当前信息检索领域的一个重要研究方向。目前主要的优化方向包括算法层面的优化、硬件层面的优化。本方案主要讨论现有图索引算法在NPU硬件上的优化部署方法。
目前图索引方案通常部署在CPU、GPU中。而在CPU中，受限于硬件性能，很难对海量数据、复杂场景做高效的计算。在GPU中，相比于向量检索领域其他的算法如PQ等，图索引算法的构建和检索过程并没有极高的并行度。受限于这一点，即使目前一些学术论文探索了图索引在GPU的优化，且有一定效果。但仍然存在着并行度天花板问题。综上本方案提出图索引在NPU的优化方案，而在NPU中缺少图索引相关计算算子实现、缺少已有的方案可以分配NPU资源使其适配图索引算法。
综上，本方案实现相关算子，并提出图索引在NPU中的优化策略。希望利用高性能硬件的计算能力进一步加速图索引方案。
技术方案
我们在华为昇腾NPU中优化HNSW（Hierarchical Navigable Small World）算法的搜索过程。HNSW算法是目前业界常用的高维度索引构建算法，通过多层图结构实现高效的近似最近邻搜索。在标准的HNSW搜索中，线性搜索路径和优先队列维护限制了并行计算的能力，而NPU具备强大的矩阵和向量运算能力，但对排序和优先队列操作不够高效。
为了解决这些问题，我们提出了以下优化策略：
充分利用NPU的矩阵运算能力：开发矩阵和向量运算算子，将计算任务分配给NPU中的矩阵运算单元和向量运算单元，以实现异步计算。
在NPU中使用AICPU进行排序和距离比较：AICPU负责处理排序和优先队列操作，降低主机侧CPU的负载并减少通信成本。
重构优先队列数据结构：定义了三个新的优先队列——当前节点集合P、邻居节点集合N和结果节点集合R，以优化搜索过程。
具体步骤如下：
初始化三个节点集合P、N、R。
选定入口节点a，将a加入P和R，a的邻居节点加入N。
向量运算单元计算查询向量q与P中节点的距离，并将结果传入AICPU的距离比较线程。
矩阵运算单元计算查询向量q与N中所有邻居节点的距离，并将结果传入AICPU的距离比较线程。
AICPU线程比较距离，将更近的节点加入P和R，并清空N。
当AICPU线程发现当前节点比所有邻居节点距离查询向量更近时，停止搜索并输出结果集合R。
我们实现了在NPU中的并行计算，优化了HNSW搜索过程，减少了冗余计算时间。具体实现需要开发以下算子：
计算两个向量欧氏距离的算子。
计算向量与矩阵欧氏距离的算子。
AICPU堆排序算子。
AICPU距离比较算子。
这些优化措施提升了HNSW算法在高性能计算硬件中的进一步搜索加速。
