Verstehen der Zusammenbruchklausel in openmp

Lesezeit: 2 Minuten

Benutzeravatar von iomartin
iomartin

Ich bin auf einen OpenMP-Code gestoßen, der die Kollapsklausel hatte, was mir neu war. Ich versuche zu verstehen, was es bedeutet, aber ich glaube nicht, dass ich seine Implikationen vollständig verstanden habe; Eine Definition, die ich gefunden habe, ist:

ZUSAMMENBRUCH: Gibt an, wie viele Schleifen in einer verschachtelten Schleife zu einem großen Iterationsraum zusammengefasst und gemäß der Zeitplanklausel aufgeteilt werden sollen. Die sequentielle Ausführung der Iterationen in allen zugehörigen Schleifen bestimmt die Reihenfolge der Iterationen im komprimierten Iterationsraum.

Ich dachte, ich hätte verstanden, was das bedeutet, also habe ich das folgende einfache Programm ausprobiert:

int i, j;
#pragma omp parallel for num_threads(2) private(j)
for (i = 0; i < 4; i++)
    for (j = 0; j <= i; j++)
        printf("%d %d %d\n", i, j, omp_get_thread_num());

Was produziert

0 0 0
1 0 0
1 1 0
2 0 0
2 1 0
2 2 1
3 0 1
3 1 1
3 2 1
3 3 1

Die habe ich dann hinzugefügt collapse(2) Klausel. Ich hatte erwartet, in den ersten beiden Spalten das gleiche Ergebnis zu haben, aber jetzt habe ich die gleiche Anzahl von 0‘s und 1steht in der letzten Spalte. Aber ich habe

0 0 0
1 0 0
2 0 1
3 0 1

Also meine Fragen sind:

  1. Was passiert in meinem Code?
  2. Unter welchen Umständen sollte ich verwenden collapse?
  3. Können Sie ein Beispiel geben, das den Unterschied zwischen der Verwendung von collapse und nicht verwenden?

  • Gute Frage. Sie versuchen, eine dreieckige Doppelschleife zu verschmelzen. Ich glaube nicht, dass der Zusammenbruch dafür funktioniert. Es muss eine quadratische Doppelschleife sein. Andere auf SO haben gesagt, dass der Zusammenbruch mit dreieckigen Schleifen funktioniert. Ich habe die Spezifikation nicht gelesen. Wenn Sie eine dreieckige Schleife verschmelzen möchten, lesen Sie diese Frage. Allerdings kenne ich jetzt einen besseren Weg, dies mit Induktionsvariablen zu tun.

    – Z-Boson

    12. Februar 2015 um 16:42 Uhr


  • Aber wenn es sich um eine quadratische Doppelschleife handelt, was ist der Vorteil der Verwendung von Collapse? Jeder Thread erhält in beiden Fällen die gleiche Anzahl von Iterationen.

    – Iomartin

    12. Februar 2015 um 16:47 Uhr


  • Wenn Sie zwei verschachtelte Schleifen haben n und m bevor Sie jeden Thread zusammenbrechen bekommt n/nthreads Iterationen, während es nach dem Zusammenbruch ist n*m Iterationen. Dies kann zB helfen, wenn n ist nicht sehr groß im Verhältnis zu nthreads aber n*m ist.

    – Z-Boson

    12. Februar 2015 um 16:53 Uhr


  • Wenn Sie C99 verwenden, sparen Sie sich die Mühe, Ihre Schleifenindizes zu privatisieren … #pragma omp parallel for for (int i = 0; i < 4; i++) for (int j = 0; j <= i; j++) printf("%d %d %d\n", i, j, omp_get_thread_num());

    – Jeff Hammond

    12. Februar 2015 um 23:07 Uhr

  • Die aktuelle nicht reduzierte Ausgabe ist falsch und zeigt 5 Ausgaben für jeden Thread – sollten nur die äußeren Schleifenwerte 0 und 2 für Thread Nr. 0 sein (dh 0 0 0, 2 0 0, 2 1 0), die anderen Ausgaben sollten mit Thread sein #1.

    – ofer.sheffer

    12. April 2017 um 15:53 ​​Uhr

Benutzeravatar von Z boson
Z-Boson

Das Problem mit Ihrem Code ist, dass die Iterationen der inneren Schleife von der äußeren Schleife abhängen. Gemäß der OpenMP-Spezifikation unter der Beschreibung des Abschnitts über die Bindung und die collapse Klausel:

Wenn die Ausführung einer zugeordneten Schleife einen der Werte ändert, die zum Berechnen einer der Iterationszählungen verwendet werden, ist das Verhalten nicht spezifiziert.

Wenn dies nicht der Fall ist, können Sie z. B. bei einer quadratischen Schleife einklappen

#pragma omp parallel for private(j) collapse(2)
for (i = 0; i < 4; i++)
    for (j = 0; j < 100; j++)

