为什么这种搜索方法不可扩展？

Question

我想使用openMP并行搜索算法, vTree是一个二叉搜索树,我想为每个点集应用我的搜索算法.下面是我的代码片段.两点的搜索过程完全不相关,因此可以是并行的.虽然他们确实需要读取同一棵树,但一旦构建,树就不会再被修改了.因此它是只读的.

但是,下面的代码显示了可怕的可扩展性,在我的32核平台上,只实现了2倍的加速.是因为vTree所有线程都读取了它？如果是这样,我该如何进一步优化代码？

    auto results = vector<vector<Point>>(particleNum);
    auto t3 = high_resolution_clock::now();
    double radius = 1.6;
#pragma omp parallel for
    for (decltype(points.size()) i = 0; i < points.size(); i++)
    {
        vTree.search(points[i], radius, results[i]);
    }
    auto t4 = high_resolution_clock::now();
    double searchTime = duration_cast<duration<double>>(t4 - t3).count();

类型签名search是

void VPTree::search(const Point& p, double radius, vector<Point>& result) const

搜索结果将被放入result.

Answer 1

我最好的猜测是您正在对结果向量进行缓存乒乓操作。我假设您的“搜索”函数使用传入的结果向量作为放置点的位置，并且您在整个算法中使用它来在搜索树中遇到邻居时插入它们。每当您向该结果向量添加一个点时，该向量对象的内部数据都会被修改。由于所有结果向量都打包在连续的内存中，因此不同的结果向量很可能占用相同的缓存行。所以，当CPU保持缓存一致性时，它会不断地锁定相关的缓存行。

解决这个问题的方法是使用一个内部的临时向量，您只在最后将其分配给结果向量一次（如果您使用移动语义，则可以便宜地完成）。像这样的东西：

void VPTree::search(const Point& p, double radius, vector<Point>& result) const {
  vector<Point> tmp_result;
  // ... add results to "tmp_result"
  result = std::move(tmp_result);
  return;
}

或者，您也可以仅按值返回向量（这隐式使用移动）：

vector<Point> VPTree::search(const Point& p, double radius) const {
  vector<Point> result;
  // ... add results to "result"
  return result;
}

欢迎来到移动语义的欢乐世界，以及它在解决这些类型的并发/缓存一致性问题方面的神奇之处。

也可以想象，您遇到了与从所有线程访问同一棵树相关的问题，但由于它都是只读操作，我很确定即使在像 x86（和其他 Intel / AMD CPU）这样的保守架构上也是如此这不应该造成重大问题，但我可能是错的（也许是一种“过度订阅”问题，但这是可疑的）。其他问题可能包括 OpenMP 确实会产生相当多的开销（生成线程、同步等），这些开销必须根据您在这些并行循环中执行的实际操作的计算成本进行权衡（而且并不总是如此）有利的权衡）。而且，如果您的 VPTree（我想代表“Vantage-point Tree”）没有良好的引用局部性（例如，您将其实现为链接树），那么无论您使用哪种方式，性能都会很糟糕它（正如我在这里解释的那样）。