evaluation data

[5000user5000]

naive baseline (at commit: 311ee2d, 10/29. 現在也可以用 make naive)
Dataset: SIFT1M

nprobe	QPS	p50(ms)	p95(ms)	R@1	R@10	R@100
1	3464.9	0.277	0.456	44.12	38.01	29.80
2	1918.6	0.499	0.791	60.04	54.14	44.41
4	1007.8	0.944	1.417	76.31	70.63	60.78
8	517.0	1.891	2.714	87.98	84.18	76.12
16	263.1	3.742	5.005	95.18	93.35	88.26
32	134.0	7.506	9.296	98.08	97.94	95.73
64	67.7	14.684	16.993	99.17	99.56	99.02
128	34.6	29.131	32.018	99.30	99.90	99.89
256	17.6	56.618	59.882	99.32	99.93	99.99

[5000user5000]

openMP-only 加速

Dataset: SIFT1M

nprobe	QPS	p50(ms)	p95(ms)	R@1	R@10	R@100
1	31251.3	0.703	1.168	44.12	38.01	29.80
2	17892.9	0.686	1.172	60.05	54.14	44.41
4	9787.5	0.356	0.591	76.23	70.63	60.78
8	5069.8	0.455	0.753	87.87	84.17	76.12
16	2605.9	0.508	0.819	95.16	93.35	88.26
32	1327.6	0.932	1.202	98.07	97.94	95.73
64	670.9	1.706	2.042	99.00	99.55	99.02
128	342.8	3.214	3.590	99.23	99.90	99.89
256	173.6	6.101	6.568	99.21	99.94	99.99

Target achieved: Recall@10 = 99.94% >= 95%
Best config: nprobe=256, QPS=173.6

[5000user5000]

數據分析總結 (比較 naive)

• nprobe 小 (1-4):

  • Latency: OpenMP 的執行緒開銷 > 實際計算時間，導致單次延遲變高。
  • QPS: 儘管單次延遲高，但並行處理的巨大優勢使得總吞吐量依然提升了近 10 倍 (3464 -> 31251)，這符合一個典型的多核心 CPU 的加速效果。

• nprobe 大 (32-256):

  • Latency: 此時，單次查詢的計算量變得很大，遠遠超過了 OpenMP 的執行緒開銷。並行化的效果在單次查詢中也體現出來，因此 p50/p95 延遲顯著降低。
  • QPS: 吞吐量繼續大幅領先，因為不僅是查詢之間並行，單個查詢的內部計算也被並行化了。

[5000user5000]

AVX SIMD-only 加速
Dataset: SIFT1M

nprobe	QPS	p50 (ms)	p95 (ms)	R@1	R@10	R@100
1	8785.1	0.110	0.171	44.12	38.01	29.80
2	5088.5	0.190	0.292	60.04	54.14	44.41
4	2782.4	0.344	0.542	76.31	70.63	60.78
8	1464.1	0.667	0.971	87.98	84.18	76.12
16	753.9	1.311	1.792	95.18	93.35	88.26
32	389.3	2.568	3.283	98.08	97.94	95.73
64	199.6	5.103	5.917	99.17	99.56	99.02
128	102.3	9.941	10.878	99.30	99.90	99.89
256	52.4	19.165	20.375	99.32	99.93	99.99

[5000user5000]

AVX SIMD + openMP
Dataset: SIFT1M

nprobe	QPS	p50(ms)	p95(ms)	R@1	R@10	R@100
1	53518.0	0.393	0.572	44.12	38.01	29.80
2	31044.0	0.394	0.598	60.05	54.14	44.41
4	17071.8	0.169	0.270	76.23	70.63	60.78
8	8979.3	0.230	0.340	87.87	84.17	76.12
16	4623.6	0.280	0.410	95.16	93.35	88.26
32	2358.1	0.511	0.648	98.07	97.94	95.73
64	1198.7	0.956	1.121	99.00	99.55	99.02
128	609.0	1.796	2.001	99.23	99.90	99.89
256	310.1	3.416	3.663	99.21	99.94	99.99

[5000user5000]

Seco1024 的數據

make full (純CPU 最快)

make cuda (GPU-only)
目前 k=100 會爆 shared memory

[5000user5000]

gpu k=100 時的數據