通过相似索引,可以在 35 分钟内(包括索引构建时间),直播,在四路 Maxwell Titan X GPU 上构建一个简单的 k-nearest-neighbor 图(k=10),基于 YFCC100M 数据集合 9500 万图像的 128D CNN 描述符,以及 0.8 的10-intersection。 十亿矢量的 k-nearest-neighbor 图也已实现。开发者可以在 Deep1B 数据集上创建强力的 k-nearest-neighbor 图(k=10),0.65 的 10-intersection 在四路 Maxwell Titan X GPU 下需要 12 个小时。而 0.8 的 10-intersection 在八路帕斯卡 P100-PCle GPU 上也需要 12 个小时。画质较低的图可以在五小时内通过 Titan X 生成。 其他方面的性能也非常惊人。例如,构建上述 Deep1B 索引需要用 k-means 聚类生成 262,144 个几何中心和 6710 万 120-dim 矢量。在 25 E-M 次迭代下,四路 Titan X GPU(12.6 tflp/s)需要花 139 分钟处理,八路帕斯卡 P100 GPU(40 tflop/s)则需花 43.8 分钟。要注意的是聚类的训练集并不需要和 GPU 显存匹配,因为数据会按需及时导入到 GPU 中,不会影响性能。 其他技术基于诸多研究成果和大量工程技术,Facebook AI Research 团队自 2015 年开始研发 Faiss。针对 Faiss, Facebook 选择优化几项基础技术,尤其是在 CPU 方面,Facebook 大量运用了如下技术: 多线程充分利用多核性能,并在多路 GPU 上进行并行搜索; 运用 matrix/matrix 乘法在 BLAS 算法库中进行高效、精确的距离计算。如果没有 BLAS,高效的暴力算法很难呈现最优效果。BLAS/LAPACK 是 Faiss 必备的前提软件; 机器 SIMD 矢量化和 popcount 被用于加速孤立向量的距离计算。 GPU 方面由于典型的 CPU 算法(如 heap selection)并不适用于 GPU,此前应用在相似性搜索上的 GPU 和 k-selection(寻找 k-minimum 或 k-maximum 因素)一直存在性能方面的问题。对 Faiss GPU 来说,我们设计了文献记载中已知的最快的小 k-selection 算法(k<=1024)。所有的中间状态都被保存在寄存器中,这样有助于提升其速度。它能将输入的数据以 single pass 的方式进行 k-select,运行潜在峰值性能的 55%,这取决于峰值 GPU 的显存带宽。由于其状态仅保留在寄存器文件中,并且能和其他内核一起使用,从而能进行快速准确的相似搜索算法。 研究领域中,许多人把注意力放在高效的平铺策略和面向相似性搜索的内核执行上。Multi-GPU 支持由分片或复制数据来提供,开发者不会受到单 GPU 显存大小的限制。半精度浮点支持(float 16)也有提供,使得开发者可以在支持的 GPU 上进行完整的 float 16 运算。float 16 这样的编码矢量能在几乎不损失精度的情况下提高速度。 总之,连续不断的超量因素在实施中非常重要,Faiss 做了许多关注工程细节的痛苦的工作。 Faiss上手 Faiss 以 C++ 实现,支持 Python。想要上手,需要从 GitHub 上获取 Faiss,编译后将 Faiss 模块导入到 Python 中。Faiss 与 numpy 完全集成,所有的函数都是用 numpy 数组来实现的(in float32)。 编译自:https://code.facebook.com/posts/1373769912645926/faiss-a-library-for-efficient-similarity-search/ (责任编辑:本港台直播) |