Facebook AI Research (FAIR)が開発したGPU対応の類似検索ライブラリ Faiss に関する2回目の紹介エントリーとなります。前回は、FaissのインストールとC++チュートリアルの説明を行いました。今回はGPUを利用した検索処理を試してみます。
Faissのインストール方法については前回のエントリーを参照してください。
環境
| Amazon Linux AMI release 2017.03 Intel Xeon CPU E5-2686 v4 @ 2.30GHz NVIDIA GK210GL [Tesla K80] |
Ubuntu 16.04 LTS (x86_64) Intel Core i5-2500K CPU @ 3.30GHz NVIDIA GM204 [GeForce GTX 970] |
|
CUDA Toolkit 8.0 GCC 4.8.3 / 5.4.0 Python 3.5.2 NumPy 1.12 |
今回からはプログラムのベンチマークも行っていくので自宅のGPUサーバをメインに使って検証します。EC2のp2.xlargeをがっつり使うと請求が怖いし、そもそもレイテンシが大きくてストレスが溜まるので。
前回の導入部分の補足としてCUDAコード部分のコンパイルにはGCCではなくNVCC(CUDAコンパイラ)を利用するので事前にインストール済みであることを確認しておきます。また、GPU製品のCompute Capabilityは3.5以降が必要となっています。
|
1 2 3 4 5 6 7 8 9 |
# PATHは事前に通しておく、デフォルトだと /usr/local/cuda-xxx/bin/nvcc $ nvcc -V nvcc: NVIDIA (R) Cuda compiler driver Copyright (c) 2005-2016 NVIDIA Corporation Built on Sun_Sep__4_22:14:01_CDT_2016 Cuda compilation tools, release 8.0, V8.0.44 $ nvidia-smi -L GPU 0: GeForce GTX 970 (UUID: GPU-35bd77fd-edfe-861b-c4a6-59e9eb111aa6) |
GPUでk-meansクラスタリング
まずは、公式ドキュメントにサンプルとして掲載されているGPUを利用したk-meansクラスタリングプログラムの動作確認をします。日本語での補足も簡単に入れておきます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <cstdio> #include <vector> #include <faiss/Clustering.h> #include <faiss/utils.h> #include <faiss/gpu/GpuIndexFlat.h> #include <faiss/gpu/StandardGpuResources.h> // just generate some random vecs in a hypercube (CPU) // クラスタリング対象のダミーデータを生成 std::vector<float> makeRandomVecs(size_t numVecs, int dim) { std::vector<float> vecs(numVecs * dim); // void faiss::float_rand (float * x, size_t n, long seed) // OpenMPを利用してマルチスレッドで生成される faiss::float_rand(vecs.data(), vecs.size(), 1); return vecs; } int main(int argc, char** argv) { // Reserves 18% of GPU memory for temporary work by default; the // size can be adjusted, or your own implementation of GpuResources // can be made to manage memory in a different way. faiss::gpu::StandardGpuResources res; int dim = 128; int numberOfEMIterations = 20; size_t numberOfClusters = 20000; size_t numVecsToCluster = 5000000; // generate a bunch of random vectors; note that this is on the CPU! std::vector<float> vecs = makeRandomVecs(numVecsToCluster, dim); faiss::gpu::GpuIndexFlatConfig config; config.device = 0; // this is the default GPUデバイス番号 config.useFloat16 = false; // this is the default GPU側でFP16(半精度浮動小数点)を利用するか faiss::gpu::GpuIndexFlatL2 index(&res, dim, config); // faiss::IndexFlatL2 のGPU版 faiss::ClusteringParameters cp; cp.niter = numberOfEMIterations; // niter にイテレーション回数を設定 cp.verbose = true; // verbose を true にすると標準出力にイテレーション毎の処理結果が表示される // faiss::Clustering::Clustering(int d, int k, const ClusteringParameters &cp) faiss::Clustering kMeans(dim, numberOfClusters, cp); // void faiss::Clustering::train(idx_t n, const float *x, faiss::Index &index) kMeans.train(numVecsToCluster, vecs.data(), index); // kMeans.centroids contains the resulting cluster centroids (on CPU) printf("centroid 3 dim 6 is %f\n", kMeans.centroids[3 * dim + 6]); return 0; } |
faiss::gpuに属するクラスについては後述しますが、faiss::gpu::GpuIndexFlatL2 は前回のエントリーで紹介した faiss::IndexFlatL2 のGPU版となっています。faiss::Clustering::train 実装内部ではイテレーション毎に現在のセントロイドをインデックスしておき、全データをクエリとして検索しています。
* コンパイル
|
1 2 3 4 5 6 |
$ nvcc \ -I/usr/local/cuda-8.0/targets/x86_64-linux/include/ -Xcompiler -fPIC -Xcudafe \ --diag_suppress=unrecognized_attribute -gencode arch=compute_52,code="compute_52" \ --std c++11 -lineinfo -ccbin g++ -DFAISS_USE_FLOAT16 \ -o gpu_kmean gpu_kmean.cpp \ libgpufaiss.a libfaiss.a -Xcompiler -fopenmp -lcublas -lopenblas |
* 実行結果例
|
1 2 3 4 |
Clustering 5000000 points in 128D to 20000 clusters, redo 1 times, 20 iterations Preprocessing in 0.74 s Iteration 19 (238.49 s, search 225.08 s): objective=4.51621e+07 imbalance=1.012 nsplit=0 centroid 3 dim 6 is 0.468013 |
GPUを利用したk-meansクラスタリングは過去にもいろいろライブラリ等が出ていますし、サンプルとしてはよく見るものです。ここでの動作確認では5,000,000個のデータを20,000クラスタに分けるのに4分弱で処理できました。いまいちよく分からないのでCPU版と比較してみます。
|
1 2 3 4 5 6 |
# ちなみにCore i5-2500K(CPU)だと、 Clustering 5000000 points in 128D to 20000 clusters, redo 1 times, 20 iterations Preprocessing in 0.73 s ^CIteration 10 (15075.25 s, search 15063.99 s): objective=4.52261e+07 imbalance=1.014 nsplit=0 ./cpu_kmean 26401.24s user 5721.63s system 198% cpu 4:29:12.17 total ## 4時間経っても終わらず、、ここで断念 |
上記プログラムをCPUでのクラスタリング処理に変更するには、インデックスオブジェクトである faiss::gpu::GpuIndexFlatL2 を faiss::IndexFlatL2 に変えるだけです。ただし上記プログラムの設定だとCPU版の処理が一向に終わらなかったので以下のようにテストの規模を縮小することで調整しました。
- データ(128次元): 500,000
- クラス(分割数): 2,000
- イテレーション: 20
500,000個のデータを2,000クラスタに分けます。それぞれ5回計測した平均処理時間は以下の通りです。また、参考までに各製品のリリース時期も併記しています。
| CPU Intel Core i5-2500K (2011/1) |
CPU Intel Xeon E5-2686 (2016/6) |
GPU NVIDIA GM204 [GeForce GTX 970] (2014/9) |
GPU NVIDIA GK210GL [Tesla K80] (2014/11) |
|---|---|---|---|
| 511.15s | 114.10s | 5.70s | 4.85s |
前回のエントリーにも書いた通り、CPU版はOpenMPやSIMDを駆使して実装されており十分に高速です。しかしGPU版はそれと比較しても遙かに高速に動作します。また、CPUからGPUへのデータ転送は必要に応じて都度行われるため(計算に必要なデータだけGPU上に載せる)、VRAM容量を超えるような巨大なデータセットでもクラスタリング可能となっています。
さらに、FP16(半精度浮動小数点値での演算)を有効にしてGTX 970上で比較してみました。こちらも同様に5回計測した平均処理時間を載せます。
- データ(128次元): 5,000,000
- クラス(分割数): 20,000
- イテレーション: 20
| FP16無効 | FP16有効 |
|---|---|
| 228.47s | 191.76s |
なかなか興味深い結果となりました。確かPascal世代からFP16の性能が格段に上がっていたかと思うので(1SPでFP16二つを同時演算したり)、PascalのGPUでベンチマークしてみたいところです。Facebook ResearchのレポートだとTesla P100でだいたい100秒ほどで完走するらしいです。
* GPU k means example
GPUを利用した検索
次は前回紹介したCPU版チュートリアルにある各種検索プログラムをGPU対応していきます。
GPUリソースの確保・初期化
GPUで処理するために予めGPUリソースの事前確保作業が必要ですが、生のCUDAプログラムと比較すれば十分抽象化されているので特に難しいところは無いかと思います。GPU版のヘッダファイルは faiss/gpu 以下にあります。
faiss::gpu::StandardGpuResourcesfaiss::gpu::GpuIndexFlatConfig
|
1 2 3 4 5 |
faiss::gpu::StandardGpuResources res; faiss::gpu::GpuIndexFlatConfig config; config.device = 0; config.useFloat16 = true; |
前述のk-meansのサンプルコードと同じ設定でだいたい大丈夫です。内部ではcuBLASのハンドル初期化やCUDAのストリーム生成処理等を行っています。デフォルトだとストリーム(cudaStream_t)は2本準備しているようです。
GPU版インデックスクラス
チュートリアルで紹介した各種CPU版インデックス用クラスのGPU対応は簡単なのでまとめて紹介します。
| CPU | GPU |
|---|---|
faiss::IndexFlatL2 |
faiss::gpu::GpuIndexFlatL2 |
faiss::IndexIVFFlat |
faiss::gpu::GpuIndexIVFFlat |
faiss::IndexIVFPQ |
faiss::gpu::GpuIndexIVFPQ |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
const int d = 64; // dimension ## IndexFlatL2 faiss::IndexFlatL2 index(d); ## GpuIndexFlatL2 (IndexFlatL2のGPU版) ## GpuIndexFlatL2(GpuResources *resources, int dims, GpuIndexFlatConfig config=GpuIndexFlatConfig()) faiss::gpu::GpuIndexFlatL2 index(&res, d, config); ## IndexIVFFlat const int nlist = 100; // number of inverted lists faiss::IndexFlatL2 quantizer(d); faiss::IndexIVFFlat index(&quantizer, d, nlist, faiss::METRIC_L2); ## GpuIndexIVFFlat (IndexIVFFlatのGPU版) ## GpuIndexIVFFlat(GpuResources *resources, int device, GpuIndexFlat *quantizer, bool useFloat16, int dims, int nlist, IndicesOptions indicesOptions, faiss::MetricType metric) faiss::gpu::GpuIndexFlatL2 quantizer(&res, d, config); faiss::gpu::GpuIndexIVFFlat index(&res, 0, &quantizer, false, d, nlist, faiss::gpu::INDICES_64_BIT, faiss::METRIC_L2); ## IndexIVFPQ const int m = 8; // number of subquantizers const int nbits = 8; // number of bits per quantization index faiss::IndexFlatL2 quantizer(d); faiss::IndexIVFPQ index(&quantizer, d, nlist, m, nbits); ## GpuIndexIVFPQ (IndexIVFPQのGPU版) ## GpuIndexIVFPQ(GpuResources *resources, int device, int dims, int nlist, int subQuantizers, int bitsPerCode, bool usePrecomputed, IndicesOptions indicesOptions, bool useFloat16LookupTables, faiss::MetricType metric) faiss::gpu::GpuIndexIVFPQ index(&res, 0, d, nlist, m, nbits, true, faiss::gpu::INDICES_64_BIT, false, faiss::METRIC_L2); |
2017/05現在、faiss::gpu::GpuIndexIVFPQ にはGPU版インデックスクラスのポインタを直接受け取るコンストラクタは未実装のようですので別のコンストラクタを利用しています。この場合は引数で渡す faiss::MetricType に応じたGPU版インデックスクラスのインスタンスを内部で生成/保持してくれます。前回紹介していませんでしたが距離尺度は faiss::MetricType 定数で指定するようになっており、チュートリアルではL2ノルムの紹介のみでしたが、もちろん内積(Inner Product)にも対応しています。
|
1 2 3 4 5 |
/// Some algorithms support both an inner product vetsion and a L2 search version. enum MetricType { METRIC_INNER_PRODUCT = 0, METRIC_L2 = 1, }; |
また、faiss::gpu::IndicesOptions は以下のように定義されています。これはCPU<->GPU間でのインデックス情報の転送・保存をどのような形式で行うかを指定します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
enum IndicesOptions { /// The user indices are only stored on the CPU; the GPU returns /// (inverted list, offset) to the CPU which is then translated to /// the real user index. INDICES_CPU = 0, /// The indices are not stored at all, on either the CPU or /// GPU. Only (inverted list, offset) is returned to the user as the /// index. INDICES_IVF = 1, /// Indices are stored as 32 bit integers on the GPU, but returned /// as 64 bit integers INDICES_32_BIT = 2, /// Indices are stored as 64 bit integers on the GPU INDICES_64_BIT = 3, }; |
CPU版とは異なりGPU版の各種インデックスクラスのメンバ変数はなぜかカプセル化されているみたいなので、提供されているgetter/setter経由でデータ操作を行います。GPU対応する際には忘れないようにしましょう。
|
1 2 3 |
// nprobe を変更する場合 index.nprobe = 10; // CPU版 index.setNumProbes(10); // GPU版 |
ベンチマーク
次は最近傍探索処理の測定を行います。チュートリアルのプログラムをベースにパラメータ等を調整して比較しました。論文中ではDeep1BやYFCC100Mなどの巨大なデータセットでベンチマークをしていて真似したかったんですけど、自宅のGPU開発環境だと空冷が適当なので kidle_inject が発生し、温度上昇防止のためCPU使用に制限をかけてしまいます。。ここではANN_SIFT1Mと同じ小規模データでベンチマークを行いました。
- 次元数: 128
- データ数: 1,000,000 (100万データ)
- 同時実行クエリ数: 10,000 (1万クエリ)
- インデックス: faiss::gpu::IndexFlatL2 (全探索) / faiss::gpu::IndexIVFPQ (PQ + 転置インデックス)
- 転置インデックスのリストサイズ 100、サブベクトル数 8、量子化ビット数 8、FP16有効
- 検索時のkの値: 1 ~ 1024 の範囲で変更
ベンチマーク用プログラムはここに記載するには少し長くなるのでGistにアップロードしておきます。
僕の個人開発環境だと1万クエリの上位20件を検索するのに、全探索(IndexFlatL2)の場合は約1.1秒、PQ + 転置インデックス(IVFPQ)の場合は約20ミリ秒でした。ただし、Faissの真価はbillion-scaleでの検索処理において発揮されるので、ここでのベンチマークは参考程度ということで。
また、Facebook AI Research公式の詳細なベンチマーク結果は以下を参照してください。
注意点など
GPUでの検索処理にはいくつか制限が設けられています。2017/06現在の仕様なので変更される可能性があります。
GPUテンポラリメモリ
cudaMalloc/cudaFree はコストが高い処理なので事前にある程度のメモリ領域が自動的に確保されるのですが、そのサイズをユーザー側が指定することができます。StandardGpuResources のAPIで指定できます。
|
1 2 3 |
faiss::gpu::StandardGpuResources res; size_t memSize = 1073741824; // 1024MB res.setTempMemory(memSize); |
テンポラリメモリが足りないと以下のような警告が出力されます。cudaMalloc が新たに必要になってしまうから遅くなるよというヒントであって処理が継続できないわけではありません。
|
1 |
WARN: increase temp memory to avoid cudaMalloc, or decrease query/add size (alloc 268435456 B, highwater 268435456 B) |
PQ(Product Quantization)のために内部ルックアップテーブルを準備する際にはそこそこ十分な容量を確保しておいた方が良いかと思います。
kおよびnprobe値の上限
kとnprobe値は1024が上限となっていますが、1024もあれば実用上は十分かなと思います。
|
1 2 |
# 1024以上を指定すると以下のようなエラーが発生する Faiss assertion k <= 1024 failed in void faiss::gpu::IVFPQ::query(faiss::gpu::Tensor<float, 2, true>&, int, int, faiss::gpu::Tensor<float, 2, true>&, faiss::gpu::Tensor<long int, 2, true>&) ~ ... 省略 |
Product Quantizationのパラメータ
PQの実装上、量子化ビット数(サブベクトル当たりのデータサイズ)は8ビット以下、データの次元数をサブベクトル数で割った余りが0になるように調整する必要があります。今回紹介したベンチマークプログラムではデータは128次元、サブベクトル数は8、量子化ビット数は8で設定しています。
|
1 2 |
Faiss assertion bitsPerCode_ <= 8 failed in void faiss::gpu::GpuIndexIVFPQ::assertSettings_() const at GpuIndexIVFPQ.cu:436 Faiss assertion this->d % subQuantizers_ == 0 failed in void faiss::gpu::GpuIndexIVFPQ::assertSettings_() const at GpuIndexIVFPQ.cu:439 |
おわりに
今回はFaiss GPU版のインタフェースを紹介しました。CPU版から移行修正しやすいように工夫されているので特に難しいところはなかったかなと思います。GPU版の実装は論文と併せて読み進めていますが、k-selection(選択アルゴリズム)のGPU実装の仕組みが難しくて難航しています。。理論面を調べつつ、そろそろPythonインタフェースを用いたアプリケーション寄りの開発もやってみたいと思っています。