Hallo Zusammen,

da ich mich zurzeit mit der Parallelverarbeitung beschäftigt, genauer gesagt OpenMP ist mir dabei was aufgefallen.

Ich habe folgenden Code:

Code:

int Gauss(double **a, int n)
{
	int i,j;
    int ij;
	double h;
	double diff;    /* Maximale Änderung seit der letzten Iteration */
	int k = 0;      /* Zählt Iterationen mit (nur für Statistik ...) */


	/*
	** Iteriere solange, bis Konvergenz erreicht ist, hier: bis die maximale
	** Änderung eines Matrixelements kleiner oder gleich 'eps' ist.
	*/
	do {
		diff = 0;
        for (ij=1; ij<2*n-4; ij++) {
            int ja = (ij <= n-2) ? 1 : ij-(n-3);
            int je = (ij <= n-2) ? ij : n-2;
            #pragma omp parallel for private(i,h) 
            for (j=ja; j<=je; j++) {
                i = ij - j +1;
                h = a[i][j];
                a[i][j] = 0.25 * (a[i][j-1] + a[i-1][j] + a[i+1][j] + a[i][j+1]);
            
		        h = fabs(a[i][j] - h);
                if (h > diff)
			        diff = h;
            }
        }        
		k++;
	} while (diff > eps);
	return k;
}

Der das Gauss-Seidel Verfahren auf eine Matrix (a) anwendet. Die Schleifenumstrukturierung ist dabei vorgegeben um in der inneren Schleife keine Abhängigkeiten zu haben, dadurch kann die innere Schleife dann komplett parallelisiert werden.

Soweit so gut. Jetzt habe ich diese funktionierenden Code mal verschiedenen Compilern vorgeworfen und bin vom Ergebnis doch recht beeindruckt. Zum Vergleich habe ich eine serielle Variante die die Matrix einfach stur lang läuft.

Das Ergebnis mit einer 3000 Matrix und GCC 4.2/4.2, omni Compiler , Intel, Sun -O optimiert:
- GCC GSV seriell: 43 Sekunden
- GCC GSV parallel auf 4 Cores: 76 Sekunden
- Omni: 26 Sekunden
- Intel: 76 Sekunden
- Sun: 83 Sekunden

Irgendwie fehlt mir gerade dafür das Verständnis das alle großen bekannten Compiler sich so abhängen lassen. Ich sehe auch gerade keinen Fehler im Code der eine Optimierung verhindert.

Bei einem anderen Problem konnte ich feststellen das der GCC durch z.b. Variablen umbenennen, bzw. Zugriffsänderungen zur Beschleunigung geführt werden konnte.

Kann das hier irgendwer bestätigen, vielleicht auch selber seinen Erfahrungen schildern?
Welche Auswirkungen auf eure Tool Chain hat das? Manche Probleme versuchen zu parallelisieren wird doch dann auch hinfällig, wenn ich davon ausgehen muss mein Compiler baut daraus vielleicht eine weniger performante Variante?

Meiner Meinung nach ist dadurch, dass du an a[i][j] zuweist, das Ergebnis deines Programms davon abhängig, in welcher Reihenfolge die Durchläufe der inneren Schleife passieren, denn damit änderst du die Eingabewerte für andere Durchläufe.

Wenn ich es jetzt richtig im Kopf habe werden bei "private" Deine Variabeln i und h nicht initialisiert. Ich habe bei diesen Initialisierungen die besten Erfahrungen damit gemacht, dass ich entweder "firstprivate" verwendet oder eben die Variablen direkt innerhalb des Threadblocks erzeuge also

Code:

#pragma
{
int ...
}

Ansonsten stimme ich Klotzkopp zu: Beim GS-Verfahren verfahren ist die Reihenfolge der Spalten/Zeilenelemente entscheidend. Bei Deiner Threadparallelisierung ist es somit entscheidend wie OpenMP die Schleife zerlegt. OpenMP hat aber die Möglichkeit die Sequenzierung anzugeben. Ich würde daher vom GS-Verfahren abraten und zu einer parallelen Cholesky-Zerlegung raten

