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 1
steht in der letzten Spalte. Aber ich habe
0 0 0
1 0 0
2 0 1
3 0 1
Also meine Fragen sind:
- Was passiert in meinem Code?
- Unter welchen Umständen sollte ich verwenden
collapse
?
- Können Sie ein Beispiel geben, das den Unterschied zwischen der Verwendung von
collapse
und nicht verwenden?
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);
}
}
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);
}
}
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
undm
bevor Sie jeden Thread zusammenbrechen bekommtn/nthreads
Iterationen, während es nach dem Zusammenbruch istn*m
Iterationen. Dies kann zB helfen, wennn
ist nicht sehr groß im Verhältnis zunthreads
abern*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