Faiss 底层基准测试

本部分展示了 Faiss 在底层操作方面的一些基准测试结果。

1M 向量上的 kmeans 聚类​

Faiss 的 kmeans（K均值聚类）实现非常高效。将 $n=1\,000\,000$ 个、每个为 $d=256$ 维的向量聚类为 $k=20\,000$ 个中心（即质心，使用 $n_{iter}=25$ 次期望最大化迭代），这种暴力计算方式的复杂度为 $n \times d \times k \times n_{iter}$ 次乘加运算。本案例总运算量为 $128$ 万亿次浮点运算（Tflop）。

不同硬件上的 Faiss 聚类耗时如下：

• CPU：11 分钟
• Kepler 架构 K40m GPU（1块）：3 分钟
• Maxwell 架构 Titan X GPU（1块）：111 秒
• Pascal 架构 P100 GPU（1块，float32）：55 秒
• Kepler 架构 K40m GPU（4块）：52 秒
• Maxwell 架构 Titan X GPU（4块）：35 秒
• Pascal 架构 P100 GPU（1块，float16）：34 秒
• Maxwell 架构 Titan X GPU（8块）：21 秒
• Pascal 架构 P100 GPU（4块，float32）：21 秒
• Pascal 架构 P100 GPU（4块，float16）：16 秒
  备注

  以上大部分耗时是在 CPU 上完成的。

• Pascal 架构 P100 GPU（8块，float32）：14 秒
  备注

  问题规模太小，绝大部分时间都在 CPU 和 PCIe 传输上。

• Pascal 架构 P100 GPU（8块，float16）：14 秒
  备注

  问题规模过小，GPU 上的 Hgemm 运算块很小成为瓶颈，大多数耗时在 CPU 和 PCIe 传输上。

9500万向量上的 kmeans 聚类​

只要训练集可以放入内存（RAM），也可以对更大数据集进行聚类测试。本实验在 9500 万个 128 维向量（约 48GB 内存）上，将其聚类为 8.5 万个中心。使用 7 块 Titan X GPU，聚类耗时不到 1 小时，具体代码参见：TODO。

knn-graph（近邻图）的构建​

我们使用 Faiss 对 1 千万张图片（每张用 128 维向量表示）构建了暴力的 k近邻图（knn-graph，其中 $k=10$）。

我们主要考察以下两个方面：

• 效率：在 8 块 M40 GPU 上，构建整个 knn-graph 所需时间。
• 质量：为了估算 knn-graph 的准确度，我们随机选取 1 万张图片，计算其精确的近邻。准确度度量标准是，生成的 knn-graph 中每个点的 10 个邻居中，有多少实际也在“真值”的10个最近邻中。

总体来看，若内存不是瓶颈（8 块 GPU 容纳 1 亿个向量轻松无压力），IVFFlat（倒排文件结构的暴力近邻搜索方法）在速度与精度上均优于其他方法。