Vorlesung, Wintersemester 2009/10M. Schölzel 1 Optimierungstechniken in modernen Compilern Optimierungstechniken für SMP- Architekturen

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


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


Optimierungstechniken für superskalare Prozessoren

Erzeugen grobranularer Parallelität


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…


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.


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.


Richtungsvektor für b bei i konstant

j k


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


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.


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


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


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



1. Schleife

2. SchleifeKeine Parallelisierung der

Iterationen möglich.

Synchronisations-barriere

Thread 1 Thread 2

Thread 1' Thread 2'


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


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


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.


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:


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


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


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


Optimierungstechniken für superskalare Prozessoren

OpenMP


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.


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.


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:


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.


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


#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.


Syntax für Sektionen

#pragma omp sections{ [# pragma omp section] { // ... } [#pragma omp section { // ... } ] …}


#pragma omp single

Initialer Thread



#pragma omp single u;

t;

}

}




Nur der Master-Thread führt u

aus.



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.


#pragma omp for

Initialer Thread



#pragma omp for for(...) {

} t;

}

}




Iterationen der for-Schleife

werden auf die Team-Mitglieder

aufgeteilt



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.


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]; } }}


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]; } }}


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.


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.


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).


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.


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;}


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;}


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.


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


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.


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.


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.


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“.


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.


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.


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}

Documents

Vorlesung, Wintersemester 2009/10M. Schölzel 1 Optimierungstechniken in modernen Compilern Optimierungstechniken für SMP- Architekturen