CODEWITHSUNDEEP
carraysfor-loopopenmpincrement
Michael
Michael

Reputation: 51

Parallel incrementing of array elements with OpenMP

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?

Upvotes: 5

Views: 2127

Answers (3)

Z boson
Z boson

Reputation: 33709

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("");
}

Upvotes: 2

Bryan Calvo Benoit
Bryan Calvo Benoit

Reputation: 81

You can use 2 "for()" one for each array

Upvotes: 0

shredder
shredder

Reputation: 11

If any of the values in a[] are identical then you would be writing to the same element of b simultaneously.

a[0] = 1 and a[1] = 1 then you would be writing to b[1] at the same time.

Upvotes: 0

Related Questions