tbb:并行查找第一个元素 [英] tbb: parallel find first element

问题描述

我遇到了这个问题:

• 找到列表中的第一个元素，并满足该条件.

不幸的是，该列表相当长(100.000个元素)，并且使用一个单个线程评估每个元素的条件总共花费大约30秒.

Unfortunately, the list is quite long (100.000 elements), and evaluation the condition for each element takes in total about 30 seconds using one single Thread.

是否有一种方法可以完全并行化此问题?我已经浏览了所有的tbb模式，但是找不到任何合适的模式.

Is there a way to cleanly parallelize this problem? I have looked through all the tbb patterns, but could not find any fitting.

更新:出于性能原因，我想在找到某项内容时尽早停止并停止处理列表的其余部分.这就是为什么我认为我不能使用parallel_while或parallel_do的原因.

UPDATE: for performance reason, I want to stop as early as possible when an item is found and stop processing the rest of the list. That's why I believe I cannot use parallel_while or parallel_do.

推荐答案

好的，我已经这样做了:

ok, I have done it this way:

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

1. Put all elements into a tbb::concurrent_bounded_queue<Element> elements.
2. Create an empty tbb::concurrent_vector<Element> results.
3. Create a boost::thread_group, and create several threads that run this logic:

可并行运行的逻辑:

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

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

So when the first element is found, all other threads will stop processing the next time they check results.empty().

在slow_and_painfull_check返回true的元素上可能有两个或多个线程在工作，因此我只是将结果放入向量中，并在并行循环之外进行处理.

It is possible that two or more threads are working on an element for which slow_and_painfull_check returns true, so I just put the result into a vector and deal with this outside of the parallel loop.

在线程组中的所有线程完成之后，我检查了results中的所有元素，并使用最先出现的元素.

After all threads in the thread group have finished, I check all elements in the results and use the one that comes first.

这篇关于tbb:并行查找第一个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！