Faiss

- Main Page
- Namespaces
- Classes
- Files

- File List

All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends
GpuIndexIVF.cu
1 /**
2 * Copyright (c) 2015-present, Facebook, Inc.
3 * All rights reserved.
4 *
5 * This source code is licensed under the BSD+Patents license found in the
6 * LICENSE file in the root directory of this source tree.
7 */
8
9 // Copyright 2004-present Facebook. All Rights Reserved.
10
11 #include "GpuIndexIVF.h"
12 #include "../FaissAssert.h"
13 #include "../IndexFlat.h"
14 #include "../IndexIVF.h"
15 #include "GpuIndexFlat.h"
16 #include "utils/DeviceUtils.h"
17 #include "utils/Float16.cuh"
18
19 namespace faiss { namespace gpu {
20
21 GpuIndexIVF::GpuIndexIVF(GpuResources* resources,
22 int dims,
23 faiss::MetricType metric,
24 int nlist,
25 GpuIndexIVFConfig config) :
26 GpuIndex(resources, dims, metric, config),
27 ivfConfig_(std::move(config)),
28 nlist_(nlist),
29 nprobe_(1),
30 quantizer_(nullptr) {
31 #ifndef FAISS_USE_FLOAT16
32 FAISS_THROW_IF_NOT_MSG(!ivfConfig_.flatConfig.useFloat16 &&
33 !ivfConfig_.flatConfig.useFloat16Accumulator,
34 "float16 unsupported; need CUDA SDK >= 7.5");
35 #endif
36
37 init_();
38 }
39
40 void
41 GpuIndexIVF::init_() {
42 FAISS_ASSERT(nlist_ > 0);
43
44 // Spherical by default if the metric is inner_product
45 if (this->metric_type == faiss::METRIC_INNER_PRODUCT) {
46 this->cp.spherical = true;
47 }
48
49 // here we set a low # iterations because this is typically used
50 // for large clusterings
51 this->cp.niter = 10;
52 this->cp.verbose = this->verbose;
53
54 if (!quantizer_) {
55 // Construct an empty quantizer
56 GpuIndexFlatConfig config = ivfConfig_.flatConfig;
57 // FIXME: inherit our same device
58 config.device = device_;
59
60 if (this->metric_type == faiss::METRIC_L2) {
61 quantizer_ = new GpuIndexFlatL2(resources_, this->d, config);
62 } else if (this->metric_type == faiss::METRIC_INNER_PRODUCT) {
63 quantizer_ = new GpuIndexFlatIP(resources_, this->d, config);
64 } else {
65 // unknown metric type
66 FAISS_ASSERT_MSG(false, "unknown metric type");
67 }
68 }
69 }
70
71 GpuIndexIVF::~GpuIndexIVF() {
72 delete quantizer_;
73 }
74
75 GpuIndexFlat*
76 GpuIndexIVF::getQuantizer() {
77 return quantizer_;
78 }
79
80 void
81 GpuIndexIVF::copyFrom(const faiss::IndexIVF* index) {
82 DeviceScope scope(device_);
83
84 this->d = index->d;
85 this->metric_type = index->metric_type;
86
87 FAISS_ASSERT(index->nlist > 0);
88 FAISS_THROW_IF_NOT_FMT(index->nlist <=
89 (faiss::Index::idx_t) std::numeric_limits<int>::max(),
90 "GPU index only supports %zu inverted lists",
91 (size_t) std::numeric_limits<int>::max());
92 nlist_ = index->nlist;
93 nprobe_ = index->nprobe;
94
95 // The metric type may have changed as well, so we might have to
96 // change our quantizer
97 delete quantizer_;
98 quantizer_ = nullptr;
99
100 // Construct an empty quantizer
101 GpuIndexFlatConfig config = ivfConfig_.flatConfig;
102 // FIXME: inherit our same device
103 config.device = device_;
104
105 if (index->metric_type == faiss::METRIC_L2) {
106 // FIXME: 2 different float16 options?
107 quantizer_ = new GpuIndexFlatL2(resources_, this->d, config);
108 } else if (index->metric_type == faiss::METRIC_INNER_PRODUCT) {
109 // FIXME: 2 different float16 options?
110 quantizer_ = new GpuIndexFlatIP(resources_, this->d, config);
111 } else {
112 // unknown metric type
113 FAISS_ASSERT(false);
114 }
115
116 if (!index->is_trained) {
117 this->is_trained = false;
118 this->ntotal = 0;
119 return;
120 }
121
122 // Otherwise, we can populate ourselves from the other index
123 this->is_trained = true;
124
125 // ntotal can exceed max int, but the number of vectors per inverted
126 // list cannot exceed this. We check this in the subclasses.
127 this->ntotal = index->ntotal;
128
129 // Since we're trained, the quantizer must have data
130 FAISS_ASSERT(index->quantizer->ntotal > 0);
131
132 if (index->metric_type == faiss::METRIC_L2) {
133 auto q = dynamic_cast<faiss::IndexFlatL2*>(index->quantizer);
134 FAISS_ASSERT(q);
135
136 quantizer_->copyFrom(q);
137 } else if (index->metric_type == faiss::METRIC_INNER_PRODUCT) {
138 auto q = dynamic_cast<faiss::IndexFlatIP*>(index->quantizer);
139 FAISS_ASSERT(q);
140
141 quantizer_->copyFrom(q);
142 } else {
143 // unknown metric type
144 FAISS_ASSERT(false);
145 }
146 }
147
148 void
149 GpuIndexIVF::copyTo(faiss::IndexIVF* index) const {
150 DeviceScope scope(device_);
151
152 //
153 // Index information
154 //
155 index->ntotal = this->ntotal;
156 index->d = this->d;
157 index->metric_type = this->metric_type;
158 index->is_trained = this->is_trained;
159
160 //
161 // IndexIVF information
162 //
163 index->nlist = nlist_;
164 index->nprobe = nprobe_;
165
166 // Construct and copy the appropriate quantizer
167 faiss::IndexFlat* q = nullptr;
168
169 if (this->metric_type == faiss::METRIC_L2) {
170 q = new faiss::IndexFlatL2(this->d);
171
172 } else if (this->metric_type == faiss::METRIC_INNER_PRODUCT) {
173 q = new faiss::IndexFlatIP(this->d);
174
175 } else {
176 // unknown metric type
177 FAISS_ASSERT(false);
178 }
179
180 FAISS_ASSERT(quantizer_);
181 quantizer_->copyTo(q);
182
183 if (index->own_fields) {
184 delete index->quantizer;
185 }
186
187 index->quantizer = q;
188 index->quantizer_trains_alone = 0;
189 index->own_fields = true;
190 index->cp = this->cp;
191 index->ids.clear();
192 index->ids.resize(nlist_);
193 index->maintain_direct_map = false;
194 index->direct_map.clear();
195 }
196
197 int
198 GpuIndexIVF::getNumLists() const {
199 return nlist_;
200 }
201
202 void
203 GpuIndexIVF::setNumProbes(int nprobe) {
204 FAISS_THROW_IF_NOT_FMT(nprobe > 0 && nprobe <= 1024,
205 "nprobe must be from 1 to 1024; passed %d",
206 nprobe);
207 nprobe_ = nprobe;
208 }
209
210 int
211 GpuIndexIVF::getNumProbes() const {
212 return nprobe_;
213 }
214
215 void
216 GpuIndexIVF::add(Index::idx_t n, const float* x) {
217 // FIXME: GPU-ize
218 std::vector<Index::idx_t> ids(n);
219 for (Index::idx_t i = 0; i < n; ++i) {
220 ids[i] = this->ntotal + i;
221 }
222
223 add_with_ids(n, x, ids.data());
224 }
225
226 void
227 GpuIndexIVF::trainQuantizer_(faiss::Index::idx_t n, const float* x) {
228 if (n == 0) {
229 // nothing to do
230 return;
231 }
232
233 if (quantizer_->is_trained && (quantizer_->ntotal == nlist_)) {
234 if (this->verbose) {
235 printf ("IVF quantizer does not need training.\n");
236 }
237
238 return;
239 }
240
241 if (this->verbose) {
242 printf ("Training IVF quantizer on %ld vectors in %dD\n", n, d);
243 }
244
245 DeviceScope scope(device_);
246
247 // leverage the CPU-side k-means code, which works for the GPU
248 // flat index as well
249 quantizer_->reset();
250 Clustering clus(this->d, nlist_, this->cp);
251 clus.verbose = verbose;
252 clus.train(n, x, *quantizer_);
253 quantizer_->is_trained = true;
254
255 FAISS_ASSERT(quantizer_->ntotal == nlist_);
256 }
257
258 } } // namespace
faiss::IndexIVF
Definition: IndexIVF.h:77
faiss::gpu::GpuIndexIVF::getNumProbes
int getNumProbes() const
Returns our current number of list probes per query.
Definition: GpuIndexIVF.cu:211
faiss::IndexFlat
Definition: IndexFlat.h:23
faiss::gpu::GpuIndexIVF::setNumProbes
void setNumProbes(int nprobe)
Sets the number of list probes per query.
Definition: GpuIndexIVF.cu:203
faiss::ClusteringParameters::niter
int niter
clustering iterations
Definition: Clustering.h:25
faiss::gpu::GpuIndexIVF::getNumLists
int getNumLists() const
Returns the number of inverted lists we&#39;re managing.
Definition: GpuIndexIVF.cu:198
faiss::gpu::GpuIndexFlat::copyTo
void copyTo(faiss::IndexFlat *index) const
Definition: GpuIndexFlat.cu:120
faiss::IndexIVF::nprobe
size_t nprobe
number of probes at query time
Definition: IndexIVF.h:78
faiss::IndexFlatL2
Definition: IndexFlat.h:79
faiss::IndexFlatIP
Definition: IndexFlat.h:73
faiss::gpu::GpuIndexConfig::device
int device
GPU device on which the index is resident.
Definition: GpuIndex.h:27
faiss::IndexIVF::ids
std::vector< std::vector< long > > ids
Inverted lists for indexes.
Definition: IndexIVF.h:81
faiss::gpu::GpuIndex::add_with_ids
void add_with_ids(Index::idx_t n, const float *x, const Index::idx_t *ids) override
Definition: GpuIndex.cu:66
faiss::Index::d
int d
vector dimension
Definition: Index.h:64
faiss::gpu::GpuIndexFlatConfig
Definition: GpuIndexFlat.h:27
faiss::gpu::GpuIndexIVFConfig::flatConfig
GpuIndexFlatConfig flatConfig
Configuration for the coarse quantizer object.
Definition: GpuIndexIVF.h:34
faiss::gpu::GpuIndexIVF::getQuantizer
GpuIndexFlat * getQuantizer()
Return the quantizer we&#39;re using.
Definition: GpuIndexIVF.cu:76
faiss::gpu::GpuIndexIVF::nprobe_
int nprobe_
Number of inverted list probes per query.
Definition: GpuIndexIVF.h:91
faiss::Level1Quantizer::quantizer_trains_alone
char quantizer_trains_alone
Definition: IndexIVF.h:41
faiss::gpu::GpuIndex::device_
const int device_
The GPU device we are resident on.
Definition: GpuIndex.h:94
faiss::gpu::GpuIndex::resources_
GpuResources * resources_
Manages streans, cuBLAS handles and scratch memory for devices.
Definition: GpuIndex.h:91
faiss::gpu::GpuIndexIVF::copyTo
void copyTo(faiss::IndexIVF *index) const
Copy what we have to the CPU equivalent.
Definition: GpuIndexIVF.cu:149
faiss::Index::idx_t
long idx_t
all indices are this type
Definition: Index.h:62
faiss::Level1Quantizer::cp
ClusteringParameters cp
to override default clustering params
Definition: IndexIVF.h:44
faiss::gpu::GpuIndexIVF::nlist_
int nlist_
Number of inverted lists that we manage.
Definition: GpuIndexIVF.h:88
faiss::Index::ntotal
idx_t ntotal
total nb of indexed vectors
Definition: Index.h:65
faiss::Index::verbose
bool verbose
verbosity level
Definition: Index.h:66
faiss::gpu::GpuIndexFlatIP
Definition: GpuIndexFlat.h:194
faiss::gpu::GpuIndexFlat::copyFrom
void copyFrom(const faiss::IndexFlat *index)
Definition: GpuIndexFlat.cu:87
faiss::gpu::DeviceScope
Definition: DeviceUtils.h:65
faiss::gpu::GpuIndexIVF::quantizer_
GpuIndexFlat * quantizer_
Quantizer for inverted lists.
Definition: GpuIndexIVF.h:94
faiss::gpu::GpuIndexFlatL2
Definition: GpuIndexFlat.h:169
faiss::Index::metric_type
MetricType metric_type
type of metric this index uses for search
Definition: Index.h:72
faiss::gpu::GpuIndexFlat::reset
void reset() override
Clears all vectors from this index.
Definition: GpuIndexFlat.cu:148
faiss::Level1Quantizer::quantizer
Index * quantizer
quantizer that maps vectors to inverted lists
Definition: IndexIVF.h:33
faiss::gpu::GpuIndexIVF::copyFrom
void copyFrom(const faiss::IndexIVF *index)
Copy what we need from the CPU equivalent.
Definition: GpuIndexIVF.cu:81
faiss::Index::is_trained
bool is_trained
set if the Index does not require training, or if training is done already
Definition: Index.h:69
faiss::gpu::GpuIndexIVF::add
void add(Index::idx_t n, const float *x) override
Definition: GpuIndexIVF.cu:216
faiss::IndexIVF::maintain_direct_map
bool maintain_direct_map
map for direct access to the elements. Enables reconstruct().
Definition: IndexIVF.h:87
faiss::ClusteringParameters::spherical
bool spherical
do we want normalized centroids?
Definition: Clustering.h:29
faiss::Level1Quantizer::own_fields
bool own_fields
whether object owns the quantizer
Definition: IndexIVF.h:42
faiss::gpu::GpuIndexIVF::cp
ClusteringParameters cp
Definition: GpuIndexIVF.h:82
faiss::Level1Quantizer::nlist
size_t nlist
number of possible key values
Definition: IndexIVF.h:34
faiss::MetricType
MetricType
Some algorithms support both an inner product version and a L2 search version.
Definition: Index.h:43