Wie gehe ich mit einem Datenrennen in OpenMP um?

Question

Ich versuche, OpenMP zu verwenden, um die Zahlen in einem Array hinzuzufügen. Im Folgenden ist mein Code:

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

Dies führt nicht das richtige Ergebnis für sum. Was ist los mit dir?

Answer 1

Ihr Code hat derzeit eine race condition, weshalb das Ergebnis nicht korrekt ist. Um dies zu veranschaulichen, verwenden wir ein einfaches Beispiel:

Sie laufen auf 2 Threads und das Array ist int input[4] = {1, 2, 3, 4};. Sie initialisieren sum korrekt zu 0 und sind bereit, die Schleife zu starten. In der ersten Iteration Ihrer Schleife lesen Thread 0 und Thread 1 sum aus dem Speicher als 0 und fügen dann ihr jeweiliges Element zu sum hinzu und schreiben es zurück in den Speicher. Dies bedeutet jedoch, dass Thread 0 versucht, 0123,in den Speicher zu schreiben (das erste Element ist 1 und sum = 0 + 1 = 1), während Thread 1 versucht, sum = 2 in den Speicher zu schreiben (das zweite Element ist 2 und sum = 0 + 2 = 2). Das Endergebnis dieses Codes hängt davon ab, welcher der beiden Threads zuletzt beendet wurde und daher zuletzt in den Speicher schreibt, was eine Race-Bedingung ist. Nicht nur das, aber in diesem speziellen Fall sind keine der Antworten, die der Code erzeugen konnte, richtig! Es gibt mehrere Möglichkeiten, dies zu umgehen; Ich werde Detail drei grundlegend diejenigen unter:

#pragma omp critical:

In OpenMP, gibt es, was eine critical Richtlinie genannt wird. Dies beschränkt den Code so, dass nur ein Thread gleichzeitig etwas tun kann. Zum Beispiel Ihre for -loop kann geschrieben werden:

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

Dadurch entfällt die Race-Bedingung als nur ein Thread zugreift und schreibt sum zu einem Zeitpunkt. Allerdings ist die critical Direktive sehr schlecht für die Leistung und wird wahrscheinlich einen großen Teil (wenn nicht alle) der Gewinne zunichte machen, die Sie durch die Verwendung von OpenMP an erster Stelle bekommen.

#pragma omp atomic:

Die atomic Richtlinie ist sehr ähnlich wie die critical Richtlinie. Der Hauptunterschied besteht darin, dass die Anweisung critical für alles gilt, das Sie jeweils nur einen Thread gleichzeitig ausführen möchten, die Anweisung atomic gilt jedoch nur für Lese-/Schreibvorgänge im Speicher. Wie alles, was wir in diesem Codebeispiel tun, ist das Lesen und Schreiben zu summieren, wird diese Richtlinie perfekt funktionieren:

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

Die Leistung von atomic im Allgemeinen, dass deutlich besser ist als von critical. Es ist jedoch immer noch nicht die beste Option in Ihrem Fall.

reduction:

Die Methode, die Sie sollten, und die Methode verwenden, die bereits von anderen vorgeschlagen wurde, ist reduction. Sie können dies tun, indem Sie die for -loop Wechsel zu:

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

Der reduction Befehl teilt OpenMP, die, während die Schleife ausgeführt wird, können Sie jeder Thread wollen im Auge zu behalten ihre eigene sum Variable, und fügen Sie sie alle am Ende der Schleife. Dies ist die effizienteste Methode, da Ihre gesamte Schleife jetzt parallel ausgeführt wird, mit dem einzigen Overhead, der direkt am Ende der Schleife liegt, wenn die sum Werte der einzelnen Threads addiert werden müssen.

Answer 2

Verwenden Sie reduction Klausel (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]; 
}