2

Is there any way I could use openMP to parallelize a loop with a list that might have more elements added each iteration? As far as I understand openMP can parallelize a for loop by diving the range in chunks for each thread, but in this case the range changes, for one case the loop might have 10 iterations and for another one 100, the thing is that in the list I will usually have around 10-20 elements.

Here's an example of what I'd like to parallelize (note that the order in which things are inserted into the vectorOfResults doesn't matter)

while(!list.empty()) {
 vectorOfResults.push_back(performExpensiveFunction());
 if (conditions) {
   add new elements to the list;
 }
}

I've been thinking about doing something like, inside the while loop, have a for loop with the current "batch" of elements in the list (copy them in a temporary list) and then the next while iteration will use the newly added elements, but I was thinking if there was a way to do this using other openmp constructs. (I only now a little bit about openmp).

Thanks for your help.

David Moreno
  • 141
  • 9
  • 1
    Please check if [this answer](https://stackoverflow.com/a/44083682/620382) helps you. While it is a more specific context, I believe it applies also to your more generic case. – Zulan Nov 06 '19 at 17:17

1 Answers1

1

I don't think its possible to grow the size of a parallel for loop once it has been started.

You can run multiple parallel for loops one after the other until all the data has been processed as proposed in this answer. Something like:

Data proccessInParallel(Data d) {
    Data newData
    #pragma omp parellel for
    for (int i = 0; i < d.size i++) {
        // Do some processing
        if (create_new) {
            #pragma omp critical
            {
                newData.push_back(data)
            }
        }
    }
    return newData;
}

int main() {
   Data data;
   // Process data in batches until no new data is created
   do {
       data = proccessInParallel(data);
   } while (!data.empty());

The downside being that some threads may be unused while between "batches" being processed.

You can also try using tasks to analyze new list items without waiting to start another for loop.

Maybe something like:


#pragma omp parallel for
for (int i = 0; i < N; i++) {
    process(data[i]);
    if (new_data) {
        #pragma omp task
        {
        process(new_data);
        }
    }
}

The task will execute as soon as a thread becomes available to execute it.

Increasingly Idiotic
  • 5,700
  • 5
  • 35
  • 73