Równoległe powiększanie elementów tablicy za pomocą OpenMP

Question

Mam macierz a o rozmiarze N z liczbami losowymi. Korzystanie OpenMP Chcę zwiększyć elementy od 0 do 9 tablicy b o rozmiarze 10 dla każdego numeru w A. język jest C.

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

Niestety najwyraźniej jednoczesną pisze w niektórych elementów b, a wynik nie jest zgodnie z oczekiwaniami. Próbowałem go, ustawiając b na firstprivate i lastprivate, ale to też nie pomogło.

Zadanie wydaje się proste, ale nie wiem, jak to zrobić, ponieważ nie ma atomic dla tablic w OpenMP. Mogłem stworzyć nową tablicę dla liczby wątków, a następnie dodać ją razem, ale to nie wydaje się optymalne.

Jaki byłby najszybszy sposób zliczania wystąpień liczb w a w elementach tablicy b?

Answer 1

Jeśli którakolwiek z wartości w [] jest identyczna, to pisałbyś jednocześnie do tego samego elementu b.

a [0] = 1 i a [1] = 1 to pisanie do b [1] w tym samym czasie.

Answer 2

Można użyć 2 „dla()”, po jednym dla każdej tablicy

Answer 3

Twoje pytanie jest w zasadzie kopią pytanie zadałem fill-histograms-in-parallel-with-openmp-without-using-a-critical-section.

Proste rozwiązanie w Twoim przypadku jest

#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];  
} 

Jest możliwe, aby to zrobić bez sekcji krytycznej (patrz moje pytanie), ale nie jest to koniecznie bardziej wydajne.

Oto przykład pracuje

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