c++ - tbb：并行查找第一个元素

Question

我遇到了这个问题：

查找列表中满足给定条件的第一个元素。

不幸的是，该列表很长（100.000 个元素），并且使用单个线程评估每个元素的条件总共需要大约 30 秒。

有没有办法干净地并行化这个问题？我浏览了所有的 tbb 模式，但找不到任何合适的。

更新：出于性能原因，我想在找到项目时尽早停止并停止处理列表的其余部分。这就是为什么我相信我不能使用parallel_whileor parallel_do。

score 1 · Accepted Answer

我对这个库不太熟悉，但只是大声思考，你能不能有一组线程从不同的凝视点以不同的步幅迭代？

假设您决定拥有n线程（= 内核数或其他），每个线程都应该有一个特定的起点，直到n，所以第一个线程开始于begin()，它比较的下一个项目是begin() + n，等等。第二个线程开始于begin()+1并且那么它的下一个比较n也是等等。

这样，您可以让一组线程在列表中并行迭代，迭代本身可能并不昂贵 - 只是比较。没有节点将被多次比较，您可以在任何线程进行匹配时设置一些条件，并且所有人都应该在迭代/比较之前检查这个条件。

我认为实现起来非常简单（？）

score 1 · Accepted Answer

我认为用 TBB 解决这个问题的最好方法是parallel_pipeline.

管道中应该有（至少）两个阶段。第一阶段是串行；它只是从列表中读取下一个元素并将其传递到第二阶段。这第二阶段是平行的；它评估给定元素的感兴趣条件。一旦满足条件，第二阶段就会设置一个标志（应该是原子的或用锁保护的）以指示找到了解决方案。第一阶段必须检查此标志并在找到解决方案后停止读取列表。

由于条件评估是针对少数元素并行执行的，因此找到的元素可能不是列表中第一个合适的元素。如果这很重要，您还需要保留元素的索引，并在找到合适的解决方案时检测其索引是否小于先前已知解决方案的索引（如果有）。

HTH。

score 1 · Accepted Answer

好的，我是这样做的：

将所有元素放入一个tbb::concurrent_bounded_queue<Element> elements.
创建一个空的tbb::concurrent_vector<Element> results.
创建一个boost::thread_group，并创建几个运行此逻辑的线程：

并行运行的逻辑：

Element e;
while (results.empty() && elements.try_pop(e) {
    if (slow_and_painfull_check(e)) {
         results.push_back(e);
    }
}

因此，当找到第一个元素时，所有其他线程将在下次检查时停止处理results.empty()。

可能有两个或多个线程正在处理一个slow_and_painfull_check返回 true 的元素，所以我只是将结果放入一个向量并在并行循环之外处理这个问题。

在线程组中的所有线程都完成后，我检查中的所有元素results并使用第一个出现的元素。

score 0 · Accepted Answer

0

如果您使用 GCC，GNU OpenMP 提供并行标准函数链接

于 2011-10-11T14:38:15.143 回答

score 0 · Accepted Answer

您不能将列表转换为平衡树或类似的吗？这样的数据结构更容易并行处理 - 通常你会收回你在第一次使它平衡时可能付出的开销......例如，如果你编写函数式代码，请查看这篇论文：Balanced trees inhabiting functional并行编程

score 0 · Accepted Answer

如果是链表，并行搜索不会增加太多速度。然而，链表在缓存中往往表现不佳。如果您有两个线程，您可能会获得微小的性能提升：一个执行 find_first_element，一个简单地遍历列表，确保在第一个线程之前不会超过 X（100？）。第二个线程不进行任何比较，但会确保为第一个线程尽可能地缓存项目。这可能会帮助您节省时间，或者可能没什么不同，或者可能会阻碍您。测试一切。

score 0 · Accepted Answer

您可以查看http://gcc.gnu.org/onlinedocs/libstdc++/manual/parallel_mode.html以了解并行算法的实现。特别是你需要 find_if 算法http://www.cplusplus.com/reference/algorithm/find_if/

score 0 · Accepted Answer

我在这里看到了两个并行的机会：在多个线程上评估一个元素，或者在不同的线程上一次评估多个元素。

没有足够的信息来确定在多个线程上评估一个元素的难度和有效性。如果这很容易，则可以减少每个元素 30 秒的时间。

对于这个问题，我看不出完全适合 TBB。列表没有随机访问迭代器、确定何时停止以及保证找到第一个元素存在问题。不过，您可能可以使用范围玩一些游戏以使其正常工作。

您也可以使用一些较低级别的线程构造来自己实现这一点，但是有很多地方会返回不正确的结果。为防止此类错误，我建议使用现有算法。您可以将列表转换为数组（或其他具有随机访问迭代器的结构），并使用引用的实验性 libstdc++ Parellel Mode find_if 算法 user383522。

score -1 · Accepted Answer

我从未听说过 Intel tbb 库，但快速打开并浏览教程让我parallel_for发现它似乎可以解决问题。

c++ - tbb：并行查找第一个元素

9 回答 9

Related

Reference