Riduzione su array in OpenMP

Sto cercando di parallelizzare il seguente programma, ma non so come ridurre su un array. So che non è ansible farlo, ma c’è un’alternativa? Grazie. (Ho aggiunto una riduzione su m che è sbagliato ma vorrei avere un consiglio su come farlo).

#include  #include  #include  #include  using namespace std; int main () { int A [] = {84, 30, 95, 94, 36, 73, 52, 23, 2, 13}; int S [10]; time_t start_time = time(NULL); #pragma omp parallel for private(m) reduction(+:m) for (int n=0 ; n<10 ; ++n ){ for (int m=0; m<=n; ++m){ S[n] += A[m]; } } time_t end_time = time(NULL); cout << end_time-start_time; return 0; } 

Sì, è ansible ridurre gli array con OpenMP. In Fortran ha anche costruito per questo. In C / C ++ devi farlo da solo. Ecco due modi per farlo.

Il primo metodo rende la versione privata di S per ogni thread, li riempie in parallelo e quindi li unisce in S in una sezione critica (vedere il codice seguente). Il secondo metodo crea un array con dimensioni 10 * nthreads. Riempie questo array in parallelo e quindi lo unisce in S senza utilizzare una sezione critica. Il secondo metodo è molto più complicato e può avere problemi di cache, specialmente sui sistemi multi-socket, se non si presta attenzione. Per ulteriori dettagli, consultare questo istogramma di riempimento (riduzione dell’array) in parallelo con OpenMP senza utilizzare una sezione critica

Primo metodo

 int A [] = {84, 30, 95, 94, 36, 73, 52, 23, 2, 13}; int S [10] = {0}; #pragma omp parallel { int S_private[10] = {0}; #pragma omp for for (int n=0 ; n<10 ; ++n ) { for (int m=0; m< =n; ++m){ S_private[n] += A[m]; } } #pragma omp critical { for(int n=0; n<10; ++n) { S[n] += S_private[n]; } } } 

Secondo metodo

 int A [] = {84, 30, 95, 94, 36, 73, 52, 23, 2, 13}; int S [10] = {0}; int *S_private; #pragma omp parallel { const int nthreads = omp_get_num_threads(); const int ithread = omp_get_thread_num(); #pragma omp single { S_private = new int[10*nthreads]; for(int i=0; i< (10*nthreads); i++) S_private[i] = 0; } #pragma omp for for (int n=0 ; n<10 ; ++n ) { for (int m=0; m<=n; ++m){ S_private[ithread*10+n] += A[m]; } } #pragma omp for for(int i=0; i<10; i++) { for(int t=0; t 

Ho due osservazioni riguardo alla risposta di Zboson:
1. Il metodo 1 è sicuramente corretto ma il ciclo di riduzione è in realtà eseguito in serie, a causa del #pragma omp critical che è ovviamente necessario in quanto le matrici parziali sono locali per ogni thread e la riduzione corrispondente deve essere eseguita dal thread dovuto al thread matrice.
2. Metodo 2: il ciclo di inizializzazione può essere spostato all’esterno della singola sezione e quindi diventare parallelizzabile.

Il seguente programma implementa la riduzione dell’array usando la funzione di riduzione definita dall’utente openMP v4.0 :

 /* Compile with: gcc -Wall -fopenmp -o ar ar.c Run with: OMP_DISPLAY_ENV=TRUE OMP_NUM_THREADS=10 OMP_NESTED=TRUE ./ar */ #include  #include  struct m10x1 {int v[10];}; int A [] = {84, 30, 95, 94, 36, 73, 52, 23, 2, 13}; struct m10x1 S = {{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}; int n,m=0; void print_m10x1(struct m10x1 x){ int i; for(i=0;i<10;i++) printf("%d ",xv[i]); printf("\n"); } struct m10x1 add_m10x1(struct m10x1 x,struct m10x1 y){ struct m10x1 r ={{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}; int i; for (i=0;i<10;i++) rv[i]=xv[i]+yv[i]; return r; } #pragma omp declare reduction(m10x1Add: struct m10x1: \ omp_out=add_m10x1(omp_out, omp_in)) initializer( \ omp_priv={{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}} ) int main () { #pragma omp parallel for reduction(m10x1Add: S) for ( n=0 ; n<10 ; ++n ) { for (m=0; m< =n; ++m){ Sv[n] += A[m]; } } print_m10x1(S); } 

Questo segue fedelmente l'esempio di riduzione del numero complesso a pagina 97 delle funzionalità di OpenMP 4.0 .

Sebbene la versione parallela funzioni correttamente, ci sono probabilmente problemi di prestazioni, che non ho esaminato:

  1. add_m10x1 input e output sono passati per valore.
  2. Il ciclo in add_m10x1 viene eseguito in serie.

Detto "problemi di prestazioni" sono di mia creazione ed è del tutto semplice non presentarli:

  1. I parametri per add_m10x1 devono essere passati per riferimento (tramite puntatori in C, riferimenti in C ++)
  2. Il calcolo in add_m10x1 dovrebbe essere fatto sul posto.
  3. add_m10x1 deve essere dichiarato nullo e l'istruzione di reso cancellata. Il risultato viene restituito tramite il primo parametro.
  4. Il pragrafo di riduzione della dichiarazione deve essere modificato di conseguenza, il combinatore dovrebbe essere solo una chiamata di funzione e non un compito (v4.0 spec. P181 righe 9,10).
  5. Il ciclo for in add_m10x1 può essere parallelizzato tramite un parallelo omp per pragma
  6. Il nesting parallelo deve essere abilitato (ad es. Tramite OMP_NESTED = TRUE)

La parte modificata del codice è quindi:

 void add_m10x1(struct m10x1 * x,struct m10x1 * y){ int i; #pragma omp parallel for for (i=0;i<10;i++) x->v[i] += y->v[i]; } #pragma omp declare reduction(m10x1Add: struct m10x1: \ add_m10x1(&omp_out, &omp_in)) initializer( \ omp_priv={{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}} ) 

Se la traduzione del tuo codice in Fortran, che può utilizzare gli array nelle operazioni di riduzione di OpenMP, non fa appello, puoi utilizzare un gruppo di variabili temporanee. Per esempio

 int S0, S1, S2, ..., S9; ... #pragma omp parallel for private(...) shared(S0, S1, S2, ..., S9) \ reduction(+:S0, S1, S2, ..., S9) for ... 

Questo ti lascia con la prospettiva poco invitante di dover scrivere una sorta di if o case statement per determinare quale dei temporanei deve essere aggiornato. Se il tuo codice è solo un esempio che vuoi utilizzare per l’apprendimento, continua.

Ma se la tua intenzione è sinceramente di scrivere una routine di sum di prefissi paralleli, allora cerca in giro. Questo è un buon punto di partenza.