Come posso gestire una corsa di dati in OpenMP?

Question

Sto cercando di utilizzare OpenMP per aggiungere i numeri in un array. Quanto segue è il mio codice:

int* input = (int*) malloc (sizeof(int)*snum); 
    int sum = 0; 
    int i; 
    for(i=0;i<snum;i++){ 
     input[i] = i+1; 
    } 
    #pragma omp parallel for schedule(static) 
    for(i=0;i<snum;i++) 
    { 
     int* tmpsum = input+i; 
sum += *tmpsum; 
    } 

Questo non produce il risultato giusto per sum. Cosa c'è che non va?

Answer 1

Il codice ha attualmente un race condition, motivo per cui il risultato non è corretto. Per illustrare il motivo di ciò, utilizziamo un semplice esempio:

Si sta eseguendo su 2 thread e l'array è int input[4] = {1, 2, 3, 4};. Si inizializza sum su 0 correttamente e si è pronti per avviare il ciclo. Nella prima iterazione del ciclo, thread 0 e thread 1 leggono sum dalla memoria come 0, quindi aggiungono il rispettivo elemento a sum e lo riscrivono in memoria. Tuttavia, ciò significa che il thread 0 sta tentando di scrivere sum = 1 in memoria (il primo elemento è 1 e sum = 0 + 1 = 1), mentre il thread 1 sta tentando di scrivere sum = 2 in memoria (il secondo elemento è 2 e sum = 0 + 2 = 2). Il risultato finale di questo codice dipende da quale dei thread finisce per ultimo, quindi scrive in memoria per ultimo, che è una condizione di competizione. Non solo, ma in questo caso particolare, nessuna delle risposte che il codice potrebbe produrre sono corrette! Ci sono diversi modi per aggirare questo; Io particolare tre quelli di base di seguito:

#pragma omp critical:

In OpenMP, v'è quello che viene chiamato una direttiva critical. Questo limita il codice in modo che solo un thread possa fare qualcosa alla volta. Ad esempio, il for -loop può essere scritto:

#pragma omp parallel for schedule(static) 
for(i = 0; i < snum; i++) { 
    int *tmpsum = input + i; 
#pragma omp critical 
    sum += *tmpsum; 
} 

Questo elimina la condizione di competizione, come un solo thread accede e scrive a sum alla volta. Tuttavia, la direttiva critical è molto pessima per le prestazioni e probabilmente ucciderà una parte considerevole (se non tutti) dei guadagni ottenuti usando OpenMP in primo luogo.

#pragma omp atomic:

La direttiva atomic è molto simile alla direttiva critical. La principale differenza è che, mentre la direttiva critical si applica a tutto ciò che si desidera fare un thread alla volta, la direttiva atomic si applica solo alle operazioni di lettura/scrittura della memoria. Come tutto quello che stiamo facendo in questo esempio di codice è la lettura e la scrittura di riassumere, questa direttiva funziona perfettamente:

#pragma omp parallel for schedule(static) 
for(i = 0; i < snum; i++) { 
    int *tmpsum = input + i; 
#pragma omp atomic 
    sum += *tmpsum; 
} 

Le prestazioni di atomic è generalmente significativamente migliore di quella di critical. Tuttavia, non è ancora l'opzione migliore nel tuo caso particolare.

reduction:

Il metodo si dovrebbe usare, e il metodo che è già stato suggerito da altri, è reduction. È possibile farlo modificando il for -loop a:

#pragma omp parallel for schedule(static) reduction(+:sum) 
for(i = 0; i < snum; i++) { 
    int *tmpsum = input + i; 
    sum += *tmpsum; 
} 

Il comando reduction dice OpenMP che, mentre il ciclo è in funzione, si desidera che ogni filo per tenere traccia della propria sum variabile, e tutti si sommano alla fine del ciclo. Questo è il metodo più efficiente in quanto l'intero ciclo viene eseguito in parallelo, con l'unico sovraccarico proprio alla fine del ciclo, quando è necessario aggiungere i valori sum di ciascuno dei thread.

Answer 2

Utilizzare la clausola reduction (description at MSDN).

int* input = (int*) malloc (sizeof(int)*snum); 
int sum = 0; 
int i; 
for(i=0;i<snum;i++){ 
    input[i] = i+1; 
} 
#pragma omp parallel for schedule(static) reduction(+:sum) 
for(i=0;i<snum;i++) 
{ 
    sum += input[i]; 
}