c++ - 如何使用 OpenMP 并行化最近邻搜索
问题描述
基本上,我有一个集合,其中包含大小为 512 (2048 )std::vector<std::pair<std::vector<float>, unsigned int>>
的模板对及其对应的 identifier 。std::vector<float>
bytes
unsigned int
我正在编写一个函数,其中为我提供了一个模板,我需要返回集合中最相似模板的标识符。我正在使用点积来计算相似度。
我的幼稚实现如下所示:
// Should return false if no match is found (ie. similarity is 0 for all templates in collection)
bool identify(const float* data, unsigned int length, unsigned int& label, float& similarity) {
bool found = false;
similarity = 0.f;
for (size_t i = 0; i < collection.size(); ++i) {
const float* candidateTemplate = collection[i].first.data();
float consinSimilarity = getSimilarity(data, candidateTemplate, length); // computes cosin sim between two vectors, implementation depends on architecture.
if (consinSimilarity > similarity) {
found = true;
similarity = consinSimilarity;
label = collection[i].second;
}
}
return found;
}
如何使用并行化加快速度。我的收藏可能包含数百万个模板。我读过你可以添加#pragma omp parallel for reduction
,但我不完全确定如何使用它(如果这甚至是最好的选择)。
另请注意:对于我的点产品实现,如果基础架构支持 AVX 和 FMA,我正在使用此实现。由于只有有限数量的 SIMD 寄存器,这会在我们并行化时影响性能吗?
解决方案
由于我们无法访问实际编译的示例(这本来很好),我实际上并没有尝试编译下面的示例。尽管如此,除了一些小的错别字(也许)之外,总体思路应该很清楚。
任务是找到相似度的最大值和对应的标签,这个我们确实可以reduction
使用一次,为了reduction
在 OpenMP 中实现它。
我稍微重写了您的代码,使用temp
变量的原始命名 ( ) 可能会使事情变得更难阅读。基本上,我们并行执行搜索,因此每个线程找到一个最佳值,然后我们要求 OpenMP 找到线程之间的最佳解决方案 ( reduction
),我们就完成了。
//Reduce by finding the maximum and also storing the corresponding label, this is why we use a std::pair.
void reduce_custom (std::pair<float, unsigned int>& output, std::pair<float, unsigned int>& input) {
if (input.first > output.first) output = input;
}
//Declare an OpenMP reduction with our pair and our custom reduction function.
#pragma omp declare reduction(custom_reduction : \
std::pair<float, unsigned int>: \
reduce_custom(omp_out, omp_in)) \
initializer(omp_priv(omp_orig))
bool identify(const float* data, unsigned int length, unsigned int& label, float& similarity) {
std::pair<float, unsigned int> temp(0.0, label); //Stores thread local similarity and corresponding best label.
#pragma omp parallel for reduction(custom_reduction:temp)
for (size_t i = 0; i < collection.size(); ++i) {
const float* candidateTemplate = collection[i].first.data();
float consinSimilarity = getSimilarity(data, candidateTemplate, length);
if (consinSimilarity > temp.first) {
temp.first = consinSimilarity;
temp.second = collection[i].second;
}
}
if (temp.first > 0.f) {
similarity = temp.first;
label = temp.second;
return true;
}
return false;
}
关于您对 SIMD 寄存器数量有限的担忧,它们的数量取决于您使用的特定 CPU。据我所知,每个内核都有一定数量的可用向量寄存器,所以只要你使用的数量不超过可用的数量,现在也应该没问题,此外,AVX512 例如提供 32 个向量寄存器和 2 个每个核心的向量运算的算术单元,因此计算资源的用完并非易事,由于内存局部性差(特别是在您的情况下,向量被保存在所有地方),您更有可能遭受痛苦。我当然可能是错的,如果是这样,请随时在评论中纠正我。
推荐阅读
- javascript - 在 $(".sim-row-edit").mousedown 上显示右键菜单
- android - E/BitmapFactory:无法解码流:java.io.FileNotFoundException for(没有这样的文件或目录)
- npm - Npm 不工作,即使它显示版本
- mongodb - 查找与多个点相交的多个多边形
- shopify - Shopify 粗体应用无法验证地址
- mongodb - 默认情况下仅从上个月的平均值获取 Mongo 结果
- java - OpenAM 12 的本地 Maven 依赖项
- objective-c - 动态链接在 iOS 科尔多瓦应用程序上不起作用
- php - 下载 PDF 文件 - 存储在 sql 数据库中的文件路径
- angular - 通过服务类中的 observable 从 web socket 向组件提供数据