Calculate the histogram with OpenMP

Question

I want to parallelize this code getting the best performance. "histogram" stores number of appareances of a certain colour (there are 10 different colours, so the size of histogram is 10). "img" is an array which stores a certain image information. In each index of img is stored a colour (int value, range 0..9). This is the code:

for( i=0; i<N1; i++ ){
  for( j=0; j<N2; j++ ){
    histogram[ img[i][j] ]  = histogram[ img[i][j] ] + 1;
  }
}

I tried this but the performance is so bad (worse than serial execution):

#pragma omp parallel for schedule(static, N1/nthreads) private(i,j)
for(i=0; i<N1; i++){
  for(j=0; j<N2; j++)
  {
    #pragma omp atomic
    histogram[img[i][j]]++;
  }
}

Any suggestions? Thank you.

Answer 1

I already went into detail on how to to this here Fill histograms (array reduction) in parallel with OpenMP without using a critical section

It's the same as an array reduction. OpenMP does not have built in support for this in C/C++ (but it does in Fortran) so you have to do it yourself.

The easy solution is to create private version of the histogram, fill them in parallel, and them merge them into one histogram in a critical section. In your case you can do that like this:

int i, histogram[10];
for(i=0; i<10; i++) histogram[i] = 0;
#pragma omp parallel
{
    int i, j, histogram_private[10];
    for(i=0; i<10; i++) histogram_private[i] = 0;
    #pragma omp for nowait
    for(i=0; i<N1; i++) {
       for(j=0; j<N2; j++) {    
           histogram_private[img[i][j]]++;
       }
    }      
    #pragma omp critical 
    {
        for(i=0; i<10; i++) histogram[i] += histogram_private[i];
    }
}

It's possible to merge in parallel as well but that's more complicated. See the first link I mentioned for more details.

Answer 2

You want to create a kind of "reduction" so each thread should have its own histogram array and you have to merge all histo in a 2nd loop .... See pseudo code below:

histogram = new int[256];
histogram_thread = new int[nbthread * 256];

#pragma omp parallel 
for(i=0; i<N1; i++){
  current_thread_id = omp_get_thread_num();
  for(j=0; j<N2; j++)
  {
    histogram_thread[current_thread_id*256 + img[i][j]]++;
  }
}

//merge
for(unsigned int ui = 0 ; ui < 256 ; ++ui)
{ 
   for(int t=0; t<nbthread ; ++t) 
   {
      histogram [i] += histogram_thread[t * 256 + i];
   }
}

delete [] histogram_thread;

Answer 3

With OpenMP 4.5, you can simply use a array reduction in C:

int histogram[BINS] = {0};
#pragma omp parallel for reduction(+:hist)
for(i=0; i<N1; i++) {
   for(j=0; j<N2; j++) {    
       histogram[img[i][j]]++;
   }
}