OpenMP

Ausgabe:

und eine weitere section

Thread 0 war hier.

Aber hier war Thread 2.

Thread 0 sagt Tschüss

Thread 2 sagt Tschüss

Thread 3 sagt Tschüss

Thread 1 sagt Tschüss

Ausgabe:

Durchläufe Thread 1 = 457

Durchläufe Thread 2 = 544

sum = 1001

Durchläufe Thread 1 = 500

Durchläufe Thread 2 = 500

sum = 1000

Durchläufe Thread 1 = 967

Durchläufe Thread 2 = 34

sum = 1001

Durchläufe Thread 1 = 882

Durchläufe Thread 2 = 118

sum = 1000

Ordered Schleife

• Ordered Schleifen ermöglichen die Abarbeitung der Iterationen in vorgegebener Reihenfolge

Quellen

• Parallele Programmierung, Springer
• Informatik im Fokus - OpenMP, Springer
• http://www.c-plusplus.de
• http://openmp.org/wp/openmp-compilers/
• http://openmp.org/wp/openmp-specifications/
• http://de.wikipedia.org/wiki/OpenMP

parallele Schleifen

p

• Wichtigste Direktive zur Verteilung der Arbeit
• #pragma omp for [Parameter[Parameter]...]
• Bedingungen für Parallelisierbarkeit:
• Anzahl der Iterationen ist vorher bekannt
• Berechnungen der Iterationen sind unabhängig
• Inkrementierung ist konstant
• Anzahl der Durchläufe wird durch Thread-Anzahl geteilt und auf die Threads aufgeteilt

T

p

Shared Memory

Steurung der parallelen Abarbeitung

Ausgabe

Verschachtelung von Schleifen

• alle Threads haben Zugang zum selben globalen Speicher
• Synchronisation findet statt (meist implizit)

p

• Nur mit zusätzlichem Parallelblock realisierbar
• Innere Parallele Bereiche werden jedoch per Default sequenziell ausgeführt!
• Möglichkeiten ab OpenMP 3.0:
• Collapse-Schleifen
• Nur für sehr einfache Schleifen

• Wichtigste Mechanismen über Compiler-Direktiven
• #pragma omp parallel[Parameter[Parameter]...]
• Parallel-Direktive erzeugt Team von Threads (fork)
• Header <omp.h> stellt Bibliotheksfunktionen bereit
• Alle Threads führen die gleichen Berechnungen durch! (auf privaten Daten)
• Am Ende des parallelen Bereichs läuft nur der Master-Thread weiter

mit Ordered-Direktive

0^10 = 0

1^10 = 1

2^10 = 1024

3^10 = 59049

4^10 = 1048576

5^10 = 9765625

6^10 = 60466176

7^10 = 282475249

8^10 = 1073741824

9^10 = 3486784401

10^10 = 10000000000

ohne Ordered Direktive

3^10 = 59049

4^10 = 1048576

5^10 = 9765625

8^10 = 1073741824

9^10 = 3486784401

10^10 = 10000000000

0^10 = 0

1^10 = 1

2^10 = 1024

6^10 = 60466176

7^10 = 282475249

p

T

Steuerung der parallelen Abarbeitung

Hinweise zur Funktionsweise

Beispiel: private / shared

• Über Parameter kann angegben werden welche Variablen private/shared sind und wie geschedult werden soll
• Das Ende eines parallelen Bereichs impliziert einen Synchronisationspunkt
• Threads werden am Ende eines Parallelen Bereichs nicht zerstört um aufwändige Neuerstellung im nächsten parallelen Bereich einzusparen

Wichtige Befehle

• omp_get_num_threads() - gibt Anzahl der offenen Threads zurück
• omp_get_thread_num() - gibt die dem Thread zugehörige Nummer zurück (0..n-1)

sum = 0

if (0 < 1000)

sum = 0 + 1 = 1

sum = 1

if (1 < 1000){

sum = 1 + 1 = 2

sum = 2

if (2 < 1000)

sum = 3

if (2 < 1000)

sum = 2 + 1 = 3

sum = 3 + 1 = 4

sum = 4

if (999 < 1000)

if (999 < 1000){

sum = 999 + 1 = 1000

sum = 1000

if (1000 < 1000) STOP!

sum = 1001

sum = 1000 + 1 = 1001

if (1000 < 1000) STOP!

Nichtiterative parallele Bereiche

Section Direktive

Gliederung

• Einleitung
• Steuerung der parallelen Abarbeitung
• Parallele Schleife
• Nichtiterative Parallele Bereiche
• Anzahl der Threads
• Koordination von Threads

Single-Direktive

Ausführungsreihenfolge von Threads

• Barrier-Direktive (#pragma omp barrrier) sorgt dafür, dass alle Threads an der Stelle im Programmcode warten.

Beispiel

Durch nowait kann Ausführung beschleunigt

werden, Synchronisation mit übrigen Threads

entfällt

• Programmierschnittstelle für C, C++, Fortran zur Shared Memory Programmierung
• Parallelisierung auf Thread-Ebene
• Umfasst Compiler-Direktiven und Bibliotheksfunktionen

Koordination von Threads

Reduction

Sequenzielle Konsistenz und Race Conditions

• Mit #pragma omp parallel reduction (Op:Var) können Rechnungen wie z.B. s += f(1)+f(2)+...+f(n) parallel ausgeführt werden.
• Hierzu wird die Variable mit der Operation angegeben.
• Jeder Thread erhält eine eigene Kopie der Variable, die mit dem neutralen Element der Operation initialisiert wurde
• Am Ende werden die Variablen mit der entsprecheznden
• Operation zusammengefasst
• Mögliche Operationen sind: +, -, *, &, |, ^, && und ||

Deadlocks

Ausgabe:

Durchläufe Thread 1 = 614

Durchläufe Thread 2 = 639

sum = 1001

Durchläufe Thread 1 = 570

Durchläufe Thread 2 = 646

sum = 1000

Durchläufe Thread 1 = 60

Durchläufe Thread 2 = 962

sum = 1001

Durchläufe Thread 1 = 727

Durchläufe Thread 2 = 514

sum = 1000

Kritische Bereiche

konsistente Speicherbelegung: Flush

Critical

Beispiel 2

Mit #pragma_omp_critical [(name)] können

Abschnitte gekennzeichnet werden, in denen sich

nicht zwei Threads gleichzeitig befinden dürfen.

Anzahl der Threads

Beispiel 1

Ausgabe:

Geben sie eine Zahl ein: Geben sie eine Zahl ein:

• Mit #pragma omp flush [(list)] kann eine Liste von Variablen mit dem Hauptspeicher synchronisiertwerden
• Ohne Parameter werden alle Variablen synchronisiert

Atomic

#pragma_omp_atomic sorgt dafür, dass auf die

entsprechende Variable von keinem anderen Thread zugegriffen werden kann (weder lesen noch schreiben)

• Ohne konkrete Angabe der OpenMP - Implementierung überlassen
• Anzahl der Threads kann dynamisch (Anpassung durch Laufzeitumgebung) oder fest gewählt werden

Dynamische Threaderstellung setzten und abfragen:

• Setzten mit void omp_set_dynamic (int dynamic_threads)
• Abfrage mit int omp_get_dynamic(void)
• Als True / False (0, !=0)

Maximale Anzahl Threads setzen und abfragen:

• Setzten mit Parameter num_threads(n) in der Parallel-Direktive
• Setzten mit void omp_set_num_threads (int num_threads)
• Abfrage mit int omp_get_num_threads(void)

Sieb des Eratosthenes