## Parallelize min-search loop

General OpenMP discussion

### Parallelize min-search loop

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

### Re: Parallelize min-search loop

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: 746
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

### Re: Parallelize min-search loop

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

### Re: Parallelize min-search loop

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: 746
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

### Re: Parallelize min-search loop

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

### Re: Parallelize min-search loop

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: 746
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh