tbb: parallel find first element

Question

I have got this problem:

• Find the first element in a list, for which a given condition holds.

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.

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

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.

Answer 1

ok, I have done it this way:

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:

logic to run in parallel:

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

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

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.

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

Answer 2

I think the best way to solve this problem with TBB is parallel_pipeline.

There should be (at least) two stages in the pipeline. The 1st stage is serial; it just reads the next element from the list and passes it to the 2nd stage. This 2nd stage is parallel; it evaluates the condition of interest for a given element. As soon as the condition is met, the second stage sets a flag (which should be either atomic or protected with a lock) to indicate that a solution is found. The first stage must check this flag and stop reading the list once the solution is found.

Since condition evaluation is performed in parallel for a few elements, it can happen that a found element is not the first suitable one in the list. If this is important, you also need to keep an index of the element, and when a suitable solution is found you detect whether its index is less than that of a previously known solution (if any).

HTH.

Answer 3

I've never heard of the Intel tbb library but a quick open and scan of the Tutorial led me to parallel_for which seems like it will do the trick.