CODEWITHSUNDEEP
c++multithreadingopenmp
ChronoTrigger
ChronoTrigger

Reputation: 8607

Decreasing number of iterations in OpenMP parallel for

I have a parallel for in a C++ program that has to loop up to some number of iterations. Each iteration computes a possible solution for an algorithm, and I want to exit the loop once I find a valid one (it is ok if a few extra iterations are done). I know the number of iterations should be fixed from the beginning in the parallel for, but since I'm not increasing the number of iterations in the following code, is there any guarantee of that threads check the condition before proceeding with their current iteration?

void fun()
{
  int max_its = 100;

  #pragma omp parallel for schedule(dynamic, 1)
  for(int t = 0; t < max_its; ++t)
  {
    ...
    if(some condition)
      max_its = t; // valid to make threads exit the for?
  }
}

Upvotes: 2

Views: 805

Answers (3)

Michael Klemm
Michael Klemm

Reputation: 2853

Modifying the loop counter works for most implementations of OpenMP worksharing constructs, but the program will no longer be conforming to OpenMP and there is no guarantee that the program works with other compilers.

Since the OP is OK with some extra iterations, OpenMP cancellation will be the way to go. OpenMP 4.0 introduced the "cancel" construct exactly for this purpose. It will request termination of the worksharing construct and teleport the threads to the end of it.

void fun()
{
  int max_its = 100;

#pragma omp parallel for schedule(dynamic, 1)
  for(int t = 0; t < max_its; ++t)
  {
    ...
    if(some condition) {
#pragma omp cancel for
    }
#pragma omp cancellation point for
  }
}

Be aware that might there might be a price to pay in terms of performance, but you might want to accept this if the overall performance is better when aborting the loop.

In pre-4.0 implementations of OpenMP, the only OpenMP-compliant solution would be to have an if statement to approach the regular end of the loop as quickly as possible without execution the actual loop body:

void fun()
{
  int max_its = 100;

#pragma omp parallel for schedule(dynamic, 1)
  for(int t = 0; t < max_its; ++t)
  {
    if(!some condition) {
      ... loop body ...
    }
  }
}

Hope that helps!

Cheers, -michael

Upvotes: 3

Massimiliano
Massimiliano

Reputation: 8032

You can't modify max_its as the standard says it must be a loop invariant expression.

What you can do, though, is using a boolean shared variable as a flag:

void fun()
{
  int max_its = 100;
  bool found = false;
  #pragma omp parallel for schedule(dynamic, 1) shared(found)
  for(int t = 0; t < max_its; ++t)
  {
    if( ! found ) {
    ...
    }
    if(some condition) {
  #pragma omp atomic
      found = true; // valid to make threads exit the for?
    }
  }
}

A logic of this kind may be also implemented with tasks instead of a work-sharing construct. A sketch of the code would be something like the following:

void algorithm(int t, bool& found) {
#pragma omp task shared(found)
{
  if( !found ) {
    // Do work
    if ( /* conditionc*/ ) {
      #pragma omp atomic
      found = true
    }
  }
} // task
} // function


void fun()
{
  int max_its = 100;
  bool found  = false;
  #pragma omp parallel 
  {
    #pragma omp single
    {
      for(int t = 0; t < max_its; ++t)
      {
        algorithm(t,found);
      }
    } // single
  } // parallel
}

The idea is that a single thread creates max_its tasks. Each task will be assigned to a waiting thread. If some of the tasks find a valid solution, then all the others will be informed by the shared variable found.

Upvotes: 1

Mats Petersson
Mats Petersson

Reputation: 129314

If some_condition is a logical expression that is "always valid", then you could do:

for(int t = 0; t < max_its && !some_condition; ++t)

That way, it's very clear that !some_condition is required to continue the loop, and there is no need to read the rest of the code to find out that "if some_condition, loop ends"

Otherwise (for example if some_condition is the result of some calculation inside the loop and it's complicated to "move" the some_condition to the for-loop condition, then using break is clearly the right thing to do.

Upvotes: 0

Related Questions