omp max reduction with storage of index

Question

Using c++ openmp 3.1 I implemented a max reduction which stores the maximum value of integer variable (score) of an vector of objects (s). But I also want to store the vector index to acces the (s) object with the maximum score. My current unsuccesfull implementation looks like this:

//s is a vector of sol objects which contain apart from other variables an  integer     score    variable s[].score            
int bestscore = 0;
int bestant = 0;                
#pragma omp parallel shared(bestant)
{//start parallel session
    #pragma omp for    nowait reduction(max : bestscore)
    for (int ant = 0; ant<maxsols; ++ant) // for all ants
    {
        //procedures on s[ant] object which update the  int s[ant].score
        if (s[ant].score > bestscore)
        {
            //find the object with the highest score
            bestscore = s[ant].score;
            bestant = ant;//i also want know which ant has the highest score
        }
    }
}

The code compiles and runs. the maximum bestscore is found but bestant gets a random index. The ant linked to the fastest thread to finish gets stored in bestant. bestscore start with a value of 0 so in most cases s[ant].score will have a higher score and bestscore and bestant are updated. I think I need a reduction operator for bestant like "on update of bestscore".

Answer 1

The reason (as you suspect) why bestant gets a random index i is because bestant is shared and does not benefit from the reduction clause as bestscore does. The solution proposed by Z boson is fine: the critical instruction block is executed only once by thread so that the overhead should be limited.

You were using a OpenMP 3.1 runtime at that time. I wanted to post to explain that this limitation has been addressed since OpenMP 4.0. You can now write a user defined operator (see 2.19.5.7 declare reduction Directive).

In your case, a solution can be to pack the two values in a struct and define how two such struct elements combine in the end of the #pragma parallel for loop.

//s is a vector of sol objects which contain apart from other variables an  integer     score    variable s[].score

typedef struct {
  int score;
  int ant;
} best_t;

best_t best = { 0, 0 };

// we declare our user reduction operator :
// it is called get_max, return a a value of type best_t.
// omp_out and omp_in are the predefined names of two private elements
// to combine in the end to the final shared variable.

#pragma omp declare reduction(get_max : best_t :\
    omp_out = omp_out.score > omp_in.score ? omp_out : omp_in)\
    initializer (omp_priv=(omp_orig))

                
#pragma omp parallel 
{//start parallel session
    #pragma omp for    nowait reduction(get_max : best)
    for (int ant = 0; ant<maxsols; ++ant) // for all ants
    {
        //procedures on s[ant] object which update the  int s[ant].score
        if (s[ant].score > best.score)
        {
            //find the object with the highest score
            best.score = s[ant].score;
            best.ant = ant;
        }
    }
}

Answer 2

Two observations:

• I think you only need to compare bestscore_private to bestscore when its value is changed, this way the number of comparisons is reduced.

• Also, at least in todays omp you can utilize a critical section inside the if conditional, this way comparisons between bestscore_private a bestscore would be carried out in parallel and the infrequent (hope so) update to bestscore will be carried out in a critical manner.

  int bestscore = 0; int bestant = 0; #pragma omp parallel {

    int bestscore_private = 0;
    int bestant_private = 0;
    #pragma omp for nowait
    for (int ant = 0; ant<maxsols; ++ant) {         
        if (s[ant].score > bestscore_private) {
            bestscore_private = s[ant].score;
            bestant_private = ant;   
            if(bestscore_private>bestscore){   
              #pragma omp critical 
              {
  
              bestscore = bestscore_private;
              bestant = besant_private;
              }
            }
        }
    }
  

  }

Answer 3

Try this

int bestscore = 0;
int bestant = 0;
#pragma omp parallel
{
    int bestscore_private = 0;
    int bestant_private = 0;
    #pragma omp for nowait
    for (int ant = 0; ant<maxsols; ++ant) {         
        if (s[ant].score > bestscore_private) {
            bestscore_private = s[ant].score;
            bestant_private = ant;
        }
    }
    #pragma omp critical 
    {
        if(bestscore_private>bestscore) {
            bestscore = bestscore_private;
            bestant = besant_private;
        }
    }
}