OpenMP-Aufgaben - warum erscheint ein Segmentierungsfehler für eine größere Anzahl von Iterationen ~ 10k?

Question

Ich benutze den folgenden Code zum Finden der Summe der Elemente eines Arrays mit OpenMP-Aufgaben-Konstrukt.
Der Code liefert die korrekten Ergebnisse bis n = 10000.

Aber darüber hinaus bekomme ich einen Segmentierungsfehler. Unter Verwendung gdb fand ich, dass der Fehler in einem der rekursiven Aufrufe an reduce() auftritt. Es gibt kein Problem mit der Eingabe-Array-Zuweisung, und das habe ich verifiziert.

Hat jemand einen Vorschlag, was das Problem sein könnte?

int reduce (int *arr, unsigned long int n) 
{ 
    int x; 
    if (n <= 0) 
     return 0; 

    #pragma omp parallel 
    { 
     #pragma omp single nowait 
     { 
      #pragma omp task shared(x) 
      x = reduce(arr, n-1) + arr[n-1]; 
      #pragma omp taskwait 
     } 
    } 
    return x; 
} 

Answer 1

Es sieht aus als ob Sie einen "Stapelüberlauf" über die Rekursionstiefe von Funktionsaufrufen treffen. Denken Sie daran, dass die meisten Openmp-Pragmas selbst Funktionen erzeugen, die wahrscheinlich die Tail-Rekursion-Optimierung stören.

Wenn Sie über Valgrind laufen, sollte es Sie vor dem Überlauf des Stapels warnen.

Answer 2

dlasalle ist korrekt über den tatsächlichen Fehler.

Es gibt jedoch zwei grundlegende Probleme bei der Verwendung von OpenMP-Aufgaben. Sie erzeugen innerhalb jedes rekursiven Aufrufs eine parallele Region. Dies bedeutet, dass Sie verschachtelte parallele Regionen verwenden. Standardmäßig ist verschachtelte Parallelität in OpenMP deaktiviert, und das ist hier nicht sinnvoll. Sie möchten, dass alle Aufgaben, die Sie während der Rekursion erzeugen, von demselben Thread-Pool ausgeführt werden. Um dies zu tun, müssen Sie die parallel/single außerhalb der Rekursion, z.

int reduce_par(int* arr, unsigned long int n) 
{ 
    int x; 
    if (n <= 0) 
     return 0; 
    #pragma omp task shared(x) 
    x = reduce_par(arr, n - 1) + arr[n - 1]; 
    #pragma omp taskwait 
    return x; 
} 

int reduce(int* arr, unsigned long int n) 
{ 
    #pragma omp parallel 
    { 
     #pragma omp single nowait 
     { 
      reduce_par(arr, n); 
     } 
    } 
} 

Auch wenn dies nicht segfault, und selbst wenn man unendlich vielen Kern hatte, mit unendlicher Speicher-Bandbreite und keine Thread-Erzeugung Overhead, diese woudn't noch jede Leistung profitieren von der Parallelisierung bieten. Um dies herauszufinden, zeichnen Sie das Diagramm der Aufgaben und ihrer Operationen und fügen Sie die Abhängigkeiten hinzu. Versuchen Sie, die Knoten des Diagramms in einer Zeitachse anzuordnen, die die Aufgabenabhängigkeiten berücksichtigt, und sehen Sie, ob überhaupt etwas parallel berechnet werden kann. Die richtige Lösung für eine parallele Summierung ist ein parallel for Worksharing-Konstrukt mit einer reduce Klausel. Und wenn Sie Aufgaben verwenden mussten, müssen Sie Divide and Conquer verwenden, z. spawnen zwei Aufgaben für zwei Hälften des Arrays. Um eine angemessene Leistung zu erzielen, müssen Sie die Task-Erstellung/Rekursion bei einer minimalen Workload-Größe stoppen, um den Overhead überschaubar zu halten.