1
Vorlesung, Wintersemester 2009/10 M. Schölzel
Optimierungstechniken in modernen Compilern
Optimierungstechniken für SMP-Architekturen
2Optimierungstechniken in modernen Compilern Grundlagen
SMP-Architektur
Bus
Cache Cache
gemeinsamer Speicher
Core 1 Core n…
Anwendung
Thread 1 Thread nKommunikation über gemeinsamen Speicher
3Optimierungstechniken in modernen Compilern Grundlagen
Thread-Erzeugung und Synchronisation mit dem Windows API
#include <windows.h>#include <stdio.h>
struct iterationSpace { int from; int to;};
DWORD WINAPI ThreadFunc(LPVOID param) { iterationSpace* is = (iterationSpace*)param;
for(int i = is->from; i <= is->to; i++) printf("Thread %d, Iteration %d ", GetCurrentThreadId(),i); return 0;}
int main(int argc, char* argv[]) { DWORD threadId1; DWORD threadId2; HANDLE threads[2]; iterationSpace is1 = {0,49}; iterationSpace is2 = {50,99};
threads[0] = CreateThread(0,0,ThreadFunc,&is1,0,&threadId1); threads[1] = CreateThread(0,0,ThreadFunc,&is2,0,&threadId2);
DWORD w = WaitForMultipleObjects(2,threads,TRUE,2000); if(w == WAIT_TIMEOUT) printf("Timeout.\n"); else printf("Kein Timeout.\n"); CloseHandle(threads[0]); CloseHandle(threads[1]);
return 0;}
Deklarationen und Thread-Funktion: Threads erzeugen:
4
Vorlesung, Wintersemester 2009/10 M. Schölzel
Optimierungstechniken für superskalare Prozessoren
Erzeugen grobranularer Parallelität
5Optimierungstechniken in modernen Compilern Grundlagen
Parallelisierung von Schleifennestern zur Ausführung auf mehreren Prozessorkernen
Parallelisierung sollte genügend Potenzial bieten, um die Parallelität gleichmäßig zu verteilen, geringen Aufwand zur Synchronisierung erfordern.
Im Allgemeinen bietet jede Schleife genügend Iterationen, um diese auf mehrere Prozessorkerne zu verteilen, sofern dies die Abhängigkeiten zulassen.
Um Synchronisationsaufwand gering zu halten, sollten deshalb die Iterationen der äußersten Schleifen parallelisiert werden.
Das bedeutet, dass durch Loop-Interchange diejenigen Schleifen eines Nests nach außen geschoben werden sollten, die keine Abhängigkeiten tragen.
Beispiel:
for i = 1 to N do for j = 1 to M do a[i+1][j] = a[i][j] + b[i][j] odod (<,=)
i = 1
j=1 j=1 j=Mj=M-1
P1 P2
i = 2
j=1 j=1 j=Mj=M-1
P1 P2
…
M Synchronisationspunkte
……
for j = 1 to M do for i = 1 to N do a[i+1][j] = a[i][j] + b[i][j] odod (=,<)
j = 1
i=1 i=1 i=N
P1 P2
1 Synchronisationspunkt
…
j = 2
i=1 i=1 i=M… …j = M
i=1 i=1 i=N…
6Optimierungstechniken in modernen Compilern Grundlagen
Parallelisierung von Schleifennestern
Die Richtungsmatrix zu einem Schleifennest enthält alle Richtungsvektoren des Schleifennests, wobei jede Zeile der Matrix genau einem Richtungsvektor entspricht.
Es gilt:In einem perfekten Schleifennest kann die Schleife in Level i genau dann als äußerste Schleife parallelisiert werden, wenn die Spalte i in der Richtungsmatrix nur Gleichheitszeichen (=) enthält.
Daraus ergibt sich folgende Strategie zum Parallelisieren von Schleifennestern:
Solange es in der Richtungsmatrix eine Spalte i mit nur = gibt, mache Schleife i zur äußersten Schleife des Nests und verteile die Iterationen auf die vorhandenen Prozessoren und Entferne die Spalte i aus der Richtungsmatrix.
Sonst wähle eine Schleife i die möglichst viele Abhängigkeiten trägt (Anzahl der < in der entsprechenden Spalte ist maximal) und die zur äußersten Schleife des Nests gemacht werden kann (Spalte darf keinen Eintrag > enthalten). Führe die Iterationen dieser Schleife sequentiell aus. Entferne Spalte i aus der Richtungsmatrix und alle Zeilen, in denen die Spalte i ein < enthalten hat (Diese Abhängigkeit wird wegen der sequentiellen Ausführung von i eingehalten). Durch entfernen dieser Zeilen entstehen möglicherweise neue Spalten in der Richtungsmatrix, die nur noch = enthalten.
Wiederhole die zwei vorhergehenden Schritte.
7Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
for i = 1 to N do for j = 1 to M do for k = 1 to L do a[i+1][j][k] = a[i][j][k] + x1 b[i][j][k+1] = b[i][j][k] + x2 c[i+1][j+1][k+1] = c[i][j][k] + x3 od odod
Richtungsmatrix
Entstehende Richtungsmatrix
Schleifennest
Richtungsvektor für a
Richtungsvektor für b
Richtungsvektor für c
i j k
i-Schleife auswählen, sequentiell ausführen und Spalte 1, Zeile 1 und 3 entfernen.
for i = 1 to N do for j = 1 to M do for k = 1 to L do a[i+1][j][k] = a[i][j][k] + x1 b[i][j][k+1] = b[i][j][k] + x2 c[i+1][j+1][k+1] = c[i][j][k] + x3 od odod
Richtungsvektor für b bei i konstant
j k
8Optimierungstechniken in modernen Compilern Grundlagen
Beispiel (fortgesetzt)
for i = 1 to N do parallel for j = 1 to M do for k = 1 to L do a[i+1][j][k] = a[i][j][k] + x1 b[i][j][k+1] = b[i][j][k] + x2 c[i+1][j+1][k+1] = c[i][j][k] + x3 od odod
Schleifennest
Richtungsmatrix
for i = 1 to N do for j = 1 to M do for k = 1 to L do a[i+1][j][k] = a[i][j][k] + x1 b[i][j][k+1] = b[i][j][k] + x2 c[i+1][j+1][k+1] = c[i][j][k] + x3 od odod
Richtungsvektor für b bei i konstant
j k
j-Schleife auswählen, parallel ausführen und Spalte 1 entfernen.
Entstehende Richtungsmatrix
Richtungsvektor für b bei i,j konstant
k
k-Schleife auswählen, sequentiell ausführen und Spalte 1 entfernen.
9Optimierungstechniken in modernen Compilern Grundlagen
Loop-Reversal
Loop-Reversal kehrt die Reihenfolge, in der die Iterationen einer Schleife ausgeführt werden, um.
Dadurch ändert sich die Richtung der durch diese Schleife verursachten Abhängigkeiten von < auf > und umgekehrt.
Wegen einer umgebenden Schleife wird die Quelle der Abhängigkeit aber trotzdem noch vor der Senke ausgeführt.
for i = 1 to N do a[i+1] = a[i] + 1od
It 1 It 2 It 3 It 4 It 5 It N…
Speicherelement
Abarbeitungsrichtung der Iterationen
Quelle Senke<
It 1 It 2 It 3 It 4 It 5 It N…
Speicherelement
Abarbeitungsrichtung der Iterationen
Senke Quelle<
for i = N downto 1 do a[i+1] = a[i] + 1od
for j = 1 to M do for i = 1 to N do a[j+1][i+1] = a[j][i] + 1 odod
for j = 1 to M do for i = N downto 1 do a[j+1][i+1] = a[j][i] + 1 odod
10Optimierungstechniken in modernen Compilern Grundlagen
Loop-Reversal
for i = 2 to N+1 do for j = 2 to M+1 do for k = 1 to L do a[i][j][k] = a[i][j-1][k+1] + a[i-1][j][k+1] od odod
Alle Abhängigkeiten der inneren Schleife haben Richtung >, kann deshalb nicht nach außen verschoben werden.
for i = 2 to N+1 do for j = 2 to M+1 do for k = L downto 1 do a[i][j][k] = a[i][j-1][k+1] + a[i-1][j][k+1] od odod
Innere Schleife kann jetzt nach außen verschoben werden, dann werden alle Abhängigkeiten von äußerer Schleife getragen. Damit können alle inneren Schleifen parallel
ausgeführt werden.
for k = L downto 1 do parallel for i = 2 to N+1 do parallel for j = 2 to M+1 do a[i][j][k] = a[i][j-1][k+1] + a[i-1][j][k+1] od odod
Schleifennest Richtungsmatrix
Schleifennest nach Loop-Reversal Richtungsmatrix nach Loop-Reversal
Parallelisiertes Schleifennest
11Optimierungstechniken in modernen Compilern Grundlagen
Loop-Distribution
Anwendbar auf eine einzelne Schleife oder die innerste Schleife eines perfekten Schleifennestes. Kann verwendet werden, um eine Schleife mit schleifengetragenen Abhängigkeiten zwischen
verschiedenen Anweisungen in mehrere Schleifen ohne schleifengetragene Abhängigkeiten zu transformieren.
Dadurch ist eine Parallelisierung der einzelnen Schleifen möglich. Erzeugt Synchronisierungsbarrieren zwischen den verschiedenen Schleifen. Grund: Alle Quellen einer Abhängigkeit werden in einer Schleife ausgeführt, die vor der Schleife
abgearbeitet wird, die die Senken enthält. Beispiel:
for i = 2 to N do(s) a[i] = b[i]+ c[i](t) d[i] = a[i-1] * 2 od
s2t2
s3t3
s4t4
s5t5
sNtN
It 1 It 2 It 3 It 4 It N
for i = 2 to N do(s) a[i] = b[i]+ c[i] od for i = 2 to N do(t) d[i] = a[i-1] * 2 od
s2
t2
s3
t3
s4
t4
s5
t5
sN
tN
It 1 It 2 It 3 It 4 It N
It 1 It 2 It 3 It 4 It N
1. Schleife
2. SchleifeKeine Parallelisierung der
Iterationen möglich.
Synchronisations-barriere
Thread 1 Thread 2
Thread 1' Thread 2'
12Optimierungstechniken in modernen Compilern Grundlagen
Alignment
Anwendbar auf eine einzelne Schleife. Ziel: Schleifengetragene Abhängigkeiten werden in schleifenunabhängige
Abhängigkeiten transformiert, indem Quelle und Senke einer schleifengetragenen Abhängigkeit in dieselbe Iteration verschoben werden.
Konsequenz: Falls dadurch alle schleifengetragenen Abhängigkeiten transformiert werden können, können die Iterationen parallelisiert werden.
Beispiel:
for i = 2 to N do(s) a[i] = b[i]+ c[i](t) d[i] = a[i-1] * 2 od
s2t2
s3t3
s4t4
s5t5
sNtN
It 1 It 2 It 3 It 4 It Ns2
t2
s3t3
s4t4
s5t5
sNtN
It 1 It 2 It 3 It 4
t6
sN-1
d[2] = a[1] * 2 for i = 2 to N-1 do(s) a[i] = b[i]+ c[i](t) d[i+1] = a[i] * 2 od a[N] = b[N] + c[N]
It N-1
13Optimierungstechniken in modernen Compilern Grundlagen
Grenzen des Alignments
Zykel im Abhängigkeitsgraphen durch rückwärtsgerichtete schleifengetragene Abhängigkeiten:
Konflikte beim Alignment durch zwei Abhängigkeiten mit derselben Quelle und Senken in verschiedenen Iterationen:
sk
tm
sn
rückwärtsgerichteteschleifengetragene
Abhängigkeit
vorwärtsgerichteteschleifengetragene und schleifenunabhängige
Abhängigkeiten
s2t2
s3t3
s4t4
s5t5
sNtN
It 1 It 2 It 3 It 4 It Ns2
t2
s3t3
s4t4
s5t5
sNtN
It 1 It 2 It 3 It 4 It N It N+1
t6
sN-1
14Optimierungstechniken in modernen Compilern Grundlagen
Loop Fusion
Durch Loop-Distribution entstehende Schleifen enthalten jeweils nur eine Anweisung; nicht sinnvoll für grobgranulare Parallelität.
Durch Loop-Fusion können parallelisierbare Schleifen die aufeinander folgen zu einer parallelisierbaren Schleife zusammengefasst werden.
Die entstehende Schleife enthält mehr Anweisungen je Iteration. Nur sinnvoll, wenn durch Loop-Fusion in der erzeugten Schleife keine
schleifengetragenen Abhängigkeiten entstehen. Beispiel:
for i = 1 to N do(s) a[i] = b[i] + 1(t) c[i] = a[i] * c[i-1](u) d[i] = a[i] + 3 od
for i = 1 to N do(s) a[i] = b[i] + 1 od for i = 1 to N do(t) c[i] = a[i] * c[i-1] od for i = 1 to N do(u) d[i] = a[i] + 3 od
s
tu
{0}D{0}D
{1}D
Ls
Lt
Lu
{0}D
{0}D
{1}D
parallelisierbare Schleifen
for i = 1 to N do(s) a[i] = b[i] + 1(u) d[i] = a[i] + 3 od for i = 1 to N do(t) c[i] = a[i] * c[i-1] od
Zusammenfassen paralleliserbarer Schleifen,
zwischen deren Anweisungen nur Abhängigkeiten existieren, die im
ursprünglichen Abhängigkeitsgraphen
schleifenunabhängig waren.
15Optimierungstechniken in modernen Compilern Grundlagen
Zerlegen des Iterationsbereichs (Index-Set Splitting)
Zerlegung des Iterationsbereichs erzeugt aus einer Schleife eine Folge von Schleifen durch:
Loop-Peeling, Strip-Mining.
Ziel ist die Transformation von schleifengetragenen Abhängigkeiten in Abhängigkeiten, zwischen den Anweisungen verschiedener Schleifen (analog zur Loop-Distribution; Loop-Distribution kann aber nicht angewendet werden, wenn zyklische Abhängigkeiten im Abhängigkeitsgraphen existieren).
s2 s3 s4 sN
It 1 It 2 It 3 It 4 It Ns1 …s5
It 5s6
It 6
Iterationen einer Schleife mit Abhängigkeiten
s2 s3
It 1 It 2 It 3s1
s4
sN
It N-4…s5
It 1
s6
It 2
Iterationen der ersten Schleife
Iterationen der zweiten Schleife
Iterationen der dritten Schleife
Zerlegung des Iterationsbereichs:
16Optimierungstechniken in modernen Compilern Grundlagen
Loop-Peeling
Eine Menge schleifengetragener Abhängigkeit hat ihre gemeinsame Quelle oder Senke in einer Iteration der Schleife (Test z.B. über weak-zero-SIV Test).
Separates Ausführen dieser Iteration. Beispiel: Auf a[1] wird nur in der ersten Iteration schreibend zugegriffen (Quelle).
Alle anderen Iterationen greifen lesend auf a[1] zu (Senken).
for i = 1 to N do a[i] = a[i] + a[1]od
a[1] = a[1] + a[1]for i = 2 to N do a[i] = a[i] + a[1]od
s2 s3 s4 sN
It 1 It 2 It 3 It 4 It Ns1 …
s2 s3 s4 sN
It 2 It 3 It N-1
s1
…It 1
schleifengetragene Abhängigkeiten
schleifenunabhängige Abhängigkeiten
17Optimierungstechniken in modernen Compilern Grundlagen
Strip Mining
Der Schwellwert einer Abhängigkeit ist der am weitesten links stehenden Wert in den Distanzvektoren dieser Abhängigkeit.
Zerlegen einer Schleife s mit schleifengetragenen Abhängigkeiten in mehrere Schleifen s1,…sn, so dass diese Schleifen keine schleifengetragenen Abhängigkeiten besitzen.
Eine schleifengetragene Abhängigkeit kann eliminiert werden, falls die Abhängigkeit einen Schwellwert t besitzt und keine Schleife s1,…sn, mehr als t Iterationen ausführt.
Beispiel:
for i = 1 to 100 do a[i+4] = a[i] + kod
for i = 1 to 100 step 4 do for j = i to i+3 do a[j+4] = a[j] + k odod
s2 s3 s4 s100
It 1 It 2 It 3 It 4 It Ns1 …s5
It 5s6
It 6
Iterationen einer Schleife mit Abhängigkeiten
s2 s3
It 1 It 2 It 3
s1 Iterationen der ersten Schleife
Iterationen der zweiten Schleife
Iterationen der 25. Schleife
Zerlegung des Iterationsbereichs:
s4
It 4
s6 s7s5 s8…
s98 s99s97 s100
18Optimierungstechniken in modernen Compilern Grundlagen
Privatisierung
Privatisierung eliminiert schleifengetragene Abhängigkeiten, die auf Grund des Zugriffs auf eine skalare Variable entstehen, falls die Variable keinen Wert aus einer Iteration in eine andere Iteration weiterreicht.
Eine skalare Variable, die am Beginn einer Schleife nicht lebendig ist, kann privatisiert werden.
Privatisierung ist Expansion skalarer Variablen vorzuziehen, weil es weniger Speicherplatz erfordert.
for i = 1 to N do t = a[i] a[i] = b[i] b[i] = tod
for i = 1 to N do private t t = a[i] a[i] = b[i] b[i] = tod
for i = 1 to N do t = a[i] + b[i] a[i-1] = tod
Privatisierung sinnvoll:
Privatisierung nicht sinnvoll wegen schleifengetragener Abhängigkeit durch a for i = 1 to N do
t[i] = a[i] + b[i]odfor i = 1 to N do a[i-1] = t[i]od
19
Vorlesung, Wintersemester 2009/10 M. Schölzel
Optimierungstechniken für superskalare Prozessoren
OpenMP
20Optimierungstechniken in modernen Compilern Grundlagen
OpenMP
Standard für C/C++ und Fortran zur Beschreibung nebenläufig arbeitender Programme die einen gemeinsamen Speicher benutzen.
Erweiterungen umfassen: Compilerdirektiven, Bibliotheksfunktionen, Umgebungsvariablen.
Durch die Annotation herkömmlicher sequentieller Programme mit Compilerdirektiven können diese Programme bei der Übersetzung mit einem OpenMP-fähigen Compiler parallelisiert werden.
Die Programme bleiben auch übersetzbar für Compiler, die kein OpenMP unterstützen.
21Optimierungstechniken in modernen Compilern Grundlagen
Einführung
Ausführungsmodell: Fork/Join Zu Beginn ein Thread aktiv (Initial Thread). Trifft ein Thread auf eine #pragma omp parallel-Direktive erzeugt
dieser Thread (Master-Thread) weitere Threads. Zusammen bilden sie das Thread-Team.
Jeder Thread im Team führt die Anweisung aus, die der Direktive folgt (Dies kann auch ein Block sein).
Der Master-Thread wartet darauf, dass alle Teammitglieder die Ausführung des parallelen Abschnitts beendet haben (Barriere als Synchronisationspunkt). Erst danach setzt er alleine die Programmausführung fort.
Jeder Thread besitzt einen separaten Steuerfluss und einen eigenen Stack.
Alle Threads haben Zugriff auf dieselben Variablen des ursprünglichen sequentiellen Programms.
Langsamster Thread in einem Team bestimmt die Ausführungszeit. Geschachtelte parallele Abschnitte sind zulässig, werden aber
nicht von jeder OpenMP-Implementierung unterstützt.
22Optimierungstechniken in modernen Compilern Grundlagen
Hello World
#include <stdio.h>#ifdef _OPENMP #include <omp.h>#endif
int main(int argc , char* argv []){ #ifdef _OPENMP printf("Anzahl Prozessoren: %d\n", omp_get_num_procs ()); #pragma omp parallel { printf("Thread %d von %d sagt \" Hallo Welt !\"\n", omp_get_thread_num (),omp_get_num_threads ()); } #else printf("OpenMP wird nicht unterstützt .\n"); #endif
printf("Fertig .\n"); return 0;}
Anzahl Prozessoren: 2Thread 0 von 2 sagt " Hallo Welt !"Thread 1 von 2 sagt " Hallo Welt !"Fertig .
Programm:
Ausgabe:
23Optimierungstechniken in modernen Compilern Grundlagen
OpenMP-Direktive
Syntax der OpenMP-Direktiven: #pragma omp directive-name [Klausel[[,] Klausel]...]
Eine Direktive bezieht sich auf die folgende Anweisung (diese kann ein Block sein)
Ein paralleler Abschnitt wird eingeleitet durch: directiv-name ::= parallel
Innerhalb eines parallelen Abschnitts kann die Arbeit mit arbeitsaufteilenden Direktiven verteilt werden, wobei directiv-name sein kann:
for: Parallelisierung von for-Schleifen• Iterationen der for-Schleife werden auf Threads eines Teams
verteilt. sections: Parallelisierung statischer Abschnitte:
• Eine Menge voneinander unabhängiger Codeblöcke werden auf die Threads eines Teams aufgeteilt.
single: Ausdrücklich nicht parallele Abarbeitung• Erzwingt Abarbeitung von Code-Abschnitten innerhalb eines
parallelen Abschnitts durch genau einen Thread im Team.
24Optimierungstechniken in modernen Compilern Grundlagen
nowait-Klausel
Am Ende des Gültigkeitsbereichs aller Arbeit aufteilenden Direktiven befindet sich eine implizite Barriere.
Das bedeutet, dass alle Threads aus dem Team warten, bis alle Teammitglieder den Bereich der Arbeit aufteilenden Direktive verlassen haben.
Durch Angabe der nowait-Klausel können Teammitglieder, die ihre Berechnungen bereits abgeschlossen haben, bereits weitere Berechnungen im restlichen Teil des parallelen Abschnitts ausführen.
Syntax: Klausel ::= nowait
25Optimierungstechniken in modernen Compilern Grundlagen
#pragma omp sections
Initialer Thread
int main(int argc, char* argv[]) { ...
#pragma omp parallel { s; ...
#pragma omp sections { #pragma omp section u1; #pragma omp section u2; ... } t;
}
}
Beginn eines parallelen Abschnitts
Arbeit aufteilende Anweisung
Jeder Thread führt s aus.
Sektionen u1, u2, … werden
auf das Thread-Team aufgeteilt
Jeder Thread führt t aus.
26Optimierungstechniken in modernen Compilern Grundlagen
Syntax für Sektionen
#pragma omp sections{ [# pragma omp section] { // ... } [#pragma omp section { // ... } ] …}
27Optimierungstechniken in modernen Compilern Grundlagen
#pragma omp single
Initialer Thread
int main(int argc, char* argv[]) { ...
#pragma omp parallel { s; ...
#pragma omp single u;
t;
}
}
Beginn eines parallelen Abschnitts
Arbeit aufteilende Anweisung
Jeder Thread führt s aus.
Nur der Master-Thread führt u
aus.
Jeder Thread führt t aus.
28Optimierungstechniken in modernen Compilern Grundlagen
Nicht-parallele Ausführung
Ziel: Innerhalb eines parallelen Abschnitts soll ein Code-Block nur von einem Thread ausgeführt werden; z.B. für:
Initialisierung von Datenstrukturen I/O-operationen
Lösung: Angabe der Direktive single innerhalb eines parallelen Codeabschnitts für diesen Code-Block.
Syntax: #pragma omp single [copyprivate (Liste)]
Liste in der copyprivate-Klausel ist eine Liste privater Variablen im parallelen Abschnitt:
Nach Ausführung des Code-Blocks wird der Wert der privaten Variablen des Thread, der den Code-Block ausgeführt hat, in die gleichnamigen Variablen aller anderen Threads im Team kopiert.
29Optimierungstechniken in modernen Compilern Grundlagen
#pragma omp for
Initialer Thread
int main(int argc, char* argv[]) { ...
#pragma omp parallel { s; ...
#pragma omp for for(...) {
} t;
}
}
Beginn eines parallelen Abschnitts
Arbeit aufteilende Anweisung
Jeder Thread führt s aus.
Iterationen der for-Schleife
werden auf die Team-Mitglieder
aufgeteilt
Jeder Thread führt t aus.
30Optimierungstechniken in modernen Compilern Grundlagen
Voraussetzung zur Parallelisierung
Damit eine for-Schleife parallelisiert werden kann, muss sie in folgender kanonischer Form vorliegen:for(index = startwert; index op endwert; inkrement) Anweisung;
Dabei: Anzahl der Schleifendurchläufe muss vor dem Eintritt in die Schleife
berechenbar sein aus startwert, endwert und inkrement. D.h.:• index darf in der Schleife nicht verändert werden,• keine break-Anweisung in der Schleife,• continue und exit ist erlaubt.
Nur <, <=, >, >= als relationale Operatoren op für Abbruchbedingung zulässig.
inkrement muss den Wert von index in jedem Schleifendurchlauf ändern und darf nur die Operatoren ++, --, +=, -= und = verwenden.
Am Ende einer parallelisierten Schleife gibt es eine implizite Sychronisierungsbarriere.
Dies kann durch #pragma omp parallel for nowait verhindert werden.
31Optimierungstechniken in modernen Compilern Grundlagen
Parallelisierung von Schleifen
Parallelisierung basiert auf folgendem Prinzip: Jeder Thread führt dieselbe Schleife aus aber jeweils für eine andere Teilmenge von Iterationen.
Beispiel:
void saxpyS(float a, int size, float* x, float* y){ for(int i = 0; i < size; i++) { y[i] = y[i] + a * x[i]; }}
void saxpyPFalsch(float a, int size, float* x, float* y){#pragma omp parallel { for(int i = 0; i < size; i++) { y[i] = y[i] + a * x[i]; } }}
32Optimierungstechniken in modernen Compilern Grundlagen
Parallelisierung von Schleifen
Richtige Implementierung:void saxpyPRichtig(float a, int size, float* x, float* y){#pragma omp parallel { #pragma omp for for(int i = 0; i < size; i++) { y[i] = y[i] + a * x[i]; } }}
33Optimierungstechniken in modernen Compilern Grundlagen
Zugriff auf Variablen
Mit Datenzugriffsklauseln kann der Zugriff durch Threads auf Variablen im C++ Programm kontrolliert werden.
Zugriffsklauseln gelten nur für den lexikalischen Bereich des Code-Blocks zu dem die Direktive gehört.
Klausel in einer Direktive darf folgende Syntax haben: Klausel ::= klausel-name ([Variable [, Variable] ...]),
wobei klausel-name sein kann:• shared oder private:
– Variable wird ausdrücklich von allen Threads gemeinsam oder von jedem Thread privat genutzt.
• firstprivate und lastprivate:– Der Inhalt privater Variablen ist beim Eintritt und beim Verlassen ihres
Gültigkeitsbereichs undefiniert. Die Klauseln firstprivate und lastprivate erlauben eine Initialisierung bzw. Finalisierung ihrer Werte.
• reduction:– Die reduction-Klausel kennzeichnet gemeinsam genutzte Variablen, in denen
mehrere Threads Werte akkumulieren können.• default:
– Wie im SAXPY-Beispiel gesehen, werden Variablen, die nicht ausdrücklich mit einer shared- bzw. private-Klausel aufgeführt werden, gemeinsam von allen Threads genutzt. Mit der Klausel default kann dieses Standardverhalten verändert werden.
34Optimierungstechniken in modernen Compilern Grundlagen
Anmerkungen zu Gültigkeitsbereich
lexikalischer Gültigkeitsbereich: Gültigkeitsbereich einer Variablen, wie er durch C++ definiert ist.
Gültigkeitsbereich einer Datenzugriffsklausel in OpenMP: Lexikalischer Umfang einer Direktive: Der Codeblock der zu der
Direktive gehört. Dynamischen Umfangs einer Direktive: Der gesamte Programmcode,
der nach dem Eintritt in den Codeblock der Direktive ausgeführt werden kann (z.B. durch Funktionsaufrufe).
Datenzugriffsklauseln einer Direktive gelten nur für die Variablen, auf die innerhalb ihres lexikalischen Umfangs zugegriffen wird.
Für Zugriffe auf Variablen im dynamischen, nicht aber im lexikalischen Umfang der Direktive, gelten die Datenzugriffsklauseln der Direktive nicht.
Verwaiste Direktiven: Arbeit aufteilende Direktive befindet sich nicht in einem parallelen
Abschnitt aber in einer Funktion. Wird diese Funktion aus einem parallelen Abschnitt heraus aufgerufen,
dann wirkt sie aber.
35Optimierungstechniken in modernen Compilern Grundlagen
Anmerkungen zu privaten Variablen
Jeder Thread im Team legt eine eigenen Instanz einer als privat deklarierten Variablen an.
Konsequenzen: Variable ist uninitialisiert zu Beginn eines parallelen Abschnitts, Variable darf nicht als const deklariert sein, Klassen und Strukturen müssen öffentliche Standardkonstruktoren und
Destruktoren bereitstellen, Schleifenvariablen sind implizit privat. Ein Thread darf nicht über Zeigervariablen auf den privaten
Speicherbereich anderer Threads im Team zugreifen (D.h. Speicheradressen lokaler Variablen sollten nicht weitergegeben werden).
Lokale Variablen einer Funktion, die aus einem parallelen Abschnitt aufgerufen wird, werden privat.
Als static deklarierte Variablen sind wie globale Variablen gemeinsam genutzt.
Im Heap angelegt Variablen sind immer gemeinsam genutzt (shared).
36Optimierungstechniken in modernen Compilern Grundlagen
Zugriff auf globale Variablen
Globale Variablen in C++ werden im Allgemeinen gemeinsam von allen Threads genutzt.
Mit der Direktive threadprivate lassen sich von globalen Variablen für jeden Thread lokale Kopien erstellen.
Syntax: #pragma omp threadprivate(Liste), wobei Liste eine Liste
globaler Variablen ist. Die Direktive muss direkt nach jeder Deklaration der in Liste
genannten globalen Variablen stehen. Für jeden Thread wird eine eigene Kopie der globalen
Variablen angelegt. Unterschied zu privaten Variablen:
Werte bleiben über mehrere parallele Abschnitte hinweg erhalten, solange in jedem parallelen Abschnitt dieselbe Anzahl Threads erzeugt wird.
37Optimierungstechniken in modernen Compilern Grundlagen
Kritischer Abschnitt
Zu jedem Zeitpunkt darf höchstens ein Thread aus einem Team den kritischen Abschnitt bearbeiten.
Syntax: #pragma omp critical (Name)
Beispiel Berechnung von Pi:double piS() { const long num_iter = 20000; const double delta_x = 1.0 / num_iter; double sum = 0.0, x; int i; for(i = 1; i <= num_iter; ++i) { x = delta_x * (i - 0.5); sum += 4.0 / (1.0 + x * x); } return delta_x * sum;}
double piP() { const long num_iter = 20000; const double delta_x = 1.0 / num_iter; double sum = 0.0; double x, f_x; int i;
#pragma omp parallel for private(x, f_x) \ shared(delta_x , sum) for(i = 1; i <= num_iter; ++i) { x = delta_x * (i - 0.5); f_x = 4.0 / (1.0 + x * x); #pragma omp critical (cs_sum_f_x) sum += f_x; } return delta_x * sum;}
38Optimierungstechniken in modernen Compilern Grundlagen
Parallele Berechnung mit reduction
In einigen Fällen können dadurch kritische Abschnitte vermieden werden. Syntax für Klausel in der parallel for - Direktive:
Klausel ::= reduction (op : Variable [, Variable] ...) op muss ein kommutativer und assoziativer Operator sein, damit Reihenfolge der Berechnung
irrelevant ist. Variable muss einen skalaren Typ haben. Zu jeder Variable wird in jedem Thread eine private Kopie angelegt und mit dem neutralen
Element von op initialisiert. Ergebnisse werden dann in jedem Thread separat akkumuliert und an der
Synchronisationsbarriere zusammengefasst. Private Variable aus einer reduction-Klausel ist auch am Ende des parallelen Abschnitts definiert.
double piP() { const long num_iter = 20000; const double delta_x = 1.0 / num_iter; double sum = 0.0; double x; int i;
#pragma omp parallel for private(x) shared(delta_x) reduction (+: sum) for(i = 1; i <= num_iter; ++i) { x = delta_x * (i - 0.5); sum += 4.0 / (1.0 + x * x); } return delta_x * sum;}
39Optimierungstechniken in modernen Compilern Grundlagen
Schedule - Klausel
Dient der Festlegung, in wie viele Stücke die Iterationen einer for-Schleife zerlegt werden und wie diese Stücke die auf Threads verteilt werden.
Unterscheidung zwischen statisch: Jeder Thread führt genau die Iterationen aus, die ihm zu
Beginn der Arbeit aufteilenden Direktive zugewiesen wurden. Zuteilung ergibt sich aus der Anzahl der Iterationen der Schleife und der Anzahl der zur Verfügung stehenden Threads.
dynamisch: Nicht alle Iterationen werden sofort auf alle Threads verteilt. Endet ein Thread, dann werden ihm neue Iterationen zugewiesen.
Syntax für Klausel in der for - Direktive: schedule(type[, chunk])
type kann sein: static, dynamic, guided, runtime, chunk kann sein ein positiver ganzzahliger Wert, der sich
während der Schleifenausführung nicht ändert.
40Optimierungstechniken in modernen Compilern Grundlagen
Parameter für schedule-Klausel
type chunk Stücke Iterationen pro Stück
Bezeichnung
static - p n/p einfach statisch
static c n/c c überlappend
dynamic - n 1 einfach dynamisch
dynamic c n/c c einfach dynamisch
guided optional c weniger als n/c
anfangs n/p, dann
abnehmend
geführt
runtime - unterschiedlich
unterschiedlich unterschiedlich
n – Anzahl der Iterationen der for-Schleifep – Anzahl der Threads
41Optimierungstechniken in modernen Compilern Grundlagen
Statisch
Einfach statisch: Iterationen werden in ungefähr gleich große Stücke
aufgeteilt. Jedem Thread wird höchstens ein Stück zugewiesen.
Überlappend: Iterationen werden in Stücke mit jeweils c Iterationen
aufgeteilt. Die Stücke werden in der Reihenfolge der
Threadnummer an die Threads vergeben. Das letzte Stück kann weniger als c Iterationen
enthalten.
42Optimierungstechniken in modernen Compilern Grundlagen
Dynamisch
Chunk nicht angegeben: chunk wird als 1 angenommen und dann so
verfahren, als ob es angegeben wurde. Chunk wurde angegeben:
Die Iterationen werden in je c Elemente umfassende Stücke an die Threads vergeben.
Immer wenn ein Thread sein Stück abgearbeitet hat, fordert er ein neues Stück an.
Das letzte zugewiesene Stück kann auch hier weniger als c viele Iterationen enthalten.
43Optimierungstechniken in modernen Compilern Grundlagen
Geführt
Geführte Ablaufpläne sind dynamische Ablaufpläne.
Bei der Zuweisung von Iterationen an Threads ist die Stückgröße proportional zur Anzahl noch zu verteilender Iterationen geteilt durch die Anzahl der Threads im Team, jedoch nie kleiner als der Wert von chunk.
Beim Fehlen der Angabe für chunk wird chunk auf 1 gesetzt.
Die Stückgrößen werden bei jeder Zuweisung exponentiell kleiner, wobei die genaue Proportionalität dem Compiler überlassen ist.
44Optimierungstechniken in modernen Compilern Grundlagen
Laufzeit
Der zu verwendende Ablaufplan wird erst zur Laufzeit durch Auswertung der Umgebungsvariablen OMP_SCHEDULE ermittelt.
Der Wert der Variablen muss eine Zeichenkette sein, die dem Parameterformat eines der vier anderen Ablaufplantypen entspricht, also z. B. “guided,10“.
45Optimierungstechniken in modernen Compilern Grundlagen
Bedingte Parallelisierung
Führt eine Schleife nur wenige Iterationen aus, dann ist eine Arbeitsaufteilung nicht immer sinnvoll.
Bedingte Parallelisierung in parallel for-Direktive durch Klausel:
Klausel ::= if(cond) Falls cond zu false ausgewertet wird, wird der
Abschnitt nicht parallel ausgeführt.
46Optimierungstechniken in modernen Compilern Grundlagen
Anzahl Threads in einem Team
Anzahl der Threads, die beim Betreten eines parallelen Abschnitts gestartet werden, kann beeinflusst werden durch:
die Umgebungsvariable OMP_NUM_THREADS, die Funktion omp_set_num_threads(num), die Klausel num_threads(num)
• ist an eine parallel-Direktive angehangen,• num kann ein Ausdruck sein, dessen Wert sich erst zur Laufzeit ergibt.
Bei Betreten eines parallelen Abschnitts wird die Anzahl der zu startenden Threads wie folgt festgelegt:
Falls Klausel num_threads(num) angegeben ist, werden num viele Threads gestartet, sonst
falls durch omp_set_num_threads(num) eine Anzahl zu startender Threads festgelegt wurde, werden num viele Threads gestartet, sonst
falls die Umgebungsvariable OMP_NUM_THREADS gesetzt ist, werden entsprechend viele Threads gestartet, sonst
ist es der Implmenetierung des Compiler überlassen, wie viele Threads gestartet werden.
Über omp_get_max_threads() kann abgefragt werden, wie viele Threads gestartet werden, wenn der Programmierer die Anzahl nicht durch eine Klausel angibt.
47Optimierungstechniken in modernen Compilern Grundlagen
Beispiel
// Ausgabeprintf("%d", omp_get_num_threads ()); // 1 printf("%d", omp_get_max_threads ()); // 2omp_set_num_threads (8);#pragma omp parallel num_threads (4){ printf("%d", omp_get_num_threads ()); // 4 printf("%d", omp_get_max_threads ()); // 8}