Parallelize min-search loop

General OpenMP discussion

Parallelize min-search loop

Postby fabian » Tue Aug 21, 2012 11:37 am

Hi,

I'm new to OpenMP and i have a problem parallelizing a loop.
The problem is, that inside the loop a minimum has to be found and stored.
The results are different w/wout OpenMP.

Till now my code looks like this:

Code: Select all
int savek = -1;
int savel = -1;
minscore = -1;
int count = 0;

for (int k=0; k<k_count; k++) {
   #pragma omp parallel for
   for (int l=0; l<l_count; l++) {
      count++;
      
      int score = calc_score(k, l);
      if (score<minscore || minscore==-1) {
         minscore = score;
         savek = k;
         savel = l;
      }
   }
}


can someone please help me with these first steps ?

thx,
fabian
fabian
 
Posts: 3
Joined: Tue Aug 21, 2012 8:10 am

Re: Parallelize min-search loop

Postby MarkB » Wed Aug 22, 2012 4:34 am

Hi Fabian,

This pattern is a little bit tricky to do in OpenMP. If it were not for the requirement to save the location of the minimum, you could simply declare minscore in a reduction clause with the min operator. Instead, you need to do something like this:

Code: Select all
   
    int savek = -1;
    int savel = -1;
    minscore = -1;
    int count = 0;
    int t_minscore, t_savek, t_savel;

    for (int k=0; k<k_count; k++) {
#pragma omp parallel reduction(+:count) shared(minscore,savek,savel,l_count) private(t_minscore, t_savek, t_savel)
{
      t_minscore = minscore;
      t_savek = savek;
      t_savel = savel;

#pragma omp for
       for (int l=0; l<l_count; l++) {
          count++;
         
          int score = calc_score(k, l);
          if (score<t_minscore || t_minscore==-1) {
             t_minscore = score;
             t_savek = k;
             t_savel = l;
          }
#pragma omp critical
{

     if (t_minscore < minscore ) {
          minscore = t_minscore;
          save_k= t_savek;
          save_l = t_savel;
    }

} //end critical
} //end parallel region


       }
    }


Hope that helps,
Mark.
MarkB
 
Posts: 427
Joined: Thu Jan 08, 2009 10:12 am

Re: Parallelize min-search loop

Postby fabian » Wed Aug 22, 2012 8:29 am

Hi Mark,
thx for your help !

That works...

Just 3 questions for broader understanding:
1) Use have an uninitalized and unused variable l_count in the shared section of the parallel pragma.
Just a relict from coding ?

2) You use these private variables t_...,
and than in a critical-block you assign their values to the "real" variables.
Why not just do all in one crital-block without private variables ?

3) I somehow must have overread it or something,
but i don't understand the sense of "shared" - are not all used variables shared by default ?
fabian
 
Posts: 3
Joined: Tue Aug 21, 2012 8:10 am

Re: Parallelize min-search loop

Postby MarkB » Wed Aug 22, 2012 8:44 am

fabian wrote:Hi Mark,
thx for your help !


You're welcome!

fabian wrote:1) Use have an uninitalized and unused variable l_count in the shared section of the parallel pragma.
Just a relict from coding ?


It's not unused: it's the upper bound for the parallel loop!

fabian wrote:2) You use these private variables t_...,
and than in a critical-block you assign their values to the "real" variables.
Why not just do all in one crital-block without private variables ?


Because then the critical section would be inside the parallel loop, and would be entered/exited many times per thread instead of once. If the
calc_score function is very expensive, then this additional overhead may not matter too much.


fabian wrote:3) I somehow must have overread it or something,
but i don't understand the sense of "shared" - are not all used variables shared by default ?


You are right they are: I just declared them shared to make the code clear. In general it is a good idea to use the default(none) clause and explicitly declare all referenced variables as shared/private/reduction etc. Otherwise it's all too easy to overlook a variable which ought not to be shared and end up with a race condition which may be hard to debug.

Mark.
MarkB
 
Posts: 427
Joined: Thu Jan 08, 2009 10:12 am

Re: Parallelize min-search loop

Postby fabian » Wed Aug 22, 2012 10:36 am

MarkB wrote:It's not unused: it's the upper bound for the parallel loop!

Ups... Sorry, i overlooked, that I replaced this variable by myself to get easier sample code ;)

MarkB wrote:Because then the critical section would be inside the parallel loop, and would be entered/exited many times per thread instead of once. If the calc_score function is very expensive, then this additional overhead may not matter too much.

Ah, but actually it still is in the for loop in you sample code. I think there are some brackets wrong in your code.
But got the point of that.

MarkB wrote:In general it is a good idea to use the default(none) clause and explicitly declare all referenced variables as shared/private/reduction etc.

I see the point in that.

THX again
fabian
 
Posts: 3
Joined: Tue Aug 21, 2012 8:10 am

Re: Parallelize min-search loop

Postby MarkB » Wed Aug 22, 2012 11:02 am

fabian wrote:Ah, but actually it still is in the for loop in you sample code. I think there are some brackets wrong in your code.


Oh dear, sorry about that! This is more like it:

Code: Select all
       
        int savek = -1;
        int savel = -1;
        minscore = -1;
        int count = 0;
        int t_minscore, t_savek, t_savel;

        for (int k=0; k<k_count; k++) {
    #pragma omp parallel reduction(+:count) shared(minscore,savek,savel,l_count) private(t_minscore, t_savek, t_savel)
    {
          t_minscore = minscore;
          t_savek = savek;
          t_savel = savel;

    #pragma omp for
           for (int l=0; l<l_count; l++) {
              count++;
             
              int score = calc_score(k, l);
              if (score<t_minscore || t_minscore==-1) {
                 t_minscore = score;
                 t_savek = k;
                 t_savel = l;
               }
           } // end parallel loop
    #pragma omp critical
       {

         if (t_minscore < minscore ) {
              minscore = t_minscore;
              save_k= t_savek;
              save_l = t_savel;
        }

       } //end critical
    } //end parallel region
} //end k loop
MarkB
 
Posts: 427
Joined: Thu Jan 08, 2009 10:12 am


Return to Using OpenMP

Who is online

Users browsing this forum: Majestic-12 [Bot] and 10 guests