Parallel incrementing of array elements with OpenMP

Question

I have array a of size N with random numbers. Using OpenMP I want to increment elements 0 to 9 of array b of size 10 for every number in A. The language is C.

#pragma omp parallel for
for(i = 0; i < N; i++)
   b[a[i]]++;

Unfortunately there are apparently simultanous writes in some elements of b and the result is not as expected. I tried it with setting b to firstprivate and lastprivate but this didn't help either.

The task seems simple but I don't know how to do it as there is no atomic for arrays in OpenMP. I could create a new array for the number of threads and then add them together in the end but that doesn't seem optimal.

Which would be the fastest way to count the occurences of the numbers in a in the elements of array b?

Answer 1

Your question is essentially a duplicate of a question I asked fill-histograms-in-parallel-with-openmp-without-using-a-critical-section.

The easy solution in your case is

#pragma omp parallel
{
    int i, b_local[10] = {0};
    #pragma omp for nowait 
    for(i = 0; i < n; i++) b_local[a[i]]++;
    #pragma omp critical
    for(i=0; i<10; i++) b[i] += b_local[i];    
}

It's possible to do this without a critical section (see my question) but it's not necessarily more efficient.

Here's a working example

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define N 100

void foo(int *b, int *a, int n) {
    #pragma omp parallel
    {
        int i, b_local[10];
        memset(b_local, 0, 10*sizeof(int));
        #pragma omp for 
        for(i = 0; i < n; i++) b_local[a[i]]++;


        #pragma omp critical
        {     
            for(i=0; i<10; i++) {
                b[i] += b_local[i]; 
            }
        }

    }
}

int main() {   
    int i;
    int b[10] = {0,1,2,3,4,5,6,7,8,9};
    int b2[10] = {0,1,2,3,4,5,6,7,8,9};
    int a[N];
    for(i=0; i<N; i++) a[i] = rand()%10;

    foo(b,a,N);
    for(i=0; i<N; i++) b2[a[i]]++;
    for(i=0; i<10; i++) printf("%d ", b[i]); puts("");
    for(i=0; i<10; i++) printf("%d ", b2[i]); puts("");
}