edit: Beispielcode habe ich irgendwo, falls Bedarf besteht.

Da kann ich dich beruhigen, deswegen ist ja das Schleifenkonstrukt etwas... unübersichtlich. Ich berechne einen diagonalen Weg durch die Matrix so das keine Abhängigkeit da ist.

Code:

| a b c |
| d e f |
| g h i |

Dann ist meine Durchlaufreihenfolge:
1) a
2) bd
3) ceg
4) fh
5) i

Wenn ich es jetzt richtig im Kopf habe werden bei "private" Deine Variabeln i und h nicht initialisiert. Ich habe bei diesen Initialisierungen die besten Erfahrungen damit gemacht, dass ich entweder "firstprivate" verwendet oder eben die Variablen direkt innerhalb des Threadblocks erzeuge also ...

Richtig, brauche ich aber ja auch nicht. In der inneren Schleife erfolgt kein Zugriff auf die Variablen bevor sie nicht initialisiert werden mit:

Code:

i = ij - j +1;
h = a[i][j];

Habe das aber dennoch geändert und der GCC erzeugt gleich schnellen/langsamen Code.

Ansonsten stimme ich Klotzkopp zu: Beim GS-Verfahren verfahren ist die Reihenfolge der Spalten/Zeilenelemente entscheidend. Bei Deiner Threadparallelisierung ist es somit entscheidend wie OpenMP die Schleife zerlegt. OpenMP hat aber die Möglichkeit die Sequenzierung anzugeben. Ich würde daher vom GS-Verfahren abraten und zu einer parallelen Cholesky-Zerlegung raten

Danke für das Angebot, leider bin ich ans GSV als Teil der Übungsaufgabe gebunden. Dabei soll der Aha Effekt auftreten, dass zum Parallelisieren eine Veränderung der Schleife nötig ist, was dann dafür sorgt das mit nur einem Thread das Programm einen Speedup von 0.8 oder schlechter erfährt. Aber ich habe eher ein WTF Erlebnis, das alle Compiler sich verhältnismäßig zu dem anderen opensource Compiler so schlecht anstellen...

Zitat von Wodar Hospur

Dann ist meine Durchlaufreihenfolge:
1) a
2) bd
3) ceg
4) fh
5) i

Da du die Werte in der Matrix änderst, und jeder Wert Berechnungsgrundlage für die benachbarten Werte ist, hast du eine Abhängigkeit.

Mal ganz konkret: Im ersten Schleifendurchlauf änderst du a[1][1]. Im zweiten änderst du a[2][1], wobei a[1][1] Eingabewert ist. Im nächsten änderst du a[1][2], wieder ist a[1][1] Eingabewert für die Berechnung.

Deine Berechnungen bauen aufeinander auf.

Nein innerhalb der inneren Schleife bestehen keine Abhängigkeiten. Die äußere Schleife gibt die Elemente für die innere Schleife vor.
So läuft im ersten Schritt die inneren Schleife nur über a[1][1]
Im zweiten Schritt läuft sie dann über a[2][1] und a[1][2].
Zwischen a[2][1] und a[1][2] besteht keinerlei Abhängigkeit, deswegen kann ich die innere Schleife parallelisieren.

Ok, jetzt habe ich es verstanden.

Ich könnte mir allerdings vorstellen, dass die Compiler Schwierigkeiten haben, das zu erkennen.

Moin!

Dein Problem hat mich an diesen Artikel erinnert:
Eliminate False Sharing

Ich habe den Artikel nicht 100%ig im Kopf, aber uebertragen auf Dein Problem scheint das Problem am gemeinsamen Zugriff auf a[] zu liegen. Grund ist, dass die Caches nach jedem Zugriff ungueltig werden und die Daten erst wieder aus dem Speicher geholt werden muessen.
Die Loesung waere also die Werte in einem eigenen Array zwischenzuspeichern und dann in einem Stueck nach a[] zu schreiben.

@Wodar Hospur
Hat sich bei Dir denn noch das oben erwaehnte "Aha-Erlebnis" eingestellt, bzw. hast Du den Grund fuer die Verlangsamung herausgefunden?