Tatsächlich ist dies ein gutes Beispiel, um zu zeigen, wann Collapse verwendet werden sollte. Die äußere Schleife hat nur vier Iterationen. Wenn Sie mehr als vier Threads haben, werden einige verschwendet. Aber wenn Sie zusammenbrechen, verteilen sich die Threads auf 400 Iterationen, was wahrscheinlich viel größer ist als die Anzahl der Threads. Ein weiterer Grund für die Verwendung des Einklappens ist, wenn die Last nicht gut verteilt ist. Wenn Sie nur vier Iterationen verwendet haben und die vierte Iteration die meiste Zeit in Anspruch genommen hat, warten die anderen Threads. Aber wenn Sie 400 Iterationen verwenden, wird die Last wahrscheinlich besser verteilt.

Sie können eine Schleife von Hand für den obigen Code wie folgt fusionieren

#pragma omp parallel for
for(int n=0; n<4*100; n++) {
    int i = n/100; int j=n%100;

Hier ist ein Beispiel, das zeigt, wie eine dreifach verschmolzene Schleife von Hand verschmolzen wird.

Schließlich ist hier ein Beispiel, das zeigt, wie man eine dreieckige Schleife fusioniert, die collapse ist nicht definiert für.


Hier ist eine Lösung, die eine rechteckige Schleife der dreieckigen Schleife in der OP-Frage zuordnet. Dies kann verwendet werden, um die dreieckige Schleife des OPs zu verschmelzen.

//int n = 4;
for(int k=0; k<n*(n+1)/2; k++) {
    int i = k/(n+1), j = k%(n+1);
    if(j>i) i = n - i -1, j = n - j;
    printf("(%d,%d)\n", i,j);
}

Dies funktioniert für jeden Wert von n.

Die Karte für die OPs Frage geht aus

(0,0),
(1,0), (1,1),
(2,0), (2,1), (2,2),
(3,0), (3,1), (3,2), (3,3),

zu

(0,0), (3,3), (3,2), (3,1), (3,0),
(1,0), (1,1), (2,2), (2,1), (2,0),

Für ungerade Werte von n ist die Karte nicht genau ein Rechteck, aber die Formel funktioniert immer noch.

Zum Beispiel wird n = 3 abgebildet

(0,0),
(1,0), (1,1),
(2,0), (2,1), (2,2),

zu

(0,0), (2,2), (2,1), (2,0),
(1,0), (1,1),

Hier ist Code, um dies zu testen

#include <stdio.h>
int main(void) {
    int n = 4;
    for(int i=0; i<n; i++) {
        for(int j=0; j<=i; j++) {
            printf("(%d,%d)\n", i,j);
        }
    }
    puts("");
    for(int k=0; k<n*(n+1)/2; k++) {
        int i = k/(n+1), j = k%(n+1);
        if(j>i) i = n - i - 1, j = n - j;
        printf("(%d,%d)\n", i,j);
    }
}

  • @Gilles, warum hast du den Kommentar hinzugefügt <!-- language-all: lang-c --> zu meiner antwort? Was ist der Sinn, das zu tun. Ich beschwere mich nicht. Ich weiß nur nicht, wofür es ist.

    – Z-Boson

    3. Dezember 2015 um 21:28 Uhr


  • Ich habe gerade den Hinweis zur Hervorhebung der C-Syntax wie beschrieben hinzugefügt hier. Tatsächlich wurden in meinem Browser alle Ihre Codeschnipsel in einem düsteren Grau angezeigt. Nun, zumindest in meinem Browser, aber ich vermute auch in vielen anderen, ist die C-Syntax farbig. OK, die Indizes in den Ausgabe-Snippets sind es auch, was möglicherweise unerwünscht ist, aber es kann behoben werden, wenn Sie möchten? Wie auch immer, ich wollte nicht stören, aber ich dachte, eine gute Antwort verdient gute Farben… Bin ich zu weit gegangen?

    – Gilles

    4. Dezember 2015 um 5:01 Uhr


  • @Gilles, das war mir nicht bewusst. Vielen Dank! Es macht mir überhaupt nichts aus, dass Sie meine Antwort verbessert haben.

    – Z-Boson

    4. Dezember 2015 um 8:16 Uhr

  • Aber ich habe nicht verstanden, was der Parameter bedeutet? zusammenbruch(2) was ist 2 ?!

    – N0rA

    5. März 2016 um 16:04 Uhr

  • @N0rA Die Anzahl der Schleifen. collapse(n) bricht folgendes zusammen n verschachtelte Schleifen in eine einzelne parallele Schleife, die von den Threads geteilt wird.

    – Chris Swierczewski

    24. Juli 2017 um 20:35 Uhr

Benutzeravatar von h2kyeong
h2kyeong

Wenn Ihr Zweck darin besteht, die Last über zunehmende Zeilen auszugleichen, vorausgesetzt, dass die Arbeitslast für jedes Element regelmäßig oder gut verteilt ist, wie wäre es dann, wenn Sie die Zeilenindizes halbieren und vergessen collapse Klausel?

#pragma omp for
for (int iy0=0; iy0<n; ++iy0){
  int iy = iy0;
  if (iy0 >= n/2) iy = n-1 -iy0 +n/2;
  for (int ix=iy+1; ix<n; ++ix){
    work(ix, iy);
  }
}

1400340cookie-checkVerstehen der Zusammenbruchklausel in openmp

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy