OpenMP - Forschungszentrum Jülich

Transcrição

Einführung in die Parallelprogrammierung
OpenMP Teil 1:
Einführung in OpenMP
Annika Hagemeier
Jülich Supercomputing Centre (JSC)
Forschungszentrum Jülich
Inhalt










Motivation
Was ist OpenMP?
Historie
OpenMP Grundlagen
Direktiven
Laufzeitroutinen
Umgebungsvariablen
Parallele Region
Parallele Ausführung kontrollieren
Vor- und Nachteile
17. November 2014
2
Literatur




Parallel Programming in OpenMP
R. Chandra, L. Dagum, D. Kohr, D. Maydan, J. McDonald, R.
Menon (2001)
Using OpenMP – Portable Shared Memory Parallel
Programming
B. Chapman, G. Jost, R. Van der Pas (2008)
OpenMP: Eine Einführung in die parallele Programmierung in
C/C++
S. Hoffmann, R. Lienhart (2008)
OpenMP Application Program Interface (Version 4.0)
OpenMP Architecture Review Board (Juli 2013)
http://www.openmp.org/mp-documents/OpenMP4.0.0.pdf

OpenMP 4.0.1 Beispiele (Februar 2014)
http://openmp.org/mp-documents/OpenMP_Examples_4.0.1.pdf
17. November 2014
3
Motivation


Die Entwicklung von Shared-Memory-Architekturen hat in
den letzen Jahren deutlich zugenommen.
Auch die Anzahl der Prozessoren hat deutlich zugenommen
(2 – 32 RISC-Prozessoren)
Wie parallelisiert man Anwendungen für SharedMemory-Architekturen?

hardware-spezifische Programmiermodelle?
⇒ nicht portabel
⇒ sind “low-level” und verlangen tiefe Programmierkenntnis
⇒ Aufwand nicht gerechtfertigt, da nur auf einer Plattform
anwendbar

MPI?
⇒ zwar portabel, aber Programmieraufwand sehr hoch
⇒ Aufwand nicht gerechtfertigt, da die Anzahl der Prozessoren
begrenzt
17. November 2014
4
Was ist OpenMP?
= Open Specifications for Multi Processing






OpenMP ist eine standardisierte Programmierschnittstelle
(API), die zur portablen Programmierung von Parallelrechnern mit gemeinsamem Speicher (bzw. gemeinsamem
Adressraum) entwickelt wurde
breite Unterstützung von Herstellern (u.a. SGI/CRAY, SUN,
IBM, Intel, Compaq)
läuft mit C/C++ und Fortran
nicht anwendbar auf Systemen mit verteiltem Speicher
keine Laufzeitüberprüfung hinsichtlich Korrektheit der
Direktiven (Deadlocks, Datenabhängigkeiten etc.)
aktuelle Spezifikation:


OpenMP Application Program Interface 4.0 (Juli 2013)
http://openmp.org/wp/
17. November 2014
5
Historie von OpenMP (1)

OpenMP ist ein kürzlich entwickelter Industriestandard


Vorgänger





proprietäre Ansätze einiger Hersteller (u.a. SGI, CRAY, SUN,
IBM) Ende der 80er
die Hersteller boten unterschiedliche Sets von Direktiven an,
die jedoch in Syntax und Semantik ähnlich waren
alle benutzen aus Portabilitätsgründen einheitliche Kommentaroder Pragma-Annotationen
verschiedene Ansätze zur Standardisierung mit wenig Erfolg
(PCF, ANSI X3H5)
OpenMP wurde durch die Entwickler motiviert


vom ersten Konzept bis zum angenommenen Standard: Juli
1996 - Oktober 1997
wachsendes Interesse an einer wirklich portablen Lösung
OpenMP Architectural Review Board (ARB)


Gruppe hauptsächlich aus Hardware- und Software-Herstellern
OpenMP Spezifikationen werden vom OpenMP ARB entwickelt
17. November 2014
6
OpenMP Spezifikationen:






1997
1998
2000
2002
2005

ein Standard für beide Sprachen

Klarstellungen besonders im Speichermodell
2008 V3.0


erstes API für Fortran (V1.0)
erstes API für C/C++ (V1.0)
Fortran (V2.0)
C/C++ (V2.0)
C/C++ und Fortran (V2.5)
Erweiterungen wie Task-Parallelität, geschachtelte Schleifen, ...
2011 V3.1

Erweiterungen wie Optimierung des Task-Modells,
Mechanismus um Threads an Prozesse zu binden, Erweiterung
des atomic-Pragmas, min/max-Reduktion für C/C++, ...
17. November 2014
7

2013 V4.0








Unterstützung für Beschleuniger (Identifizierung von CodeRegionen, die auf anderen Rechenlaufwerken gerechnet
werden sollen)
SIMD-Konstrukte zur Vektorisierung von seriellen und parallelen
Schleifen
Error Handling
Thread Affinity (Mechanismen zur Bestimmung, wo Threads
ausgeführt werden sollen)
Erweiterung des Task-Modells (Task-Gruppen, Abhängigkeiten
zwischen Tasks)
Fortran 2003 Unterstützung
Benutzerdefinierte Reduktionen
Neue Klausel bei atomic
17. November 2014
8
OpenMP Komponenten
1. Direktiven
 Instruktionen für Compiler, die OpenMP unterstützen:





Pragmas in C/C++
Quelltext-Kommentare in Fortran
Kontrollstrukturen zur Beschreibung der Parallelität
Datenumgebungskonstrukte zur Kommunikation
zwischen den Threads
Synchronisationkonstrukte zur Koordination der Threads
2. Laufzeitroutinen
 Abfragen und Ändern der Parameter der parallelen
Umgebung
 Synchronisation
3. Umgebungsvariablen
 Einstellen der Parameter der parallelen Umgebung
17. November 2014
9
Erstes Beispiel
Programm:
int main(void)
{
#pragma omp parallel
printf(“Hello World\n“);
}
Übersetzen (Beispiel):
Ausführen:
export OMP_NUM_THREADS=4
./hello
Hello world
Hello world
Hello world
Hello world
icc -openmp -o hello hello.c
17. November 2014
10
Ausführungsmodell (1)





OpenMP basiert auf dem fork/join Modell
Ein OpenMP-Programm startet als
einzelner Thread (master thread).
Weitere Threads (Team) werden durch
eine parallele Region erzeugt und am
Ende der parallelen Region wieder (an
das Betriebs- oder Laufzeitsystem)
zurückgegeben.
Ein Team besteht aus einer festen
Anzahl von Threads, die die parallele
Region redundant abarbeiten.
Am Ende der parallelen Region findet
eine Barrier-Synchronisation aller
Threads im Team statt.
Nach der parallelen Region führt der
master thread den Code (sequentiell)
fort.
17. November 2014
11
Ausführungsmodell (2)


In einem Programm können mehrere parallele Konstrukte
spezifiziert werden.
Folglich kann sich der master thread in einem Programm
mehrfach aufspalten und wieder zusammenfügen.
17. November 2014
12
Kommunikation und Datenumgebung (1)

jeder Thread hat eine eigene Datenumgebung oder
Ausführungskontext:




Master Thread:


globale Variablen
automatische Variablen in Unterfunktionen (Stack)
dynamisch angelegte Variablen (Heap)
Ausführungskontext existiert während der gesamten
Laufzeit des Programms
Worker Threads:



Auführungskontext existiert nur innerhalb einer parallelen
Region
eigener Stack zum Aufruf von Unterfunktionen
alle anderen Variablen sind entweder gemeinsam oder
privat
17. November 2014
13






Daten werden unterteilt in gemeinsame (engl. shared) und
private Daten
die Bindung einer Variablen in einer parallelen Region wird
individuell durch ein Statement vom Programmierer
festgelegt
Daten sind per Default, ohne weitere Angaben gemeinsam
eine Ausnahme bilden Schleifenvariablen:
 Schleifenvariablen einer parallelen Schleife sind immer
privat
neben den Attributen shared und private, kann eine
Variable auch das Attribut reduction besitzen
Reduktionsvariablen:


Mischung aus gemeinsam und privat
Gegenstand einer arithmetischen Operation am Ende eines
parallelen Konstrukts
17. November 2014
14

Gemeinsame Daten:




sind allen Threads bekannt und von diesen zugreifbar
alle Threads, die auf diese Daten zugreifen, greifen auf die
selbe Speicherstelle zu
Threads kommunizieren miteinander oder synchronisieren
sich über gemeinsame Daten
Private Daten:





jeder Thread legt seine eigene private Kopie an
jeder Thread greift nur auf seine eigene Speicherstelle in
seinem Ausführungskontext zu
nicht zugreifbar für andere Threads
existiert nur während der Ausführung einer parallelen
Region
Wert beim Eintritt und Austritt in die parallele Region
undefiniert
17. November 2014
15
Ausführungsmodel mit gemeinsamen Variablen
17. November 2014
16
Ausführungsmodel mit privaten Variablen
17. November 2014
17
Synchronisation


OpenMP Threads kommunizieren miteinander durch das
Schreiben und Lesen von gemeinsamen Daten
oft ist es jedoch nötig den Zugriff auf gemeinsame Daten bei
mehreren Threads zu koordinieren (synchronisieren):



mehrere Threads versuchen gleichzeitig die gleiche Variable zu
ändern
ein Thread liest eine Variable, während ein anderer die gleiche
Variable gerade ändert
ungeregelter Zugriff:
 der Wert der Variablen ist undefiniert oder hängt von der
Reihenfolge ab, in der die Threads auf die Variablen zugreifen
⇒ mehrere unabhängige Programmdurchläufe liefern unterschiedliche Ergebnisse
⇒ unzulässig, da das parallele Programm in jedem Fall die gleichen
Ergebnisse liefern soll, wie das serielle Programm
17. November 2014
18
Speichermodell
Geteilter Speicher mit gelockerter Konsistenz


alle Threads haben Zugriff zum Speicher
jeder Thread darf außerdem seine eigene temporäre Sicht
auf den Speicher haben




jeder Thread hat außerdem Zugriff auf einen (Thread-)
privaten Speicher


kein zwingend notwendiger Teil des Speichermodells
kann jedes Element zwischen Thread und Speicher darstellen
(z.B. Register oder Cache)
erlaubt das Halten von Variablen im Cache, so dass nicht jedes
Mal auf den Speicher zugegriffen werden muss
andere Threads haben dort keinen Zugriff
die flush-Direktive erzwingt Konsistenz zwischen
temporärer Sicht und Speicher
17. November 2014
19
OpenMP Direktiven (1)


Direktiven weisen den Compiler an, bestimmte CodeAbschnitte zu parallelisieren
man unterscheidet Direktiven für




Parallelität (for, parallel, sections, single, task, ...)
Synchronisation (barrier, critical, master, atomic, ...)
Daten (threadprivate)
alle für OpenMP relevanten Pragmas beginnen mit
#pragma omp


bzw.
!$omp
solche Pragmas werden von Compilern ohne OpenMPUnterstützung einfach ignoriert
eine OpenMP-Direktive bezieht sich immer auf den
folgenden strukturierten Block oder ein OpenMPKonstrukt
17. November 2014
20
OpenMP Direktiven (2)

OpenMP-Pragmas haben die allgemeine Form:
#pragma omp Direktive [Klausel[[,] Klausel] ...] new-line

Klauseln sind optional und beeinflussen das Verhalten der
Direktive, auf die sie sich beziehen





jede Direktive hat eine andere Menge von gültigen Klauseln
im Allgemeinen ist die Menge jedoch sehr ähnlich
für einige Direktiven ist diese Menge leer (keine Klauseln sind
erlaubt)
alle Anweisungen müssen mit dem Zeilenumbruch enden
Direktiven über mehrere Zeilen werden folgendermaßen
geschrieben:
#pragma omp Direktive hier_steht_der_Beginn \
und_hier_steht_der_Rest
17. November 2014
21
OpenMP Direktiven: Syntax



C/C++
Direktiven sind spezielle Compiler-Pragmas
Direktiven und API-Funktionen werden kleingeschrieben
es gibt keine END-Direktive wie in Fortran, sondern die
Direktive bezieht sich immer auf den folgenden strukturierten Block
#pragma omp Direktive [Klausel[[,] Klausel] ...] new-line
strukturierter Block
Beispiel:
int main() {
#pragma omp parallel default(shared)
printf(”hello world\n” );
}

Stand-alone Direktiven haben keinen zugehörigen Block
Beispiel:
#pragma omp barrier
17. November 2014
22
OpenMP Direktiven: Syntax


Fortran
Direktiven sind spezielle Kommentare
die Groß-/Kleinschreibung ist irrelevant
!$OMP Direktive [Klausel[[,] Klausel] ...] new-line
!$OMP END
Beispiel:
!$OMP PARALLEL DEFAULT(SHARED)
write(*,*) ´Hello world´
!$OMP END PARALLEL

Stand-alone Direktiven haben keinen zugehörigen Block
Beispiel:
!$omp barrier
17. November 2014
23
Strukturierter Block



besteht aus einem oder mehreren Statements
hat einen Eingang am Anfang und einen Ausgang am Ende
Nicht erlaubt:



Erlaubt:



Verzweigungen in den Block
Verzweigungen aus dem Block heraus
Verzweigungen innerhalb des Blocks
Beenden des Programms innerhalb des Blocks (z.B. mit exit())
Strukturierte Blöcke, die aus mehreren Statements
bestehen, müssen in C/C++ immer mit Klammern
umschlossen werden!
 ansonsten bezieht sich die Direktive nur auf das erste
Statement
17. November 2014
24
OpenMP Direktiven: Beispiele
/* fehlende Klammern, nur das 1. Statement wird parallel ausgeführt */
printf(“Ich werde parallel ausgeführt.\n”);
printf(“Ich werde NICHT parallel ausgeführt.\n”);
/* falsch gesetzte Klammer, Code compiliert nicht */
#pragma omp parallel default(shared) {
printf(“Ich werde auch parallel ausgeführt.\n”);
}
/* richtig gesetzte Klammern, beide Statements werden parallel
ausgeführt */
{
printf(“Ich werde auch parallel ausgeführt.\n”);
}
17. November 2014
25
Bedingte Übersetzung




OpenMP Direktiven werden von gewöhnlichen Compilern
(ohne OpenMP-Unterstützung) ignoriert
zusätzlich ermöglichen die meisten OpenMP-Compiler das
Ausschalten von OpenMP durch ein Compiler-Flag
⇒ das Programm kann sowohl seriell (ohne OpenMP) als
auch parallel ausgeführt werden
dies gilt jedoch nur für Direktiven
ein Programm kann jedoch auch andere OpenMP spezifische
Kommandos (z. B. Aufruf von Laufzeitroutinen) enthalten
 Bedingte Übersetzung
 OpenMP bietet die Möglichkeit der bedingten
Übersetzung
 Statements, die nur für die parallele Ausführung relevant
sind, werden markiert
17. November 2014
26
Bedingte Übersetzung: Syntax

C/C++:

das Makro _OPENMP wird zum selektiven Übersetzen
verwendet:


Bei OpenMP-Unterstützung wird _OPENMP auf den Wert yyyymm
gesetzt (Jahr und Monat der unterstützen OpenMP-Version)
OpenMP-Kommandos werden mit einer Direktive zur
Abfrage des Makros versehen
#ifdef _OPENMP
iam = omp_get_thread_num();
#endif

Fortran:
 OpenMP-Kommandos werden mit !$ am Zeilenanfang
gekennzeichnet
!$
17. November 2014
iam = OMP_GET_THREAD_NUM()
27
Parameterangaben zur Datenumgebung (1)
private(Variablenliste)


Variablen in der Variablenliste werden als privat deklariert
jeder Thread bekommt seine eigene private Kopie der Variablen
shared(Variablenliste)


Variablen in der Variablenliste werden als gemeinsam deklariert
alle Threads greifen auf die selbe Variable zu
default(private / shared / none)




ändert das Standardverhalten von Variablen, die nicht explizit mit
einer shared- bzw. private-Klausel aufgeführt werden
default(private): existiert nur für Fortran
default(shared): ändert nichts am Standardverhalten
default(none):


für jede Variable in einer parallelen Region muss die Zugriffsklausel
explizit angegeben werden, ansonsten Fehler beim Compilieren
Aufdecken von Programmierfehlern, die aus falschen Annahmen über
Variablenzugriffe resultieren
17. November 2014
28
Parameterangaben zur Datenumgebung (2)


der Inhalt privater Variablen ist beim Eintritt und beim Verlassen
einer parallelen Region undefiniert
⇒ minimiert das Kopieren von Daten
die Klauseln firstprivate und lastprivate erlauben eine
Initialisierung bzw. Finalisierung der Werte privater Variablen
firstprivate(Variablenliste)


Variablen in der Variablenliste werden als privat deklariert und
erhalten den Wert, den die Variable vor Eintritt in die prallele
Region hatte
jede Kopie der Variablen wird initialisiert (nur einmal pro Thread)
lastprivate(Variablenliste)

Variablen in der Variablenliste werden als privat deklariert und der
Thread, der die sequentiell letzte Iteration einer parallelen Schleife
ausführt, kopiert den Wert seiner Variablen auf die Variable
außerhalb der parallelen Region
17. November 2014
29
Laufzeitroutinen

die Funktionen der Laufzeitbibliothek werden hauptsächlich
dazu verwendet, Parameter der Laufzeitumgebung von
OpenMP abzufragen bzw. zu setzen


bietet außerdem portable Funktionen zur Zeitmessung



z. B. omp_set_num_threads(), omp_get_num_threads()
z. B. omp_get_wtime() liefert die Zeit in Sekunden
zusätzlich enthält die Bibliothek Funktionen zur
Synchronisation von Threads (z. B. omp_set_lock())
zur Verwendung von Funktionen der Laufzeitbibliothek muss
die Header-Datei omp.h eingebunden werden
#ifdef _OPENMP
#include <omp.h>
#endif
17. November 2014
30
Laufzeitroutinen der Ausführungsumgebung (1)
void omp_set_num_threads(int num_threads);

setzt die Anzahl der Threads in einem Team
int omp_get_num_threads(void);

gibt die Anzahl der Threads im aktuellen Team zurück
int omp_get_max_threads(void);

gibt die maximale Anzahl Threads zurück, die verwendet werden
können um ein neues Team von Threads zu erzeugen
int omp_get_thread_num(void);

gibt die Thread-ID zurück (Zahl zwischen 0 und n-1)
int omp_get_num_procs(void);

liefert die Anzahl der Prozessoren, auf denen das Programm
parallel ausgeführt werden kann
17. November 2014
31
int omp_in_parallel(void);

liefert true (Wert ungleich 0) zurück, wenn sich der Aufruf in
einer parallelen Region befindet, ansonsten false (Wert 0)
void omp_set_dynamic(int dynamics_threads);

die dynamische Anpassung von Thread-Teamgrößen kann mit
dieser Funktion aktiviert und deaktiviert werden
int omp_get_dynamic(void);

gibt an, ob die dynamische Anpassung von Thread-Teamgrößen
aktiviert wurde oder nicht
void omp_set_nested(int nested);

aktiviert verschachtelte Parallelität bei ineinander verschachtelten parallelen Abschnitten
int omp_get_nested(void);

fragt ab, ob verschachtelte Parallelität aktiviert ist
17. November 2014
32
weitere (hier nicht behandelte) Laufzeitroutinen:









omp_get_cancellation()
omp_set_schedule()
omp_get_schedule()
omp_get_thread_limit()
omp_set_max_active_levels()
omp_get_max_active_levels()
omp_get_level()
omp_getancestor_thread_num()
omp_get_team_size()
4.0









omp_get_active_level()
omp_in_final()
4.0 omp_get_proc_bind()
4.0 omp_set_default_device()
4.0 omp_get_default_device()
4.0 omp_get_num_devices()
4.0 omp_get_num_teams()
4.0 omp_get_team_num()
4.0 omp_is_initial_device()
nähere Informationen zu den oben genannten Funktionen im
OpenMP-Standard
17. November 2014
33
Laufzeitroutinen zur Zeitmessung

die OpenMP-Laufzeitbibliothek bietet portable Funktionen zur
Messung der Ausführungszeit von Programmen
double omp_get_wtime(void);



liefert die Zeit (in Sekunden) zurück, die seit einem festen
Zeitpunkt in der Vergangenheit verstrichen ist
die zeitliche Auflösung ist begrenzt und von der zugrunde
liegenden Architektur und Betriebssystem abhängig
⇒ zu messende Laufzeit sollte nicht zu kurz sein
zur Zeitmessung speichert man den Zeitpunkt des Beginns der
Ausführung ab und bildet nach deren Ende die Differenz aus
diesem Wert und der aktuellen Zeit
double omp_get_wtick(void);


die Rückgabewerte von omp_get_wtime() basieren auf einem
internen Timer
omp_get_wtick() gibt die Anzahl Sekunden zwischen zwei Ticks
dieses Timers zurück
17. November 2014
34
Beispiel: Zeitmessung

befindet sich der zu vermessende Code komplett innerhalb
eines parallelen Abschnitts, so kann der Aufruf von
omp_get_wtime() innerhalb eines single-Blocks erfolgen,
damit die Zeitnahme nur einmal erfolgt
{
// ...
#pragma omp single nowait
start = omp_get_wtime();
// ... zu vermessender Codeabschnitt
#pragma omp single nowait
end = omp_get_wtime();
// ...
} // Ende paralleler Abschnitt
printf(“Zeit in Sekunden: %lf\n”, end - start);
17. November 2014
35
Umgebungsvariablen (1)



werden dazu verwendet, Parameter der Laufzeitumgebung von
OpenMP zu setzen
die Standardwerte der meisten Umgebungsvariablen sind
implementierungsabhängig (Ausnahme: OMP_NESTED)
werden einmal zu Beginn der Programmausführung abgefragt
(Änderung der Parameter während der Programmausführung nur
über Laufzeitroutinen möglich)
OMP_SCHEDULE type[,chunk]




nur anwendbar auf parallele Schleifen mit Schedule-Typ runtime
Schedule-Typ muss angegeben werden
optional kann noch die Blockgröße (chunk) angegeben werden
Beispiele: export OMP_SCHEDULE=”dynamic”
export OMP_SCHEDULE=”GUIDED,4”
OMP_NUM_THREADS num


setzt die Anzahl der Threads in einem Team
Beispiel: export OMP_NUM_THREADS=4
17. November 2014
36
Umgebungsvariablen (2)
OMP_DYNAMIC dynamic


dynamische Anpassung der Anzahl der Threads erlauben bzw.
nicht erlauben
Beispiel: export OMP_DYNAMIC=TRUE
OMP_NESTED nested



Verschachtelung von parallelen Konstrukten erlauben bzw. nicht
erlauben (default: OMP_NESTED=FALSE)
Beispiel: export OMP_NESTED=TRUE
weitere (hier nicht behandelte) Umgebungsvariablen:






OMP_STACKSIZE
OMP_WAIT_POLICY
OMP_MAX_ACTIVE_LEVELS
OMP_THREAD_LIMIT
OMP_PROC_BIND

4.0

4.0

4.0

4.0
OMP_CANCELLATION
OMP_DEFAULT_DEVICE
OMP_DISPLAY_ENV
OMP_PLACES
nähere Informationen zu den oben genannten Umgebungsvariablen
im OpenMP-Standard
17. November 2014
37
Parallelität mit OpenMP
OpenMP bietet verschiedene Möglichkeiten der Parallelität

Parallelisierung von Schleifen:



Parallele Regionen:



ermöglicht die parallele Ausführung eines beliebigen CodeAbschnitts
Parallelisierung im SPMD-Stil (Single-Program Multiple-Data)
Work-Sharing Konstrukte:


Haupteinsatzgebiet / Stärke von OpenMP
jeder Thread führt eine (andere) Teilmenge von Iterationen einer
Schleife aus
ermöglicht die Aufteilung der Arbeit auf die Threads innerhalb
einer parallelen Region
Tasks:

erlaubt die einfache Parallelisierung von Operationen auf
komplexen Datenstrukturen wie Listen oder Bäumen
17. November 2014
38
Parallele Region



grundlegendes Konstrukt zur Parallelisierung eines
beliebigen Programmabschnitts
Schachtelung von parallelen Regionen im Prinzip möglich,
aber vielfach noch nicht implementiert oder nicht per
Default möglich
innerhalb einer parallelen Region werden weitere
Konstrukte eingesetzt
 zur Koordination der einzelnen Threads (z.B. critical)
 zur Aufteilung der Arbeit auf die Threads (z.B. for,
sections)
17. November 2014
39
Parallele Region: Syntax
#pragma omp parallel [Klausel[[,] Klausel] ...] new-line
Klauseln:









private (list)
shared (list)
default (shared | none)
firstprivate (list)
reduction (operator: list)
if (scalar-expression)
copyin (list)
num_threads (integer-expression)
4.0 proc_bind (master | close | spread)
17. November 2014
40
Parallele Region: Ausführungsmodell



zu Beginn einer parallelen Region wird ein Team von
Threads erzeugt (Thread 0 ist der Master Thread, der zuvor
den sequentiellen Code ausgeführt hat)
die Threads des Teams bearbeiten den Code gemeinsam
bis zum Ende der parallelen Region ab
am Ende der parallelen Region findet eine BarrierSynchronisation statt, danach fährt der Master Thread mit
der sequentiellen Ausführung fort
Master
Fork
{
Worker
printf(“Hello World!\n”);
}
17. November 2014
printf()
printf()
printf()
Join
41
Parallele Ausführung kontrollieren (1)

Dynamisches Ausschalten der parallel-Direktive mit der ifKlausel:





die Entscheidung, ob ein Codeabschnitt parallel ausgeführt
werden soll oder nicht kann von Faktoren abhängen, die erst zur
Laufzeit feststehen
wenn ein Programm in eine parallele Region mit einer if-Klausel
eintritt, wird zunächst die logische Bedingung ausgewertet
ist die Bedingung true, wird die Region parallel ausgeführt
ist die bedingung false, wird die Region seriell ausgeführt
Abfrage auf parallele Ausführung mit omp_in_parallel():


true, wenn die Funktion innerhalb einer parallel ausgeführten
Region aufgerufen wurde
false, wenn die Funktion innerhalb einer seriellen Region oder
einer serialisierten parallelen Region aufgerufen wurde
17. November 2014
42

Threadaffinität kontrollieren mit der proc_bind-Klausel:


Die proc_bind-Klausel definiert die Regel zur Platzierung der
Threads auf der zur Verfügung stehenden Partition
Erlaubt sind die folgenden Regeln:

master:

jeder Thread im Team soll der selben Stelle zugewiesen
werden, wie der Master Thread
close:
die Threads im Team sollen Stellen nahe der des Master
Threads zugewiesen werden

spread:
die Threads im Team sollen möglichst breit gestreut auf die
zu verfügung stehende Partition verteilt werden
17. November 2014
43
Anzahl der Threads kontrollieren:
 export OMP_NUM_THREADS=n


omp_set_num_threads(n)



wird die Umgebungsvariable vor Programmstart gesetzt, werden
Teams mit n Threads erzeugt
Einstellung der Teamgröße zur Laufzeit
beeinflusst nur nachfolgende parallele Regionen
num_threads

kontrolliert die
Teamgröße für eine
spezielle Region
#pragma omp parallel for num_threads(4)
for (i=0; i<16; i++)
[…]
Prioritätenreihenfolge der Mechanismen:



num_threads
omp_set_num_threads(n)
OMP_NUM_THREADS
17. November 2014
44
Vorteile von OpenMP





erlaubt die Parallelisierung seriellen Codes durch Hinzufügen
von Direktiven
einfache parallele Algorithmen sind einfach und schnell zu
implementieren
Aufblähung des Codes sehr gering
 (in der Regel 2 – 25%)
guter Code compiliert und läuft auch mit einem
gewöhnlichen Compiler auf einer CPU (Direktiven werden
vom Compiler ignoriert)
gemeinsamer Adressraum vereinfacht die Entwicklung von
Debuggern
17. November 2014
45
Nachteile




Skalierbarkeit ist begrenzt
Spezieller Compiler wird benötigt
Programmierer hat nicht die volle Verantwortung, Aktionen
wie die Aufteilung der Arbeit oder die Kommunikation
zwischen Threads werden implizit realisiert
 implizite Prozesse schwer nachvollziehbar
 wann wird kommuniziert und wann nicht
 wie teuer ist die Kommunikation
kann nur auf Architekturen mit gemeinsamem Speicher
verwendet werden
17. November 2014
46
Übung
Übung 10:
17. November 2014
47
OpenMP Teil 2:
Schleifenparallelisierung
Annika Hagemeier
Inhalt


Syntax
Klauseln









Einschränkungen
Laufzeitverhalten
Scheduling-Strategien
Reduktion
Datenabhängigkeiten und Race Condition




schedule
if
ordered
copyin
Flussabhängigkeit (Flow Dependence)
Gegenabhängigkeit (Anti Dependence)
Ausgabeabhängigkeit (Output Dependence)
Intel Thread Checker
17. November 2014
2
Parallele Schleife




Haupteinsatzgebiet von OpenMP
viele Programme können effizient parallelisiert werden nur
durch Parallelisierung der Schleifen
inkrementelle Parallelisierung: Hinzufügen von Direktiven und nur kleine lokale Änderungen im Programmtext
parallele Ausführung von Schleifen lässt sich als SPMD
(single program multiple data) beschreiben:


Korrektheit: die parallele Version muss die selben
Ergebnisse liefern, wie die serielle Version


jeder Thread führt den in der Schleife enthaltenen Code aus,
aber jeder für eine andere Teilmenge von Iterationen und damit
auf anderen Daten
Nicht alle Schleifen lassen sich ohne weiteres parallellisieren
for-Direktive: Schleifenparallelisierung in OpenMP
17. November 2014
3
Parallele Schleife: Syntax
#pragma omp for [Klausel[[,] Klausel] ...] new-line
for ( var = startwert; var op endwert; inkrement )
Schleifenkörper
parallelisiert nur die unmittelbar folgende Schleife

Klauseln:








private (list)
firstprivate (list)
lastprivate (list)
schedule (kind [, chunksize])
collapse (n)
ordered
nowait
17. November 2014
4
Parallele Schleife: Syntax (Kurzform)
#pragma omp parallel for [Klausel[[,] Klausel] ...] new-line
for ( var = startwert; var op endwert; inkrement )
Schleifenkörper



die Direktiven #pragma omp parallel und #pragma omp
sections lassen sich zu einer Direktive zusammenfassen
jedoch nur, wenn die parallele Region nur aus einer
parallelen Schleife besteht
alle für parallel und for gültigen Klauseln (außer nowait)
sind erlaubt:







lastprivate (list)

num_threads (n)
schedule (kind[, chunksize])

collapse (n)

shared (list)
ordered
copyin (list)
4.0 proc_bind (master | close | spread)



17. November 2014
private (list)
firstprivate (list)
5
Geschachtelte Schleifen

die for-Direktive bezieht sich nur auf die unmittelbar
folgende Schleife
Beispiel 1: Zeilensumme
#pragma omp parallel for
for ( i = 0; i < n; i++ ) {
a[i][0] = 0;
for ( j = 0; j < m; j++ )
a[i][0] = a[i][0] + a[i][j];
}
Beispiel 2: Glättungsfunktion
for ( i = 1; i < n; i++ ) {
for ( j = 1; j < m - 1; j++ )
a[i][j] = ( a[i-1][j-1] + a[i-1][j] + a[i-1][j+1] ) / 3.0;
}
17. November 2014
6
for-Direktive: collapse-Klausel

zur Parallelisierung von perfekt geschachtelten Schleifen





alle Schleifenvariablen müssen komplett unabhängig
voneinander sein
nur die innerste Schleife darf beliebigen Code enthalten, alle
anderen dürfen nur geschachtelte Schleifen enthalten
sinnvoll z. B. bei Iterationen über mehrdimensionale Felder
n gibt an, wie viele Schleifen vom Compiler in eine Schleife
zusammengefasst (kollabiert) werden, d.h. wie viele Schleifen geschachtelt sind
Reihenfolge der
Iterationen der
kollabierten Schleife
hängt von der
sequentiellen
Reihenfolge ab
17. November 2014
#pragma omp parallel for collapse(3)
for(int l=0; l<10; ++l)
for(int j=0; j<3; ++j)
for(int k=0; k<7; ++k){
/* Nur hier darf
beliebiger Code stehen! */
foo[l][j][k] = 0;
}
7
Geordnete Ausführung mit ordered
#pragma omp ordered new-line

die ordered-Direktive bewirkt, dass der folgende Block in
der originalen sequentiellen Reihenfolge ausgeführt wird



z.B. geordnetes Schreiben von Werten in eine Datei
der Code in der ordered-Region wird sequentialisiert,
während der Code außerhalb der Region parallel
abgearbeitet wird
sollen Teile einer parallelen Schleife geordnet ausgeführt werden, so muss
das Schlüsselwort ordered
sowohl als Klausel als
auch als Direktive
eingefügt werden
17. November 2014
/* ordered als Klausel */
#pragma omp parallel for ordered
for ( i=0; i<n; i++ ) {
a[i] = f(i);
/* ordered als Direktive */
#pragma omp ordered
printf("a[%d] = %d", i, a[i]);
}
8
Einschränkungen der Schleifenstruktur
Damit eine Schleife in OpenMP parallelisiert werden kann,
muss sie in kanonischer Form vorliegen (erleichtert die
Compiler-basierte Parallelisierung):
 die Anzahl der Schleifendurchläufe muss vor dem Eintritt
in die Schleife berechnet werden können und darf sich
innerhalb der Schleife nicht ändern
 die Zählvariable darf innerhalb der Schleife nicht verändert
werden
 das Programm muss alle Iterationen beenden




kein vorzeitiges Verlassen durch eine break-Anweisung
keine Ausnahme innerhalb der Schleife werfen, die erst
außerhalb aufgefangen wird
beenden der aktuellen Iteration und Wechsel zur nächsten
Iteration möglich (continue erlaubt)
beenden des gesamten Programms innerhalb der Schleife
möglich (exit erlaubt)
17. November 2014
9
C/C++
Schleifenstruktur
for ( var = startwert ; var op endwert ; inkr-op )
Schleifenkörper



Logischer Operator (op):
 folgende Operatoren sind erlaubt:
Inkrementoperator (inkr-op):
 müssen den Wert der Zählvariablen in jedem Schleifendurchlauf um denselben
Wert verändern
<, <=, >, >=
++var, var++, var, var
var += inkr, var = inkr,
var = var + inkr,
var = inkr + var,
var = var – inkr
Schleifenvariable (var):
 muss vom Typ int sein
 ist standardmäßig private
 Wert ist unbestimmt nach Schleifendurchlauf (Ausnahme:
lastprivate)
17. November 2014
10
Laufzeitverhalten







außerhalb der Schleife führt ein Master Thread den Code
sequentiell aus
erreicht der Master Thread eine parallele Schleife, erzeugt er
0 oder mehr Slave Threads
die Schleife wird gleichzeitig von allen Threads ausgeführt
jede Iteration wird nur einmal ausgeführt
jeder Thread kann mehr als eine Iteration ausführen
Variablen sind entweder shared oder private für jeden
Thread
am Ende der parallelen Schleife findet eine BarrierSynchronisation statt


alle Threads warten aufeinander, bevor sie mit der Ausführung
des restlichen Codes im parallelen Abschnitt fortfahren, bzw. der
Master Thread mit der seriellen Ausführung fortfährt
Vermeidung der Synchronisation durch Angabe von nowait
17. November 2014
11
Scheduling
Wie werden die Iterationen einer parallelen Schleife
auf die Threads eines Teams aufgeteilt?

Die Art der Aufteilung einer parallelen Schleife in OpenMP
lässt sich durch die schedule-Klausel beeinflussen
Wie teilt man die Iterationen am effizientesten auf?
 die Wahl der richtigen Scheduling-Strategie kann das
Laufzeitverhalten einer Schleife entscheidend beeinflussen
 Ziel: Arbeitslast möglichst ausgewogen verteilen
 Idealfall: alle Threads brauchen gleich lange, um ihre
Teilaufgaben zu erfüllen
 nicht ausbalancierte Schleifen zwingen schnelle Threads auf
langsamere zu warten
 man unterscheidet statisches und dynamisches
Scheduling
17. November 2014
12
Statisches Scheduling

die Verteilung der Iterationen geschieht zu Beginn des
Schleifendurchlaufs, basierend auf:




Anzahl der Threads
Anzahl der Iterationen
Index einer Iteration
ein Thread erhält bei jeder Ausführung dieselben
Iterationen

geringe Flexibilität

so gut wie kein Scheduling-Overhead

sinnvoll bei Schleifen mit der gleichen Menge an Arbeit pro
Iteration
for ( i = 0; i < n; i++ )
z[i] = a * x[i] + y;
17. November 2014
13
Dynamisches Scheduling

die Verteilung der Iterationen geschieht während der
Ausführung der Schleife






Jeder Thread bekommt eine Teilmenge der Iterationen zu Beginn
des Schleifendurchlaufs
Nach Beendigung bekommt jeder Thread weitere Iterationen
zugewiesen
welcher Thread welche Iterationen bearbeitet kann sich von
Programmausführung zu Programmausführung ändern
mehr Flexibilität (Ausgleich der Lastverteilung)
höherer SchedulingOverhead durch zusätzlichen Verwaltungsaufwand
sinnvoll bei Schleifen mit
unterschiedlicher
Arbeitslast pro Iteration
17. November 2014
for ( i = 0; i < n; i++ )
if ( f(i) )
do_big_work(i);
else
do_small_work(i);
14
Schedulingstrategien (1)


Die verschiedenen Schedulingstrategien in OpenMP
unterscheiden sich dadurch:
 Wie die Iterationen einer Schleife in Blöcke (engl. chunks)
aufgeteilt werden
 Wie die Chunks den Threads eines Teams zugewiesen
werden
Syntax:
schedule(type[, chunk])

erlaubte Angaben für type:
static

dynamic

guided

runtime

auto
chunk: positiver ganzzahliger Wert, der sich durch die Schleifenausführung nicht ändern darf


17. November 2014
15
static

ohne Angabe von chunk:



Iterationen werden in ungefähr gleich große Blöcke aufgeteilt
jeder Thread bekommt höchstens einen Block
mit Angabe von chunk:



Iterationen werden in Blöcke der Größe chunk aufgeteilt
der letzte Block kann dabei auch weniger als chunk Iterationen
enthalten
die Blöcke werden in Reihenfolge der Threadnummern reihum
an die Threads verteilt
dynamic



jeder anfragende Thread bekommt einen Block zugewiesen
wenn chunk nicht angegeben wird, ist die Blockgröße 1
der letzte Block kann auch kleiner als chunk sein
17. November 2014
16
guided




exponentiell fallende Blockgröße (compilerabhängig)
chunk definiert die minimale Blockgröße
wird chunk nicht angegeben ist die minimale Blockgröße 1
Zuteilung erfolgt dynamisch, d. h. jeder anfragende Thread
erhält einen Block
runtime




darf nur ohne chunk-Wert angegeben werden
Schedulingstrategie wird über Umgebungsvariable definiert
und erst zur Laufzeit ermittelt
ist die Variable nicht gesetzt, ist das Scheduling abhängig
von der Implementierung
Syntax: export OMP_SCHEDULE=“type[,chunksize]”

Beispiel: export OMP_SCHEDULE=“guided,10”
17. November 2014
17
auto


der Compiler und/oder die Laufzeitumgebung entscheidet
über das Scheduling der Schleife
der Programmierer gibt der Implementierung die Freiheit
jede mögliche Art der Aufteilung der Iterationen auf die
Threads zu wählen
17. November 2014
18
guided, 7
3
2
1
dynamic, 7
Thread ID
0
3
2
1
0
3
static
2
1
0
0
25
50
75
100
125
150
175
200
Iterationsnummer
17. November 2014
19
Beispiel: parallele Schleife
#include <stdio.h>
#include <omp.h>
#define N 100
int main(int argc, char *argv[])
{
int iam,nthreads;
int i,a[N],b[N];
#pragma omp parallel private(iam,nthreads)
{
iam=omp_get_thread_num();
nthreads=omp_get_num_threads();
#pragma omp for schedule(dynamic,10)
for(i=0;i<N;i++) {
a[i]=iam;
}
#pragma omp for schedule(guided)
for(i=0;i<N;i++) {
b[i]=iam;
}
}
for(i=0;i<N;i++) {
printf("a[%03d]=%d , b[%03d]=%d\n",i,a[i],i,b[i]);
}
return 0;
}
17. November 2014
20
parallel for vs. parallel
Master
Master
Worker
0 15
0 15
0 15
Worker
0 15
{
for ( i=0; i<16; i++ )
[…]
}
17. November 2014
0 3
4 7
8 11
12 15
{
#pragma omp for
for ( i=0; i<16; i++ )
[…]
}
21
Reduktionen





häufig wird in Schleifen wiederholt mittels eines binären
Operators ein Wert in einer Variablen akkumuliert
solche Schreibzugriffe auf gemeinsamen Variablen
müssen in jeder Iteration synchronisiert werden
kann die Laufzeit des parallelen Programms jedoch negativ
beeinflussen
zur effizienten Durchführung solcher Operationen stellt
OpenMP deshalb die reduction-Klausel zur Verfügung
Voraussetzung: der Operator ist kommutativ und
assoziativ, so dass das Endergebnis nicht von der
Ausführungsreihenfolge der Einzeloperationen abhängt
sum = 0;
#pragma omp parallel for reduction(+:sum)
for ( i = 0; i < n; i++ )
sum = sum + b[i];
17. November 2014
22
Reduktionen: Syntax
C/C++
reduction (op: Variable [, Variable] ...)



für alle Variablen in der Liste wird in jedem Thread eine private
Kopie angelegt und mit dem entsprechenden neutralen Element
des Operators initialisiert
während der parallelen Ausführung werden
zunächst die Zwischenergebnisse in den
Erlaubte Operatoren:
privaten Instanzen akkumuliert
am Ende des parallelen Abschnitts wird
dann synchronisiert die ursprüngliche
Variable des Master Threads akkumuliert
op:

erlaubte Operatoren siehe Tabelle
Variable:

skalare Variable vom Typ shared

nicht erlaubt sind:
Arrays, Pointer und const-Variablen
17. November 2014
23
Reduktionen: Syntax
Fortran
reduction ({op | intrinsic}: Variable [, Variable] ...)
für alle Variablen in der Liste wird in jedem Thread eine private

Kopie angelegt und mit dem entsprechenden neutralen Element
des Operators initialisiert
während der parallelen Ausführung werden
zunächst die Zwischenergebnisse in den
Erlaubte Operatoren:
privaten Instanzen akkumuliert
am Ende des parallelen Abschnitts wird
dann synchronisiert die ursprüngliche
Variable des Master Threads akkumuliert


op | intrinsic:

erlaubte Operatoren siehe Tabelle
Variable:



skalare Variable vom Typ shared
nicht erlaubt sind Fortran Pointer
ALLOCATABLE-Variablen müssen allokiert sein
und dürfen während der Reduktion nicht
deallokiert werden
17. November 2014
24
Reduktionen: benutzerdefiniert
4.0
C/C++
#pragma omp declare reduction( Operatorname : Typenliste
: Kombinierer) [NeutralesElement] new-line

definiert einen neuen Operator, der wie vordefinierte
Operatoren bei Reduktionen verwendet werden kann
Operatorname:

Name des Operators
Typenliste:

Liste von gültigen Variablentypen für den Operator
Kombinierer:


Ausdruck, der beschreibt, wie zwei Teilergebnisse zusammengefügt
werden
dazu können die Variablen omp_in (private Kopie, die Teilergebnis
enthält) und omp_out (private Kopie, die Wert nach zusammenfügen
zweiter Teilergebnisse enthält) verwendet werden
NeutralesElement:

Klausel zur Bestimmung des neutralen Elementes mit der Form:

initializer(expr), wobei expr omp_priv=initializer oder

Funktionsname( Argumentenliste )
17. November 2014
25
Benutzerdefinierte Reduktion: Beispiel

4.0
neuen Operator merge definieren:
#pragma omp declare reduction (merge : std::vector<int> :
omp_out.insert(omp_out.end(), omp_in.begin(), omp_in.end()))

neuen Operator merge in einer Reduktion verwenden:
void schedule (std::vector<int> &v, std::vector<int> &filtered) {
#pragma omp parallel for reduction (merge : filtered)
for (std::vector<int>::iterator it=v.begin(); it<v.end(); it++)
If ( filter(*it)) filtered.push_back(*it);
}
17. November 2014
26
Datenabhängigkeiten und Race Condition



die Parallelisierung muss die Korrektheit eines Programms
erhalten
Datenabhängigkeiten können die Korrektheit eines
Programms beeinflussen
typische Multi-Prozessor Programmierfehler treten auf, wenn:





zwischen zwei Synchronisationspunkten zwei oder mehr
Threads gleichzeitig auf die gleiche Speicherstelle/Variable
zugreifen und
mindestens einer der Threads den Wert der Variablen
verändert und
der Zugriff nicht geregelt (z.B. durch critical) ist
in vielen Fällen fehlen Anweisungen wie private oder barrier
Datenabhängigkeiten in parallelen Programmen können eine
Wettlaufsituation oder Race Condition hervorrufen ⇒
Ergebnisse hängen von der Reihenfolge ab, in der die
Operationen ausgeführt werden
17. November 2014
27
Data Races


gleichzeitige Zugriffe auf die gleiche Variable/Speicherstelle
werden Data Races genannt
keine Synchronisation notwendig, wenn alle Zugriffe nur lesen
sind:
#pragma omp parallel for shared(a,b)
for ( i = 0; i < n; i++ ) {
a[i] = a[i] + b;
}


b ist als shared deklariert:
 b wird nicht verändert, nur gelesen
 kein Konflikt bzgl. b → keine Synchronisation notwendig
a[ ] ist als shared deklariert:
 jeder Thread modifiziert eine andere Stelle von a[ ]
 kein Konflikt bzgl. a[ ] → keine Synchronisation notwendig
17. November 2014
28
Beispiel: Data Races
for ( i = 1; i =< 2; i++ )
a[i] = a[i] + a[i-1];



Anfangswerte:
a[0] = 1;
a[1] = 1;
a[2] = 1;
das Ergebnis für a[i] hängt vom Ergebnis an der Stelle i-1 ab
kein Problem bei serieller Ausführung, das a[i-1] vor a[i]
berechnet wird
bei paralleler Ausführung mit mehreren nebenläufigen
Threads ist dies nicht mehr garantiert:


a[2] wird mit dem neuen Wert von
a[1] berechnet
a[0] = 1;
a[1] = 2;
a[2] = 3;
a[2] wird mit dem alten Wert von
a[1] berechnet
a[0] = 1;
a[1] = 2;
a[2] = 2;
17. November 2014
29
Vermeidung von Abhängigkeiten
wichtig bei der Parallelisierung sind Abhängigkeiten zwischen
verschiedenen Iterationen einer parallelen Schleife

keine Abhängigkeit:

wenn auf eine Speicherstelle nur lesend zugegriffen wird

wenn auf eine Speicherstelle nur in einer Iteration zugegriffen
wird



Abhängigkeit:

wenn auf eine Speicherstelle in mehr als einer Iteration
zugegriffen wird und mehr als einmal beschrieben wird
Faustregel: eine Schleife kann ohne weiteres parallelisiert werden,

wenn alle Zuweisungen Zuweisungen zu unterschiedlichen
Feldelementen sind

wenn jedem Element höchstens in einer Iteration ein Wert
zugewiesen wird

wenn in keiner Iteration von einem Element gelesen wird, dass
in einer anderen Iteration mit Werten belegt wird
17. November 2014
30
Klassifizierung von Abhängigkeiten



Klassifizierung von Abhängigkeiten zur Entscheidung:
 ob die Abhängigkeit beseitigt werden muss
 ob die Abhängigkeit beseitigt werden kann
 welche Technik zur Beseitigung verwendet werden kann
loop-carried und non-loop-carried Dependences:
 non-loop-carried Dependences sind in vielen Fällen
ungefährlich
weitere Abhängigkeiten:
 Flow Dependence
 Anti Dependence
 Output Dependence
17. November 2014
31
Flussabhängigkeit (Flow Dependence)
for ( i = 0; i < n; i++ ) {
x = x + a[i];
}







zwei Zugriffe A1 und A2 auf die gleiche Speicherstelle x
A1 beschreibt die Speicherstelle x
A2 liest die Speicherstelle x
das Ergebnis von A1 wird über die gemeinsam genutzte
Speicherstelle x an A2 kommuniziert
Ergebnis von A1 fließt nach A2 → Flussabhängigkeit
auch echte Datenabhängigkeit (True Dependence)
genannt
die zwei Zugriffe können nicht parallel ausgeführt werden
Gegeben seien zwei Anweisungen A1 und A2, wobei A1 in der
sequentiellen Ausführung vor A2 liege
17. November 2014
32
Flussabhängigkeit (Beseitigung)
for ( i = 0; i < n; i++ ) {
x = x + a[i];
}


A2 hängt vom Ergebnis ab, das in A1 gespeichert wird
 Abhängigkeit kann nicht immer beseitigt werden
hier: Beseitigung durch Reduktion
#pragma omp parallel for reduction(+: x)
for ( i = 0; i < n; i++ ) {
x = x + a[i];
}
17. November 2014
33
Gegenabhängigkeit (Anti Dependence)
for ( i = 0; i < n - 1; i++ ) {
a[i] = a[i+1] + b[i];
}



A1 liest eine Speicherstelle
A2 beschreibt die selbe Speicherstelle anschließend
Gegenteil von Flussabhängigkeit
→ Gegenabhängigkeit
17. November 2014
34
Gegenabhängigkeit (Beseitigung)




Speicheradressen
disjunkt machen
erzeuge temporären
Vektor a2[] und
initialisiere mit
Werten von a[] Initialisierung von
a2[] kann ebenfalls
parallel erfolgen
Overhead:
 Speicher
 Berechnung
for ( i = 0; i < n - 1; i++ ) {
a[i] = a[i+1] + b[i];
}
for ( i = 0; i < n - 1; i++ ) {
a2[i] = a[i+1];
}
for ( i = 0; i < n - 1; i++ ) {
a[i] = a2[i] + b[i];
}
17. November 2014
35
Ausgabeabhängigkeit (Output Dependence)
for
x
d
}
y =




( i = 0; i < n; i++ ) {
= b[i] - c[i];
= 2 * x;
x + d;
A1 und A2 beschreiben die selbe Speicherstelle
Der Schreibzugriff von A2 erfolgt im sequentiellen Programm
nach dem von A1
die Speicherstelle wird lediglich ausgegeben
→ Ausgabeabhängigkeit
hier: Ausgabeabhängigkeit von d und x
17. November 2014
36
Ausgabeabhängigkeit (Beseitigung)
for
x
d
}
y =


( i = 0; i < n; i++ ) {
= b[i] - c[i];
= 2 * x;
x + d;
privatisiere Speicherstelle
kopiere den letzen Wert mit lastprivate zurück auf die
gemeinsame Variable
#pragma
for (
x =
d =
}
y = x
omp parallel lastprivate(x, d)
i = 0; i < n; i++ ) {
b[i] - c[i];
2 * x;
+ d;
17. November 2014
37
Intel Inspector XE



überprüft parallele Anwendungen auf Speicherfehler, DataRaces und Deadlocks
Finden solcher Fehler mit herkömmlichen Methoden
schwierig
unterstützte Betriebssysteme:



Linux (32 bit und 64 bit)
Windows (32 bit und 64 bit)
unterstützte Thread Technologien:




POSIX
OpenMP
Intel Threading Building Blocks (TBB)
WIN32-Threads
Eine parallele Anwendung sollte vor dem Produktiveinsatz immer mit einem solchen Tool überprüft
werden!
17. November 2014
38
Intel Inspector XE: Benutzung (JUDGE)


kann komplett auf Login-Knoten durchgeführt werden
Grafische Benutzerschnittstelle (inspxe-gui) und
Kommandozeilenschnittstelle (inspxe-cl) vorhanden
1. Modul laden:
module load inspector
2. Programm mit Option -g übersetzen
(evtl. Optimierung ausschalten):
icc -openmp -g -O0 -o my_proc my_proc.c
3. Inspector (GUI) starten:
inspxe-gui
Generelle Informationen zum Intel Inspector XE:
module help inspector
17. November 2014
39
Intel Inspector XE: Beispiel (race.c)
#include <stdio.h>
#include <omp.h>
#define SIZE 20
{
int i;
int a[SIZE];
int sum=0;
for (i=0; i<SIZE; ++i)
a[i] = i;
for (i=0; i<SIZE; ++i)
sum = sum + a[i];
printf("Summe:
}
17. November 2014
%d\n",sum);
return 0;
40
Intel Inspector XE – Projekt anlegen (1)
17. November 2014
41
Intel Inspector XE – Projekt anlegen (2)
Sicherstellen, dass
mehrere Threads
verwendet werden

Bei größeren Programmen, möglichst kleine Konfigurationen
verweden, da die Ausführungszeit deutlich (10 – 1000 mal) länger ist
17. November 2014
42
Intel Inspector XE – Analyse konfigurieren
1. Neue Analyse
auswählen
2. Analyse-Typ
wählen
17. November 2014
3. Analyseumfang wählen
(je genauer desto mehr
Overhead)
4. Analyse
starten
43
Intel Inspector XE – Ergebnisse (1)
Doppelklick auf den Fehler öffnet einen Editor mit dem Quelltext
17. November 2014
44
Intel Inspector XE – Ergebnisse (2)
17. November 2014
45
Übung
Übung 11:
Schleifenparallellisierung
17. November 2014
46
OpenMP Teil 3:
Worksharing-Konstrukte
Annika Hagemeier
Inhalt

Aufteilung der Arbeit in parallelen Regionen




Datenumgebung






Parallele Sektion (sections-Direktive)
single-Direktive
copyprivate-Klausel
Verwaiste Konstrukte
threadprivate-Direktive
Grundregeln
Tasks: parallele Aufgaben
Verschachtelte parallele Abschnitte
Parallele Ausführung kontrollieren
18. November 2014
2
Motivation



bislang nur Parallelisierung von Schleifen
 iterative Berechnungen
 relativ einfach zu parallelisieren
außerdem kennen gelernt: parallel-Direktive
 ermöglicht die parallele Ausführung eines beliebigen
Code-Abschnitts
 nicht-iterative, unabhängige Aufgaben
in diesem Kapitel:
 weitere Techniken zur Parallelisierung nicht-iterativer,
unabhängiger Aufgaben
 Techniken zur Aufteilung der Aufgaben auf mehrere
Threads
18. November 2014
3
Aufteilung der Arbeit




Manuelle Aufteilung
 erzeugen einer Kette von Aufgaben, die parallel
abgearbeitet werden können
Aufteilung nach Thread-Nummer
 Anhand ihrer Nummer werden den Threads Aufgaben
zugewiesen
Worksharing Konstrukte
 for
 sections
 single
Task-Konstrukt
 Parallelisierung von Operationen auf komplexen
Datenstrukturen wie Listen und Bäume
18. November 2014
4
Manuelle Aufteilung der Arbeit (1)

gemeinsame Datenstruktur mit einer Liste von Aufgaben

alle Aufgaben können gleichzeitig ausgeführt werden


z. B. Rendern eines Bildausschnitts
Threads eines Teams fordern wiederholt neue Aufgaben an,
bis alle Aufgaben abgearbeitet wurden
int main(int argc, char* argv[]) {
int my_index;
#pragma omp parallel private(my_index)
{
my_index = get_next_task();
while ( my_index != -1 ) {
process_task(my_index);
}
}
}
18. November 2014
5
Manuelle Aufteilung der Arbeit (2)

der Zugriff auf die Aufgabenliste muss synchronisiert
werden, damit jede Aufgabe nur einmal verteilt wird
int index;
int get_next_task() {
#pragma omp critical
if ( index == MAX_INDEX ) {
return -1;
} else {
index++;
return index;
}
}
18. November 2014
6
Aufteilung nach Thread-Nummer

mit Hilfe von Laufzeitroutinen kann jeder Thread seine
eigene Nummer (Id) und die Anzahl der Threads im Team
bestimmen

damit lässt sich die Arbeit in (gleichgroße) Blöcke zerlegen

jedem Thread wird ein Block zugewiesen
#pragma omp parallel private(nthreads, iam, chunk, start, end)
{
nthreads = omp_get_num_threads();
iam
= omp_get_thread_num();
chunk
= (n + (nthreads - 1))/nthreads;
start
= iam * chunk;
end
= n < (iam + 1) * chunk ? n : (iam + 1) * chunk;
for ( i = start; i < end; i++ )
do_work(i);
}
18. November 2014
7

manuelle Aufteilung der Arbeit kann mühsam sein



Implementierung der Berechnungen für die Arbeitsaufteilung
Neuschreiben des Code-Abschnitts
Worksharing-Konstrukte bieten eine automatische
Verteilung der Arbeit

Aufteilung von Schleifeniterationen
⇒ for-Direktive (bereits behandelt)

Aufteilung von unterschiedlichen Code-Abschnitten
⇒ sections-Direktive

Kennzeichnung von Code-Abschnitten, die nur von einem
Thread bearbeitet werden dürfen
⇒ single-Direktive
18. November 2014
8
Grundregeln: Kollektives Ausführen


die Reihenfolge der Worksharing-Konstrukte und barrierDirektiven muss die gleiche sein für jeden Thread
jeder Thread muss an allen Worksharing-Konstrukten
teilnehmen



wenn ein Thread ein Konstrukt erreicht, müssen auch alle
anderen Threads dieses erreichen
wenn ein Thread mehrere Worksharing-Konstrukte in einer
parallelen Region ausführt, müssen alle anderen Threads diese in
der gleichen Reihenfolge ausführen
wenn ein Thread ein Worksharing-Konstrukt überspringt, müssen
auch alle anderen Threads dieses überspringen
{
if (omp_get_thread_num() != 0) /* nicht erlaubt */
#pragma omp for
for (i=0; i<n; i++)
[…];
}
18. November 2014
9
Grundregeln: Schachtelung

Das Schachteln von Worksharing-Konstrukten ist in
OpenMP nicht erlaubt



wenn ein Thread innerhalb eines Worksharing-Konstruktes auf
ein anderes Worksharing-Konstrukt stößt, ist das Verhalten
undefiniert
Parallelisierung von geschachtelten Schleifen möglich
 Iterationen manuell verteilen
 geschachtelte parallele Regionen
keine barrier-Direktive innerhalb von WorksharingKonstrukten
#pragma omp
for (i=0;
{
#pragma omp
for
a
}
18. November 2014
for
i<n; i++)
for
(j=0; j<m; j++)
= […];
/* nicht erlaubt! */
10
Parallele Sektion



enthält Anweisungsblöcke, die parallel zueinander
bearbeitet werden können
Anweisungsblöcke sind unabhängig, d. h. kein Block hängt
von den Ergebnissen eines anderen Blocks ab
jeder Block wird einmal von genau einem Thread des
Teams bearbeitet




dabei ist nicht festgelegt, welcher Thread welchen Block
bearbeitet
eventuell kann sogar ein Thread alle Blöcke bearbeiten
nützlich, wenn einzelne Task zu klein sind um sie effizient zu
parallelisieren
die Ausführungsreihenfolge der Blöcke einer Sektion ist nicht
definiert

OpenMP bietet keine Möglichkeit die Abarbeitungsreihenfolge
der Blöcke zu kontrollieren
18. November 2014
11
Parallele Sektion: Syntax
#pragma omp sections [Klausel[[,] Klausel] ...] new-line
{
[#pragma omp section new-line]
[#pragma omp section new-line
strukturierter Block]
...
}
Klauseln:





private (list)
firstprivate (list)
lastprivate (list)
nowait
18. November 2014
12
Parallele Sektion: Syntax (Kurzform)
#pragma omp parallel sections [Klausel[[,] Klausel] ...] new-line
{
[#pragma omp section new-line]
[#pragma omp section new-line
strukturierter Block]
...
}



genau wie beim Schleifenkonstrukt lassen sich #pragma omp
parallel und #pragma omp sections zu einer Direktive
zusammenfassen
jedoch nur, wenn die parallele Region nur aus einer
parallelen Sektion besteht
alle für parallel und sections gültigen Klauseln sind
erlaubt
18. November 2014
13
Parallele Sektion: Bemerkungen (1)




das gesamte parallele Konstrukt wird von
#pragma omp sections
umschlossen
jede Teilaufgabe wird zu einem Codeblock zusammengefasst und mit
#pragma omp section
umschlossen (ohne “s”)
bei der ersten Teilaufgabe ist die Angabe von #pragma omp
section optional
nowait:


Threads werden am Ende eines parallelen Konstrukts
synchronisiert
nowait verhindert die implizite Synchronisation am Ende der
parallelen Sektion
18. November 2014
14
Parallele Sektion: Bemerkungen (2)

firstprivateVariablen:
werden beim Eintritt in die parallele Region initialisiert (von
jedem Thread)

ein Thread kann mehrere Blöcke einer Sektion bearbeiten
⇒ der Wert einer firstprivate-Variable kann sich vom Wert der
entsprechenden shared-Variable zu Beginn eines Blocks
unterscheiden


lastprivate-Variablen:


der Thread, der den lexikalisch letzten Block ausführt, kopiert
den Wert der Variablen auf die entsprechende shared-Variable
Reduktions-Variablen:

nachdem ein Thread alle ihm zugewiesenen Blöcke abgearbeitet
hat verbindet er seine private Kopie der Variablen mit der
gemeinsamem Kopie
18. November 2014
15
Parallele Sektion: Beispiel
#include <stdio.h>
#define N 100
{
int iam,nthreads;
int i,a[N],b[N];
#pragma omp parallel sections
{
#pragma omp section
for( i=0; i<N; i++ ) {
a[i]=100;
}
#pragma omp section
for( i=0; i<N; i++ ) {
b[i]=200;
}
}
return 0;
}
18. November 2014
16
single-Direktive

innerhalb eines parallelen Abschnitts besteht oftmals die
Notwendigkeit, bestimmte Anweisungen sequentiell
auszuführen, ohne deswegen den parallelen Abschnitt ganz
zu verlassen





z. B. Daten einlesen oder ausgeben
die single-Direktive sorgt dafür, dass der eingeschlossene
Codeblock von genau einem Thread des Teams
durchlaufen wird
der Thread, der den Codeblock durchläuft muss dabei nicht
unbedingt der Master-Thread sein
alle Threads führen eine Barrier-Synchronisation am Ende
des Konstruktes aus, falls nicht nowait angegeben wird
der single-Abschnitt muss folglich von jedem Thread
erreicht werden
18. November 2014
17
single-Direktive: Syntax
#pragma omp single [Klausel[[,] Klausel] ...] new-line
Klauseln:




private (list)
firstprivate (list)
copyprivate (list)
nowait
18. November 2014
18
single-Direktive: Beispiel




beim Erreichen der single-Direktive wird ein beliebiger
Thread ausgewählt, der den Block bearbeitet
die Richtigkeit des Programms darf nicht von der Wahl
eines bestimmten Threads abhängen
die übrigen Threads
warten am Ende des
Blocks, bis der Thread,
der den Block ausführt,
ebenfalls das Ende des
Blocks erreicht hat
wird ein nowait
angegeben, findet keine
Barrier-Synchronisation
am Ende des Blocks statt
18. November 2014
{
#pragma omp for
for(i=0; i<n; i++)
[…]
#pragma omp single
write_intermediate_result();
#pragma omp for
for(i=0; i<n; i++)
[…]
}
19
copyprivate-Klausel



darf nur an eine single-Direktive angehängt werden
kopiert den Wert der privaten Variable(n) des Threads, der
den single-Block ausgeführt hat, auf die privaten Kopien
der anderen Threads im Team (Broadcast)
copyprivate kann also
den Wert einer privaten
Variable nach Ausführung eines singleBlocks den anderen
Threads im Team
mitteilen, ohne dass ein
Umweg über eine
gemeinsam genutzte
Variable genommen
werden muss
18. November 2014
double x;
#pragma omp threadprivate(x)
void init() {
double a;
#pragma omp single copyprivate(a,x)
{
scanf(“%lf”, &a);
scanf(“%lf”, &x);
}
use_values(a,x);
}
20
Warum ist single ein Worksharing-Konstrukt?






der eingeschlossene Codeblock wird nur einmal ausgeführt
vergleichbar mit einer sections-Direktive, die nur einen
Block enthält
muss von allen Threads im Team erreicht werden
jeder Thread muss alle Worksharing-Konstrukte in der
gleichen Reihenfolge erreichen, auch die single-Direktive
implizite Barrier-Synchronisation am Ende des Konstruktes
Barrier-Synchronisation kann durch nowait vermieden
werden
18. November 2014
21
Ausdehnung eines parallelen Konstrukts



Lexikalische Ausdehnung
 alle Statements, die lexikalisch eingeschlossen sind
Dynamische Ausdehnung
 beinhaltet auch Statements in Funktionen, die innerhalb
eines parallelen Konstruktes aufgerufen werden
Verwaiste (engl. orphaned) Direktiven
 Direktiven, die nicht in der lexikalischen, sondern in der
dynamischen Ausdehnung eines Konstruktes liegen
 erlaubt die parallele Ausführung eines Programms mit
minimalen Änderungen der seriellen Version
18. November 2014
22
Datenumgebung




lexikalische oder statische Ausdehnung:
 Quelltext, der lexikalisch eingeschlossen ist
dynamische Ausdehnung:
 lexikalische Umgebung und zusätzlich der Quelltext der
Funktionen die in der lexikalischen Umgebung aufgerufen
werden
lexikalische Ausdehnung ist
eine Teilmenge der
dynamischen Ausdehnung
Datenklauseln (private,
shared, ...) beziehen sich
immer auf die lexikalische
Ausdehnung
18. November 2014
void subroutine();
{
printf(“Hello world!\n”);
}
int main(int argc, char* argv[])
{
{
subroutine();
}
}
23
Verwaiste Worksharing-Konstrukte (1)



können überall in der
dynamischen Umgebung
einer parallelen Region
auftreten
Worksharing-Konstrukte,
die sich nicht in der lexikalischen Umgebung befinden, werden verwaiste
Konstrukte (engl.
orphaned) genannt
Benutzer einer Funktion
sollten sich der Anwesenheit eines WorksharingKonstruktes bewusst sein
18. November 2014
void initialize(double a[], int
n) {
int i;
#pragma omp for
for (i=0; i<n; i++)
a[i] = 0.0;
}
int main(int argc, char* argv[])
{
{
initialize(a,n);
[…]
}
}
24
Verwaiste Worksharing-Konstrukte (2)
Aufruf innerhalb einer parallelen Region:
 fast das gleiche Verhalten als läge das Konstrukt in der
lexikalischen Umgebung
 geringe Unterschiede bestehen lediglich in der Bindung
der Daten
Aufruf innerhalb eines seriellen Programmteils:
 fast das gleiche Verhalten als gäbe es keine WorksharingDirektive
 ein serieller Thread verhält sich wie ein paralleles Team
bestehend aus nur einem Master Thread
 kann gefahrlos aus seriellem Code aufgerufen werden
(Direktive wird ignoriert)
 geringe Unterschiede bestehen lediglich in der Bindung
der Daten
18. November 2014
25
Verwaiste Konstrukte: Datenumgebung




Datenklauseln einer parallelen Region beziehen sich nur auf
die lexikalische Umgebung
globale Variablen (C/C++) und Variablen in commonBlöcken (Fortran) sind standardmäßig gemeinsam
unabhängig von den Datenklauseln der einschließenden
parallelen Region
automatische Variablen der Funktion, die das verwaiste
Konstrukt enthält sind immer privat
Parameter der Funktion, die das verwaiste Konstrukt
enthält haben die Bindung, die der entsprechenden Variablen
vor Funktionsaufruf zugewiesen wurde
18. November 2014
26
Datenumgebung: Beispiel (1)

my_start und my_end sind nicht private in work()
int my_start, my_end;
void work() {
/* my_start and my_end are undefined */
printf("My subarray is from %d to %d\n",
my_start, my_end);
}
#pragma omp parallel private(my_start, my_end)
{
/* get subarray indices */
my_start = get_my_start(omp_get_thread_num(),
omp_get_num_threads());
my_end
= get_my_end(omp_get_thread_num(),
omp_get_num_threads());
work();
}
}
18. November 2014
27
Datenumgebung: Beispiel (2)


Lösung: Variablen als Parameter übergeben
⇒ lästig für lange Parameterlisten
bessere Lösung: threadprivate-Direktive
void work(int my_start, int my_end) {
my_start, my_end);
}
#pragma omp parallel private(my_start, my_end)
{
my_start = […]
my_end
= […]
work(my_start, my_end);
}
}
18. November 2014
28
threadprivate-Direktive (1)

my_start und my_end sind jetzt auch in work() private
#pragma omp threadprivate(my_start, my_end)
void work() {
my_start, my_end);
}
{
my_start = […]
my_end
= […]
work();
}
}
18. November 2014
29
threadprivate-Direktive (2)







deklariert eine Variable für einen Thread als private für das
gesamte Programm
die Variable wird einmal zu einem unspezifizierten Zeitpunkt
im Programm initialisiert, jedoch bevor eine Kopie der
Variablen zum ersten Mal referenziert wird
der Wert der Variablen bleibt über mehrere parallele
Regionen hinaus erhalten, solange die Anzahl der Threads
konstant bleibt
Threads mit der gleichen Thread-Nummer erhalten
dieselbe Kopie der Variablen
threadprivate-Variablen dürfen in keiner Daten-Parameterliste erscheinen, ausgenommen copyin und copyprivate
die threadprivate-Direktive darf erst nach der Deklaration
der Variablen angewendet werden
es gelten noch einige andere Einschränkungen (siehe
Spezifikation)
18. November 2014
30
copyin-Klausel

jeder Thread hat seine eigene Kopie von threadprivateVariablen während der gesamten Programmlaufzeit



ein Thread hat nicht die Möglichkeit auf die private Kopie eines
anderen Thread zuzugreifen
die copyin-Klausel kopiert den Wert vom Master Thread auf die
private Kopie jedes Threads, der in die parallele Region eintritt
Variablen in der copyin-Klausel müssen threadprivateVariablen sein
int c;
#pragma omp threadprivate(c)
c = 2;
#pragma omp parallel copyin(c)
{
/* c has value 2 in all thread-private copies */
[…] = c;
}
}
18. November 2014
31
Tasks in OpenMP
Motivation:


Parallelisierung von Operationen auf komplexeren
Datenstrukturen wie Listen und Bäumen in OpenMP
grundsätzlich möglich
erfordert aber meist umfangreiche Änderungen im Code
⇒ entspricht jedoch nicht dem Prinzip der inkrementellen
Parallelisierung
⇒ meist mit sehr hohem Verwaltungsaufwand zur
Laufzeit verbunden
Tasks in OpenMP:


Tasks in OpenMP dienen der Parallelisierung irregulärer
Daten- und Kontrollstrukturen
erst seit OpenMP 3.0 Teil des Standards
18. November 2014
32
Tasks



Task = Codeblock, dessen Anweisungen unabhängig sind
und sequentiell abgearbeitet werden (vgl. sections)
direkte oder verschobene Ausführung der Arbeit von
einem Thread des Teams
ein Task besteht aus:





einem Codeblock der ausgeführt werden soll
der entsprechenden Datenumgebung
internen Kontrollvariablen
kann an einen bestimmten Thread gebunden werden (nur
dieser Thread kann den Task ausführen
nützlich zur Parallelisierung von



while-Schleifen
rekursiven Algorithmen
Operationen auf komplexeren Datenstrukturen, wie Listen oder
Bäumen
18. November 2014
33
Tasks: Syntax
#pragma omp task [Klausel[[,] Klausel] ...] new-line
{
}
Klauseln:









final (scalar-expression)
untied
mergeable
private (list)
firstprivate (list)
shared (list)
4.0 depend (dependence-type: list)
18. November 2014
34
Tasks: Datenumgebung

Es gelten die allgemeinen impliziten Regeln:




C/C++
Schleifenvariablen eines for oder parallel for-Konstruktes sind
private
Automatische Variablen, die innerhalb eines Konstruktes
deklariert werden sind private
Globale und statische Variablen sind shared
Ist die Bindung der Daten nicht explizit (durch Klauseln)
bestimmt, gilt außerdem:
Variablen in verwaisten task-Konstrukten sind firstprivate

Variablen in nicht-verwaisten task-Konstrukten erben das
shared-Attribut aus dem umgebenen Kontext
⇒ Variablen sind firstprivate, falls sie nicht das shared-Attribut
erben

Tipp: Bei Unsicherheit default(none) verwenden und alle
Bindungen explizit setzen!
18. November 2014
37
Datenumgebung: Beispiel
int a;
void bar(int f, int g) {
#pragma omp task
{
f = ?;
g = ?;
}
}
void foo() {
int b, c, g;
#pragma omp parallel private(b) shared(g)
{
int d, f;
bar(f, g);
#pragma omp task
{
int e;
a
b
c
d
e
=
=
=
=
=
?;
?;
?;
?;
?;
}}}
18. November 2014
38
Datenumgebung: Beispiel (Lösung)
int a;

gem
void bar(int f, int g) {
#pragma omp task
{
f = firstprivate;
g = firstprivate;
}
}
void foo() {
int b, c, g;
#pragma omp parallel private(b) shared(g)
{
int d, f;
bar(f, g);
#pragma omp task
{
int e;
a
b
c
d
e
=
=
=
=
=
shared;
firstprivate;
shared;
firstprivate;
private;
}}}
18. November 2014
39
Task-Typen (1)



Tied Task (tied = gebunden):
Task, dessen Ausführung nur von dem Thread wieder
aufgenommen werden kann, der sie auch zurückgestellt hat
⇒ der Task ist an einen Thread gebunden
Untied Task (untied = ungebunden):
Task, dessen Ausführung verschoben wurde, kann von
jedem beliebigen Thread wieder aufgenommen werden
⇒ der Task ist an keinen Thread gebunden
Undeferred Task (undeferred = nicht aufgeschoben):
Task, dessen Ausführung nicht verschoben wird (im Hinblick
auf den generierenden Task) der generierende Task ist
verschoben, solange bis der Undeferred Task ausgeführt
wurde
⇒ die Ausführung des Tasks darf nicht verschoben werden
18. November 2014
40
Task-Typen (2)



Included Task (included = eingeschlossen):
Task, dessen Ausführung sequentiell in den generierenden
Task eingeschlossen ist
der Task ist undeferred und wird direkt vom ankommenden
Thread ausgeführt
Merged Task (merged = vermischt):
Task, dessen Datenumgebung, einschließlich der ICVs
(Internal Control Variables), mit der des generierenden Tasks
übereinstimmt
Final Task (final = letzter):
Task, der alle Kind-Tasks dazu zwingt, final und included zu
sein, d.h. es werden keine neuen eigenständigen (mit
eigener Datenumgebung) Tasks mehr erzeugt
18. November 2014
41
Klauseln der task-Direktive (1)


if (Bedingung)
 ist die Bedingung false, so muss der Thread sofort mit
der Ausführung des neuen Tasks beginnen
 führt er bereits einen anderen Task aus, so wird dessen
Ausführung ausgesetzt und erst wieder aufgenommen,
wenn die Ausführung des inneren Tasks beendet ist
untied
 kontrolliert, welche Threads die Ausführung eines
ruhenden Tasks an einem Scheduling-Punkt wieder
aufnehmen dürfen
 normalerweise wird ein verschobener Task von dem
Thread fortgeführt, der ihn gestartet hat
 mit der Option untied kann jeder andere Thread mit der
Ausführung nach einer Aufschiebung des Tasks fortfahren
18. November 2014
42


final (Bedingung)
 ist die Bedingung true, so ist der erzeugte Task ein Final
Task
 alle Task-Konstrukte, die währen der Ausführung eines
Final Tasks erreicht werden, erzeugen Final Tasks oder
Included Tasks
⇒ es werden keine neuen eigenständigen (mit eigener
Datenumgebung) Tasks mehr erzeugt
mergeable
 ist die mergeable-Klausel angegeben und ist der
generierte Task ein Undeferred oder Included Task, dann
kann ein Merged Task erzeugt werden, anstatt eines
eigentständigen Tasks
Ziel: Vermeidung von Overhead durch Datenumgebungen
18. November 2014
43

4.0
depend (dependence-type : list)
 Definiert Abhängigkeiten zwischen Geschwister-Tasks

dependence-type ist entweder in, out oder inout und
list ist eine Liste von Variablen:


in: der generierte Task hängt von allen vorher generierten
Geschwister-Tasks ab, die eine der Variablen in einer out
oder inout-Klausel referenzieren
out oder inout: der generierte Task hängt von allen vorher
generierten Geschwister-Tasks ab, die eine der Variablen in
einer in, out oder inout-Klausel referenzieren
Beispiel:
#pragma omp task depend (out: a)
{...}
#pragma omp task depend (out: b)
{...}
#pragma omp task depend (in: a,b)
{...}
18. November 2014


die ersten beiden Tasks können
parallel ausgeführt werden
der dritte Task kann erst starten,
wenn Ausführung der ersten
beiden Tasks abgeschlossen ist
44
Tasks: Regeln







trifft ein Thread auf ein task-Konstrukt, so wird ein Task des
Codeblocks erzeugt
der Thread kann den Task sofort selbst ausführen oder
seine Ausführung verschieben
bei Verschieben des Task, wird dieser später durch einen
beliebigen Thread aus dem Team ausgeführt
die Daten-Umgebung eines Tasks wird entsprechend der
Data-Sharing Parameter angelegt
an Scheduling-Punkten im Programm kann ein Thread die
Ausführung eines Tasks A unterbrechen und stattdessen
einen anderen Task B ausführen
zur Sicherstellung, dass Tasks ausgeführt wurden muss
synchronisiert werden (taskwait)
Task-Direktiven können geschachtelt werden

der innen liegende Task zählt nicht als Teil des äußeren Task,
sondern wird als Kind-Task (oder Child-Task) bezeichnet
18. November 2014
45
Tasks: Taskwait
#pragma omp taskwait new-line




ähnliche Bedeutung wie eine Barrier-Synchronisation
wartet auf die Fertigstellung von Kind-Tasks, die seit dem
Beginn des aktuellen Tasks generiert wurden
die Ausführung der aktuellen Task-Region (über den mit
taskwait markierten Punkt hinaus) wird solange
ausgesetzen, bis die Ausführung aller Kind-Tasks beendet ist
ist ein impliziter Task-Scheduling-Punkt in der aktuellen TaskRegion
18. November 2014
46
4.0
Tasks: Taskgroup
#pragma omp taskgroup new-line
{
}




ähnliche Bedeutung wie taskwait
wartet auf die Fertigstellung von Kind-Tasks und
Geschwister-Tasks, die seit dem Beginn des aktuellen
Tasks generiert wurden
die Ausführung der aktuellen Task-Region (über den mit
taskwait markierten Punkt hinaus) wird solange
ausgesetzen, bis die Ausführung aller Kind- und GeschwisterTasks beendet ist
Unterschied zu taskwait: taskwait wartet nur auf KindTasks
18. November 2014
47
Tasks: Taskyield
#pragma omp taskyield new-line


Spezifiziert, dass die Ausführung des aktuellen Tasks
zugunsten eines anderen Tasks verschoben werden kann
Einschränkungen bzgl. der Plazierung im Programm:
 Darf nur an Stellen verwendet werden, an denen
Statements der Basissprache erlaubt sind
 Darf nicht vor einem if, while, do, switch oder label
verwendet werden
18. November 2014
48
Task Scheduling


wann immer ein Thread einen Task-Scheduling-Punkt
erreicht, kann er einen Task-Switch (Wechsel des gerade
ausgeführten Tasks) durchführen:
 Starten der Ausführung eines neuen Tasks
 Wiederaufnahme eines anderen Tasks
Task-Scheduling-Punkte:
 Eintreten in eine Task-Region (direkt nach Generierung
eines neuen Tasks)
 nach Abarbeitung der letzten Instruktion einer TaskRegion (nach Beendigung eines Tasks)
 jeder Punkt innerhalb eines Tasks mit der untied-Klausel
 taskwait-Direktiven
 implizite und explizite Barrieren
18. November 2014
49
Tasks: Unterschiede
Tasks unterscheiden sich von anderen parallelen Konstrukten
(sections, parallel, for, ...):

Tasks sind für die Dauer ihrer Ausführung nicht an genau
einen ausführenden Thread gebunden


ein Task kann zu verschiedenen Zeitpunkten von
verschiedenen Threads ausgeführt werden
jeder Task hat seinen eigenen privaten Datenbereich


führt ein Thread einen Task aus, so geschieht das unter
Verwendung des Datenbereichs des Tasks (nicht im
Datenbereich des Threads)
der Inhalt des Task-Datenbereichs bleibt bis zur
Beendigung des Tasks erhalten
18. November 2014
50
Tasks: Beispiel Baumtraversierung
struct node {
struct node *left;
struct node *right;
};
extern void process(struct node *);
void traverse( struct node *p ) {
if (p->left)
#pragma omp task
/* p is firstprivate by default */
traverse(p->left);
if (p->right)
#pragma omp task
traverse(p->right);
process(p);
}
int main (void){
...
{
#pragma omp single
traverse(p);
}
...
}
18. November 2014
51
Tasks: Beispiel Baumtraversierung (Postorder)
struct node {
struct node *left;
struct node *right;
};
extern void process(struct node *);
void traverse( struct node *p ) {
if (p->left)
#pragma omp task
traverse(p->left);
if (p->right)
#pragma omp task
traverse(p->right);
#pragma omp taskwait
process(p);
}
int main (void){
...
{
#pragma omp single
traverse(p);
}
...
}
18. November 2014
52
Geschachtelte Parallele Regionen (1)


haben bis jetzt nur Worksharing-Konstrukte innerhalb
paralleler Regionen betrachtet
OpenMP erlaubt auch mehrere parallele Abschnitte
ineinander zu verschachteln (engl. nested parallelism)



wird ein paralleler Abschnitt von einem Team von Threads
ausgeführt, so können die Threads wiederum auf ein #pragma
omp parallel stoßen
in diesem Fall, wird für jeden Thread, der die innere parallele
Region erreicht ein neues Team von Threads gestartet, das den
inneren parallelen Abschnitt
ausführt
{
standardmäßig wird die Aussome_work();
führung der inneren parallelen
{
Region serialisiert
some_other_work();
⇒ das Team enthält nur einen
}
}
Thread mit Nummer 0 (Master
Thread)
18. November 2014
53
Bindung:
 alle Worksharing-Konstrukte beziehen sich auf die nächste
einschließende parallele Direktive
 die Synchronisations-Konstrukte barrier and master beziehen sich auf die nächste einschließende parallele Direktive
Funktionen:
 omp_set_nested (int nested)


nested = 0: die verschachtelte parallele Region wird serialisiert
und mit nur einem Thread ausgeführt
nested ≠ 0: mehr als ein Thread kann zur Bearbeitung der
parallelen Region erzeugt werden



Anzahl der Threads abhängig von der Implementierung
parallele Region kann immer noch serialisiert werden
omp_get_nested ()

liefert den Wert von nested zurück
18. November 2014
54
Umgebungsvariable:

export OMP_NESTED=TRUE/FALSE
Abfragefunktionen:
 omp_get_level()


omp_ancestor_thread_num(level)


gibt zur Schachtelungstiefe level des aktuellen Threads die
Thread-ID des Vorfahren oder des aktuellen Threads zurück
omp_get_team_size(level)


gibt die Anzahl der geschachtelten parallelen Regionen zurück, in
der sich der aufrufende Thread befindet
gibt zur Schachtelungstiefe level die Größe des Teams zurück,
zu dem der aktuelle Thread selbst oder sein Vorfahr gehört
omp_get_active_level()

gibt die Anzahl der aktiven geschachtelten parallelen Regionen
zurück, in der sich der aufrufende Thread befindet
18. November 2014
55
Geschachtelte Parallele Regionen: Beispiel
void process_task(int k) {
int i;
for (i=0; i<n; i++)
a[k][i] = 3.0;
}
int my_index;
#pragma omp parallel private(my_index)
{
while ( my_index != -1 ) {
process_task(my_index);
}
}
}
18. November 2014
56
Übung
Übung 12:
18. November 2014
57
OpenMP Teil 4:
Synchronisation
Annika Hagemeier
Inhalt



Data Races
Synchronisationsarten
 Gegenseitiges Ausschließen
 Kritische Region (critical)
 Atomare Anweisung (atomic)
 Locks
 Sychronisation von Ereignissen
 Barrieren (barrier)
 Geordnete Ausführung (ordered)
 master-Direktive
 Sychronisation über Speicherstellen (flush)
Effiziente Parallelisierung
 Tipps zur effizienten Parallelisierung
18. November 2014
Synchronisation
2
Wettlaufsituationen (Race Condition)
wird eine Aufgabe von mehreren Threads gemeinsam
bearbeitet, kann es der Fall sein, dass sie sich in ihrer
Ausführung gegenseitig beeinflussen
 im Kontext von OpenMP nutzen alle Threads im Team einen
gemeinsamen Adressraum
 die Kommunikation zwischen den Threads erfolgt durch Lesen
und Schreiben gemeinsam genutzter Variablen
 die Reihenfolge von parallel ausgeführten Anweisungen ist
nicht garantiert
 um die gemeinsam genutzten Daten dennoch konsistent zu
halten, werden OpenMP-Sprachkonstrukte zur
Synchronisierung benötigt
Eine Situation, in der mehrere Threads auf gemeinsam genutzte
Daten zugreifen und das Ergebnis der Berechnung von der
jeweiligen Ausführungsreihenfolge abhängt heißt
Wettlaufsituation oder Race Condition.

18. November 2014
Synchronisation
3
Beispiel: Wettlaufsituation
Aufgabe: Finde das größte Element in einer Liste
cur_max = MINUS_INFINITY;
for ( i = 0; i < n; i++ )
if ( a[i] > cur_max )
cur_max = a[i];
Die obige parallele Version kann falsche Ergebnisse liefern:
Thread 0:
Thread 1:
read a[i]
(12)
read cur_max
(10)
if (a[i] > cur_max) (12 > 10)
cur_max = a[i]
(12)
read a[j]
read cur_max
(11)
(10)
if (a[j] > cur_max) (11 > 10)
cur_max = a[j]
(11)
18. November 2014
Synchronisation
4
Synchronisation (1)

Kommunikation in Shared-Memory-Programmen implizit



Kommunikation = read/write-Operationen auf Variablen im
gemeinsamen Adressbereich
implizite Kommunikation bedarf Koordination ⇒
Synchronization
Synchronisation in OpenMP:
gegenseitiges Ausschließen:

kritische Section

atomare Anweisungen

Lock-Routinen
• Event-Synchronisation
 Barrieren
 ordered
 master
 flush
 taskwait

18. November 2014
Synchronisation
5
Synchronisation (2)

gegenseitiges Ausschließen
 exklusiver Zugriff auf eine gemeinsame Variable
 kann verwendet werden zur Sicherstellung, dass
1. innerhalb des Synchronisationskonstrukts nur ein Thread
Zugriff auf die Variable hat
2. Zugriffe mehrerer Threads in der Granularität des
Synchronisationskonstruktes verschachtelt werden

Synchronisation von Ereignissen
 signalisiert einem Thread die Fertigstellung von
Ereignissen eines anderen Threads
 Synchronization von Ereignissen kann verwendet werden
um die Reihenfolge der Threads zu regeln
 durch gegenseitiges Ausschließen lässt sich die
Zugriffsreihenfolge nicht regeln
18. November 2014
Synchronisation
6
Kritische Abschnitte

um eine Wettlaufsituation zu vermeiden, muss sichergestellt
werden, dass immer nur ein Thread den Wert der Variablen
cur_max verändern kann
⇒ Synchronisation des Zugriffs
Kritische Abschnitte:
 für parallel laufende Threads müssen also diejenigen
Codeabschnitte identifiziert werden, in denen ein Thread
exklusiven Zugriff auf gemeinsam genutzte Daten haben
muss
 diese Abschnitte werden kritische Abschnitte genannt
 wenn ein Thread einen kritischen Abschnitt ausführt, darf kein
anderer Thread diesen kritischen Abschnitt ausführen
18. November 2014
Synchronisation
7
Kritische Region
#pragma omp critical [(name)] new-line
{
}


OpenMP setzt das Konzept des kritischen Abschnitts direkt in ein
Pragma um
die critical-Direktive markiert den folgenden Block als
kritischen Abschnitt:




der Block wird zu jedem Zeitpunkt von höchstens einem Thread
ausgeführt
weitere Threads blockieren am Anfang des Blocks
alle mit critical gekennzeichneten Codeabschnitte im Programm werden wie ein einziger kritischer Abschnitt behandelt
⇒ Threads an verschiedenen Stellen im Programm warten
unnötigerweise aufeinander
feinere Granularität: kritische Regionen mit Namen versehen
⇒ Regionen mit unterschiedlichen Namen können parallel
ausgeführt werden
18. November 2014
Synchronisation
8
Beispiel: Wettlaufsituation (Lösung)
Aufgabe: Finde das größte
Element in einer Liste
for ( i = 0; i < n; i++ )
cur_max = a[i];
Erste Lösung:
Bessere Lösung:
for ( i = 0; i < n; i++ ){
{
cur_max = a[i];
}
}
for ( i = 0; i < n; i++ ){
if( a[i] > cur_max)
{
cur_max = a[i];
}
}
18. November 2014
Synchronisation
9
Beispiel: kritische Region mit Namen
cur_min = PLUS_INFINITY;
for ( i = 0; i < n; i++ ) {
#pragma omp critical (MAX_LOCK)
{
cur_max = a[i];
}
if ( a[i] < cur_min )
#pragma omp critical (MIN_LOCK)
{
if ( a[i] < cur_min )
cur_min = a[i];
}
}
18. November 2014
Synchronisation
10
Atomare Anweisung





atomare Anweisungen sind nützlich, wenn man ein Datum
exklusiv aktualisieren möchte
zwischen dem Lese- und anschließenden Schreibzugriff darf
kein anderer Thread auf dieses Datum schreibend zugreifen
statt eines kompletten Codeabschnitts wie bei critical wird
hier nur eine einzelne Speicherstelle vor unerlaubtem
Parallelzugriff geschützt
Vorteil:
 geringerer Verwaltungsaufwand zur Synchronisation der
Threads
⇒ in den meisten Fällen hat eine atomare Anweisung Laufzeitvorteile gegebenüber einem kritischen Abschnitt
Nachteil:
 nur bei bestimmten Operationen auf dieser Speicherstelle
möglich
18. November 2014
Synchronisation
11
Atomare Anweisung: Syntax (1)
C/C++
#pragma omp atomic [read | write | update | capture] \
[seq_cst] new-line
Zuweisung
die Zuweisung, auf die sich die atomic-Direktive bezieht, muss
die Anwendung eines Inkrement- oder Zuweisungsoperators auf
einer skalaren Variable x oder v sein:






x und v sind skalare
l-value Ausdrücke
expr ist ein skalarer
Ausdruck
binop ist folgendes:
+, , *, /, &, ^, |, <<, >>
v und expr dürfen
nicht auf x zugreifen
x und expr dürfen
nicht auf v zugreifen
18. November 2014
Klausel
erlaubte Zuweisung
read
write
update
oder keine
Klausel
capture
v = x;
x = expr;
x++; ++x; x--; --x;
x binop = expr;
x = x binop expr;
v = x++; v = ++x;
v = x--; v = --x;
v = x binop= expr;
seq_cst
bewirkt einen impliziten Flush
Synchronisation
12
Atomare Anweisung: Syntax (2)
C/C++
#pragma omp atomic capture [seq_cst] new-line
die Zuweisung, auf die sich die atomic-Direktive bezieht, muss
die Anwendung eines Inkrement- oder Zuweisungsoperators auf
einer skalaren Variable x oder v sein:






x und v sind skalare
l-value Ausdrücke
expr ist ein skalarer
Ausdruck
binop ist folgendes:
+, , *, /, &, ^, |, <<, >>
v und expr dürfen
nicht auf x zugreifen
x und expr dürfen
nicht auf v zugreifen
18. November 2014
erlaubte strukturierte Blöcke
{v = x; x binop= expr;}
{x binop= expr; v = x;}
{v = x; x = x binop expr;}
{x = x binop expr; v = x;}
{v = x; x++;}{v = x; ++x;}
{x++; v = x;}{++x; v = x;}
{v = x; x--;}{v = x; --x;}
{x--; v = x;}{--x; v = x;}
Synchronisation
13
Locks








Eine Art „kritische Region“ auf Daten
Jede Lock-Variable kann nur von einem Thread zu einem
Zeitpunkt belegt sein
Lock-Variablen müssen vom Typ omp_lock_t sein
auf Lock-Variablen kann nur mit entsprechenden Routinen
zugegriffen werden
ein OpenMP-Lock kann einen der folgenden Zustände haben:
uninitialized, unlocked, locked
es gibt zwei Arten von Locks:
 einfache Locks
 ineinander schachtelbare (nestable) Locks
einfache Locks: können nur einmal von einem Thread
gesetzt werden
schachtelbare Locks: können mehrfach von dem selben
Thread gesetzt werden, bevor sie wieder deaktiviert werden
18. November 2014
Synchronisation
14
Funktionen für einfache Locks
void omp_init_lock(omp_lock_t *lockvar);

einen einfachen Lock initialisieren
void omp_destroy_lock(omp_lock_t *lockvar);

einen Lock löschen (Status des Locks wird auf uninitialized
gesetzt)
void omp_set_lock(omp_lock_t *lockvar);

einen Lock sperren (Thread blockiert solange, bis er den
Lock bekommt, bzw. der Lock gesetzt ist)
void omp_unset_lock(omp_lock_t *lockvar);

einen Lock entsperren
void omp_test_lock(omp_lock_t *lockvar);
Lock testen und setzen (liefert TRUE, wenn Lock gesetzt
werden konnte)
Funktionen für geschachtelte Locks sind analog,
werden hier jedoch nicht weiter behandelt !

18. November 2014
Synchronisation
15
Beispiel: Lock
omp_lock_t lock;
omp_init_lock(&lock);
for ( i = 0; i < n; i++ ) {
{
omp_set_lock(&lock);
cur_max = a[i];
omp_unset_lock(&lock);
}
}
omp_destroy_lock(&lock);
18. November 2014
Synchronisation
16
Beispiel: Lock
omp_lock_t lock;
omp_init_lock(&lock);
for ( i = 0; i < n; i++ ) {
{
while (!omp_test_lock(&lock))
do_work();
cur_max = a[i];
omp_unset_lock(&lock);
}
}
omp_destroy_lock(&lock);
18. November 2014
Synchronisation
17
C/C++
Barrieren: Syntax
#pragma omp barrier new-line



implizite Barrieren: am Ende eines parallelen Abschnitts
warten alle Threads bis alle den parallelen Abschnitt
durchlaufen haben (wenn der Abschnitt nicht mit einer
nowait-Direktive versehen ist)
mit Hilfe der barrier-Direktive kann der Programmierer
Barrieren explizit an notwendigen Stellen im Programm
einfügen
Vorsicht: Barrieren sollten jedoch nur sparsam verwendet
werden, da sie die Performance negativ beeinflussen
18. November 2014
Synchronisation
18
Geordnete Ausführung: Syntax
C/C++
#pragma omp ordered new-line


manchmal kann es notwendig sein, dass innerhalb einer
parallel ausgeführten Schleife ein Stück Code in der
Reihenfolge ausgeführt werden muss, die der sequentiellen
Ausführung der Schleife entspricht, ohne dass man
deswegen den parallelen Abschnitt verlassen möchte oder
kann.
sollen Teile einer parallelen Schleife geordnet ausgeführt werden, so muss
das Schlüsselwort ordered
sowohl als Klausel als
auch als Direktive
eingefügt werden
18. November 2014
/* ordered als Klausel */
#pragma omp parallel for ordered
for ( i=0; i<n; i++ ) {
a[i] = f(i);
/* ordered als Direktive */
#pragma omp ordered
printf("a[%d] = %d", i, a[i]);
}
Synchronisation
19
C/C++
master-Direktive
#pragma omp master new-line


mit Hilfe der master-Direktive lässt sich genau spezifizieren,
welcher Thread den entsprechenden Abschnitt alleine
ausführen soll: der Master-Thread
in einem master-Abschnitt können z. B. Zwischenergebnisse
aus einer vorhergehenden parallelen Berechnung sequentiell
ausgegeben werden

zu beachten ist jedoch, dass diese Zwischenergebnisse
möglicherweise bereits weiter modifiziert wurden bevor der
Master-Thread die Ausgabe beendet hat, da die anderen
Threads nicht am Ende des Abschnitts auf den Master-Thread
warten
18. November 2014
Synchronisation
20
Unterschiede master und single



die single-Direktive stellt nur sicher, dass genau ein Thread
den Abschnitt ausführt, jedoch nicht welcher
mit Hilfe der master-Direktive lässt sich spezifizieren, dass
der Master-Thread den Abschnitt alleine ausführen soll
am Ende eines master-Abschnitts befindet sich keine
implizite Barriere


andere Threads können also einfach den master-Abschnitt
überspringen und den nachfolgenden Code ausführen
ein master-Abschnitt muss für die anderen Threads nicht
unbedingt erreichbar sein
18. November 2014
Synchronisation
21
Synchronisation über Speicherstellen




Register, Caches etc. können Daten puffern, wodurch in
einem Multiprozessorsystem Kohärenzprobleme auftreten
können
das OpenMP-Speichermodell besitzt eine gelockerte Kohärenz
⇒ der lokale Pufferspeicher eines Threads muss nicht zu
jedem Zeitpunkt kohärent mit dem Hauptspeicher sein
Beispiele:
 ein Wert, der einer Variablen zugewiesen wird, kann im
lokalen Pufferspeicher eines Threads verbleiben bis ein
Schreiben in den Hauptspeicher erzwungen wird
 das Lesen einer Variablen kann vom lokalen
Pufferspeicher eines Threads erfolgen solange nicht ein
Lesen vom Hauptspeicher erzwungen wird
ein typisches Beispiel, wo dies Probleme verursachen kann, ist
die Synchronisation von Threads über Speicherstellen
18. November 2014
Synchronisation
22
Die flush-Direktive: Syntax
C/C++
#pragma omp flush [(Liste von Variablen)]





Die flush-Direktive stellt einen Synchronisationspunkt für
Speicherbereiche dar.
Die flush-Direktive sorgt dafür, daß lokale Pufferspeicher
mit dem Hauptspeicher abgeglichen werden. Dies ist sowohl
bei dem schreibenden als auch lesenden Thread nötig.
In der Variablenliste sind nur gemeinsame Variablen
möglich. Fehlt die Angabe der Variablenliste, werden alle
gemeinsamen Variablen abgeglichen.
Eine flush-Operation begrenzt die Umsortierung von
Speicheroperationen durch den Compiler.
Ein Flush geschieht implizit bei folgenden Direktiven, falls
kein nowait angegeben wird: barrier, critical, end critical, enddo, end parallel, end sections, end
single, ordered, end ordered
18. November 2014
Synchronisation
23
Die flush-Direktive


Durchführung eines flush garantiert folgendes:
 eine flush-Operation ist erst dann beendet, wenn der Wert
der Variablen in den Hauptspeicher geschrieben wurde
 die lokale Kopie der Variablen wird verworfen, die Variable
muss beim nächsten Zugriff aus dem Hauptspeicher
gelesen werden
 spätere Speicheroperationen des Threads, die diese
Variable betreffen, dürfen erst starten, wenn die flushOperation beendet wurde
die flush-Direktive kann verwendet werden zur Sicherstellung
dass ein Wert der einer Variablen von einem Thread zugewiesen wurde von einem anderen Thread gelesen werden kann:
1)
2)
3)
4)
Der erste Thread schreibt einen Wert auf die Variable
Die Variable wird vom ersten Thread geflusht
Die Variable wird vom zweiten Thread geflusht
Der zweite Thread liest die Variable
18. November 2014
Synchronisation
24
Effiziente Parallelisierung



Letztlich entscheidet die Effizienz einer Parallelisierung
darüber, ob sich der zusätzliche Aufwand bei der
Programmierung gelohnt hat.
Obwohl OpenMP einer der einfachsten Möglichkeiten
darstellt, durch inkrementelles Vorgehen Schritt für Schritt
ohne komplette Neustrukturierung des Codes ein Programm
zu parallelisieren, zeigt sich in der Praxis, dass die effiziente
Parallelisierung ein nichttriviales Unterfangen ist.
Gerade beim Einstieg in OpenMP sind die Ergebnisse oft
ernüchternd: Das parallelisierte Programm läuft um ein
Vielfaches langsamer als das sequentielle.


der zusätzliche Verwaltungsaufwand für mehrere Threads frist
die durch die Parallelisierung erreichbare Beschleunigung
eine parallele Ausführung lohnt sich erst ab eine gewissen
Problemgröße
Das Ziel einer Parallelisierung ist immer ein
skalierbares Programm!
18. November 2014
Synchronisation
26
Tipps zur effizienten Parallelisierung (1)

Die Gesamtanzahl paralleler Abschnitte minimieren:




das Starten und Beenden von Threads bei jedem Eintreten und
Verlassen von parallelen Abschnitten ist mit nicht zu vernachlässigendem Verwaltungsaufwand verbunden
im Falle von parallelen Schleifen kommt noch zusätzlicher
Aufwand für die Zuweisung von Iterationen an Threads hinzu
oft können zwei parallele Abschnitte durch einen single- oder
master-Block zusammengefasst werden
Verschachtelte Schleifen so weit außen wie möglich
parallelisieren:


bei verschachtelten Schleifen sollte nach Möglichkeit (wenn
keine Datenabhängigkeiten dagegen sprechen) die äußerste
Schleife parallelisiert werden
Grund: innen liegende parallele Abschnitte werden in jeder
Iteration einer weiter außen liegenden Schleife betreten und
verlassen ⇒ Multiplikation des Verwaltungsaufwands
18. November 2014
Synchronisation
27

Kritische Abschnitte möglichst sparsam verwenden:




viele kritische Abschnitte erhöhen den sequentiellen Teil eines
Programms ⇒ Performancelimitierung (Amdahl'sches Gesetz)
manchmal kann es vorteilhaft sein, mit Lock-Funktionen eine
exaktere Synchronisation auf gemeinsam genutzte Ressourcen
zu implementieren
alternativ kann man gemeinsam genutzte Ressourcen jedem
Thread als private Kopie mitgeben und am Ende die Ergebnisse
zusammenfassen
Kritische Abschnitte mit Namen versehen:



der für die Korrektheit notwendige Synchronisationsaufwand
lässt sich nicht umgehen
umso wichtiger ist es, dass Threads nicht unnötig an nicht oder
gleich benannten kritischen Abschnitten aufeinander warten
müssen
darüber hinaus sollte geprüft werden, ob ein kritischer Abschnitt
möglicherweise durch eine atomic-Direktive oder reductionKlausel ersetzt werden kann
18. November 2014
Synchronisation
28

if-Klausel:




bei manchen Problemen lohnt sich eine parallele Ausführung
erst ab einer gewissen Problemgröße
die Parallelisierung “kleiner” Schleifen mit wenig Rechenaufwand pro Iteration lohnt sich oft nur ab einer gewissen Anzahl
von Iterationen
in solchen Fällen kann die if-Klausel verwendet werden, die die
Ausführung eines parallelen Abschnitts an eine zur Laufzeit
ausgewertete Bedingung knüpft
Lastbalancierung:


während der Parallelisierung mit OpenMP sollte man das
Programm immer wieder ausführen, seine Laufzeit messen und
dabei auch die Auslastung der Prozessoren überprüfen
stellt man ein Ungleichgewicht bei der Prozessornutzung fest,
muss die Aufteilung der Arbeit auf die Threads neu überdacht
werden (bei parallelen Schleifen z. B. genügt oft die Anpassung
der Scheduling-Strategie)
18. November 2014
Synchronisation
29

Wo immer möglich nowait-Klauseln verwenden:



am Ende aller Arbeit aufteilenden Direktiven steht eine implizite
Barriere
wo es nicht notwendig ist, dass alle Threads auf die Beendigung
der Berechnungen auch des letzten Threads warten, sollte
immer die nowait-Klausel verwendet werden um die Wartezeit
an impliziten Barrieren zu minimieren
Möglichkeiten der Privatisierung von Daten nutzen:



zeitliche und räumliche Lokalität in Datenzugriffsmustern
ausnutzen, damit möglichst viele Anfragen direkt aus dem
Cache bedient werden können
Private Variablen erhöhen die Lokalität im Sinne der Cachenutzung ⇒ wo immer möglich Variablen als private deklarieren
False Sharing (mehrere Threads greifen gemeinsam auf dieselbe
Cache-Line zu) verhindern, z. B. durch statische SchedulingStrategien (Speicherbereiche auf die die Threads zugreifen
möglichst weit voneinander trennen)
18. November 2014
Synchronisation
30
Übung
Übung 13:
Synchronisation
18. November 2014
Synchronisation
31
OpenMP Teil 5:
OpenMP 4.0 Erweiterungen
Annika Hagemeier
Inhalt




Array Sections
Error Handling
SIMD-Konstrukte
Unterstützung für Beschleuniger
24. November 2014
2
4.0
Array Sections



Ein Feldabschnitt (array section) bezeichnet eine Teilmenge
eines Feldes
Ein Feldabschnitt kann nur in Klauseln verwendet werden, wo
er explizit erlaubt ist
Auch erlaubt bei mehrdimensionalen Feldern
Syntax C/C++:
[
[
[
[

Beispiel:
untere Grenze : Länge ] oder
untere Grenze : ]
oder
: Länge ]
oder
: ]
a[0:6]
A[1:]
b[10][:][:0]
C[1:10][42][0:6]
Fortran unterstützt bereits die Definition von Teilfeldern
24. November 2014
3
4.0
Error Handling (1)
#pragma omp cancel Konstruktname [if (expr)] new-line
Sauberer Weg, um die vorzeitige Beendigung eines
Konstruktes zu signalisieren
 Ein Thread signalisiert
 Alle anderen Threads springen zum Ende des Konstruktes

Konstruktname:





parallel
sections
for
taskgroup
Beispiel:

#pragma omp parallel for private (eureka)
for (i=0, i<n, ++i)
eureka = testing(i,...)
#pragma omp cancel parallel if (eureka)
24. November 2014

Der erste Thread, für den
eureka true ist, bricht die
parallele Region ab und
beendet sich
Alle anderen Threads
beenden sich, wenn sie
das nächste mal an die
cancel-Direktive stoßen
4
Error Handling (2)
4.0
#pragma omp cancellation point Konstruktname new-line
Bezeichnet einen benutzer-definierten Cancellation-Punkt
Ein Thread oder Task muss an diesem Punkt prüfen, ob für
das angegebene Konstrukt eine Abbruchbedingung
vorhanden/erfüllt ist
Vordefinierte Cancellation-Punkte sind:
 Implizite Barrieren
 barrier-Regionen
 cancel-Regionen
 cancellation point-Regionen



Konstruktname:




parallel
sections
for
taskgroup
24. November 2014
5
SIMD-Vektorisierung


4.0
SIMD-Prozessing nutzt Datenparallelität aus
Datenparallelität bedeutet, dass Operationen die auf
Vektorelementen durchgeführt werden, gleichzeitig
ausgeführt werden können
24. November 2014
6
simd-Direktive: Syntax
4.0
#pragma omp simd [Klausel[[,] Klausel] ...] new-line
for-Schleife


Gibt an, dass die folgende Schleife in eine SIMD-Schleife
transformiert werden kann, d.h. mehrere Iterationen der
Schleife können gleichzeitig im Sinne von SIMD-Instruktionen
verarbeitet werden
Die Schleifeniterationen werden dabei nicht auf die Threads
verteilt
Klauseln:

safelen (length)

linear (list[:linear-step])

aligned (list[:alignment])

private (list)

lastprivate (list)


collapse (n)
24. November 2014
7
declare simd-Direktive: Syntax
4.0
#pragma omp declare simd [Klausel[[,] Klausel] ...] nl
[#pragma omp declare simd [Klausel[[,] Klausel] ...] nl]
[...]
Funktionsdefinition oder -deklaration

Ermöglicht die Erzeugung einer SIMD-Version der
zugehörigen Funktion
Klauseln:

simdlen (length)

linear (argument-list[:constant-linear-step])

aligned (argument-list[:alignment])

uniform (argument-list)

inbranch

notinbranch
24. November 2014
8
for simd-Direktive: Syntax
4.0
#pragma omp for simd [Klausel[[,] Klausel] ...] new-line
for-Schleife



Gibt an, dass die folgende Schleife in eine SIMD-Schleife
transformiert werden kann, d.h. mehrere Iterationen der
Schleife können gleichzeitig im Sinne von SIMD-Instruktionen
verarbeitet werden
Die Schleifeniterationen werden auch auf die Threads
verteilt
Erlaubte Klauseln: alle Klauseln, die bei der for- und der
simd-Direktive erlaubt sind
24. November 2014
9
Unterstützung für Beschleuniger (1)






4.0
Host-zentriertes Modell: ein Host-Device und mehrere Target
-Devices vom selben Typ
Device: eine logische Ausführungseinheit mit lokalem
Speicher
Device Data Environment: Datenumgebung eines TargetDevices
target-Direktive kontrolliert wie Daten und Quelltext auf
Target-Devices ausgelagert werden
Daten werden von der Datenumgebung des Hosts auf die
Datenumgebung des Target-Devices abgebildet
Quelltext innerhalb der target-Region wird auf dem TargetDevice ausgeführt


Wird standardmäßig sequentiell ausgeführt
Kann aber auch
#pragma omp target map(to:B,C), map(tofrom:sum)
OpenMP-Direktiven #pragma omp parallel for reduction(+:sum)
zur parallelen Ausfor (int i=0; i<N; ++i)
sum += B[i] + C[i];
führung enthalten
24. November 2014
10
Unterstützung für Beschleuniger (2)
4.0
Direktiven:
 target: erzeugt eine Datenumgebung für ein TargetDevice, bzw. transferriert Daten auf das Target-Device und
führt den folgenden strukturierten Block auf dem Device aus
 target data: erzeugt eine Datenumgebung für ein TargetDevice, bzw. transferriert Daten auf das Target-Device
 target update: aktualisiert Daten innerhalb einer targetRegion
 declare target: compiliert Quelltext für ein Target-Device
Weitere Direktiven
 teams: erzeugt mehrere Master-Threads, die parallel
ausgeführt werden können, aber nicht miteinander
kommunizieren können
 distribute: verteilt die Iterationen einer parallelen Schleife
auf mehrere Thread-Teams
24. November 2014
11
Performance Analyse
Annika Hagemeier
Inhalt




Performance Analyse und Tuning
UNITE
Vampir
Scalasca
24. November 2014
Performance Analyse
2
Performance Analyse und Tuning



Erfolgreiches Tuning ist eine Kombination aus

Dem richtigen Algorithmus und Bibliotheken

Compiler-Flags und Pragmas/Direktiven

Nachdenken
Messen ist besser als Intuition bzw. Rätselraten

Um Performance-Probleme zu finden

Und Optimierungensergebnisse zu überprüfen
(nach jedem Schritt!)
Es ist leichter, ein langsames korrektes Programm zu
optimieren, als ein schnelles inkorrektes Programm zu
debuggen

Erst debuggen, dann tunen!

Niemanden interessiert es, wie schnell man ein
falsches Ergebniss produzieren kann
24. November 2014
Performance Analyse
3
Performance Analyse: Typisches Vorgehen

Habe ich ein Performance/Skalierungs-Problem?

Ermitteln z.B. durch Speedup-Messung

Mögliche Gründe:






Loadimbalances
Zu viel Overhead durch Kommunikation,
Synchronisation, ...
Serialisierungen
Was ist der größte Bottleneck?

Berechnung oder Kommunikation
Wo ist der größte Bottleneck?
Warum ist dies ein Bottleneck
24. November 2014
Performance Analyse
4
Ein Bild sagt mehr als 1000 Worte ...
Ringsendung
24. November 2014
Reales Beispiel
Performance Analyse
5
UNITE (UNiform Integrated Tool Environment)



Standardisiert den Zugriff auf Tools und
Dokumentation für die Performance-Analyse paralleler
MPI, OpenMP und hybriden MPI/OpenMP-Programme
auf High-Performance Compute Clustern
Besteht aus einer Reihe portabler, allgemein
anerkannter Tools, die mehrheitlich Open-Source sind
Basiert auf dem module-Kommando:

Standardisierte Tool- und Versionsidentifikation
 <tool>/<version>-<special>
 <special>: gibt an, ob das Tool für eine spezifische
MPI Bibliothek, Compiler oder 32/64-bit-Modus
vorgesehen ist
24. November 2014
Performance Analyse
6
UNITE - Benutzung


Tools erst sichtbar, nachdem UNITE geladen wurde:

module load UNITE
Benutzungsbeschreibung und Link zum Tool mittels:

module help <tool>
train085@jj28l01:~> module load UNITE
UNITE loaded
train085@jj28l01:~> module help vampir
------------------------------------------------------------------Module Specific Help for
/usr/local/UNITE/modulefiles/tools/vampir/8.1.0:
Vampir: Event Trace Visualizer
Version 8.1.0
Basic usage:
1. Start the trace visualizer (vampir)
2. Load and analyze trace file
For more information:
- See ${VAMPIR_ROOT}/doc/
- http://www.vampir.eu
- mailto:[email protected]
------------------------------------------------------------------24. November 2014
Performance Analyse
7
Vampir





Vampir = Visualization and Analysis of MPI Programs
Ursprünglich vom Forschungszentrum Jülich entwickelt
Heute hauptsächlich von der TU Dresden
weiterentwickelt
Vampirtrace:
 Bibliothek zum Tracen von MPI, OpenMP und
Anwendungsevents
 Bis Version 4.0 kommerziell, ab Version 5 open-source
Vampir Event Trace Visualizer:
 Kommerziell und portable
 Visualisiert Traces generiert mittels VampirTrace,
Scalasca, TAU
 Zudem existieren Konverter, die andere Formate in
Vampirformat konvertieren
24. November 2014
Performance Analyse
8
Vampir: Weitere Informationen
Weitere Informationen zu Vampir/VampirTrace:
 http://apps.fz-juelich.de/unite/index.php/Vampir
 http://www.vampir.eu/
24. November 2014
Performance Analyse
9
Vampir: Benutzung auf JUDGE (MPI)
Auf Login-Knoten:
 Module laden:
module load UNITE vampirtrace vampir
 Programm compilieren und linken mit:
vtcc -vt:cc mpicc -o my_proc my_proc.c
 interaktive Partition allokieren (mit X-Forwarding): msub -I -X -l nodes=2:ppn=8
Auf Compute-Knoten:
 Module laden:
module load UNITE vampirtrace vampir
 Programm normal ausführen (generiert TraceDatei .otf):
mpiexec -np 8 ./my_proc
Auf Login-Knoten:
 Traces anschauen mit Vampir:
vampir my_proc.otf
24. November 2014
Performance Analyse
10
Vampir: Trace View Window
Zoom
Toolbar
Charts
Toolbar
Global Timeline
24. November 2014
Performance Analyse
11
Scalasca

SCALASCA ist ein open-source Toolset zur
skalierbaren Performance Analyse von
hochskalierbaren parallelen Anwendungen
Weitere Informationen zu Scalasca:


http://apps.fz-juelich.de/unite/index.php/Scalasca
http://www.scalasca.org
24. November 2014
Performance Analyse
12
Scalasca: Benutzung auf JUDGE
Auf Login-Knoten:
 Modul laden:
module load UNITE scalasca
 Programm compilieren und linken mit:
skin mpicc -o my_proc my_proc.c  interaktive Partition allokieren (mit X-Forwarding): msub -I -X -l nodes=2:ppn=8
Auf Compute-Knoten:
 Modul laden:
module load UNITE scalasca
 Programm ausführen mit Scalasca Analyzer (generiert
Verzeichnis epik_...):
scan mpiexec -np 8 ./my_proc
Auf Login-Knoten:
 Profiles anschauen:
square epik_...
24. November 2014
Performance Analyse
13
Scalasca: Cube Result Browser
24. November 2014
Performance Analyse
14
Übung
Übung 14:
Hybride Programmierung
und Performance Analyse
24. November 2014
Performance Analyse
15

OpenMP - Forschungszentrum Jülich

Transcrição

Documentos relacionados

pragma omp parallel

Parallele Programmierung

6. Der OpenMP Standard

isoKERAM Gewebeband

MADE IN GERMANY Die ästhetischen Freischwinger gibt es in Stoff

26. April

Innengewinde-Adapter Metall für PMAJACK

Kinder bilden Zukunft 2010

Erstellt mit Poseidon for UML Community Edition

FCH-SE-PP Art.-Nr: 155307 DN 32

158 Gewinde-Kernlochdurchmesser · Thread hole