OpenMP „Open specifications for Multi

 Documents

 25 views
of 32
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Westfälische Wilhelms-Universität WIRTSCHAFTS Münster INFORMATIK WIRTSCHAFTSINFORMATIK OpenMP Präsentation im Rahmen des Seminars „Parallele und verteilte…
Share
Transcript
Westfälische Wilhelms-Universität WIRTSCHAFTS Münster INFORMATIK WIRTSCHAFTSINFORMATIK OpenMP Präsentation im Rahmen des Seminars „Parallele und verteilte Programmierung“ Michael Westermann WIRTSCHAFTS Gliederung INFORMATIK  Einführung  Vergleich von OpenMPI und MPI  Grundlagen  Parallelisierung von Programmbereichen  Koordination und Synchronisation von Threads  Zusammenfassung 2 WIRTSCHAFTS Einführung INFORMATIK  OpenMP: „Open specifications for Multi Processing“  Spezifikation für parallele Programmierung - Multiprozessor-Systeme - Gemeinsamer Speicher  Möglichkeit, ein Programm schrittweise zu parallelisieren  Compiler-Direktiven, Bibliotheksfunktionen, Umgebungsvariablen  Bindings für C, C++ und Fortran  1997 für Fortran; 1998 für C/C++  Aktuelle Version: OpenMP 2.5 (Mai 2005)  Von vielen Soft- und Hardwareherstellern unterstützt (Intel, Sun, Compaq usw.) 3 WIRTSCHAFTS Gliederung INFORMATIK  Einführung  Vergleich von OpenMPI und MPI  Grundlagen  Parallelisierung von Programmbereichen  Koordination und Synchronisation von Threads  Zusammenfassung 4 WIRTSCHAFTS Vergleich OpenMP vs. MPI INFORMATIK Kriterium OpenMP MPI Hardware Gemeinsamer Speicher Verteilter oder Gemeinsamer Speicher Sprachen C, C++, Fortran C, C++, Fortran Inkrementelle einfach Programm muss neu Parallelisierung designed werden Kommunikation Gemeinsame Variablen Message Passing Serialität bleibt erhalten Ja nein Anzahl Prozessoren Bis ca. 8 praktikabel Auf sehr hohe CPU- Anzahlen skalierbar  OpenMP und MPI können auch kombiniert werden: - MPI verteilt Arbeit auf Multiprozessor-Systeme - OpenMP führt die Arbeit dort parallel aus 5 WIRTSCHAFTS Gliederung INFORMATIK  Einführung  Vergleich von OpenMPI und MPI  Grundlagen - Gemeinsamer Speicher - Programmiermodell - OpenMP-Direktiven  Parallelisierung von Programmbereichen  Koordination und Synchronisation von Threads  Zusammenfassung 6 WIRTSCHAFTS Grundlagen: Gemeinsamer Speicher INFORMATIK  Gemeinsamer Speicher Gemeinsamer Speicher - Mehrere Prozessoren Pi: Prozessor i - Einheitlicher Adressraum P0 P1 P2 Pn  Verteilter gemeinsamer Netzwerk Globaler Adressraum Speicher Pi: Prozessor i - Mehrere Prozessoren M0 M1 M2 Mn Mi: RAM von Pi - Seitenbasierter, virtueller, gemeinsamer P0 P1 P2 Pn Adressraum  Beide Varianten werden von OpenMP unterstützt 7 WIRTSCHAFTS Grundlagen: Programmiermodell INFORMATIK  Auf Threads basierend - Ausführungsfäden innerhalb eines Prozesses - Leichtgewichtiger als Prozesse - Gemeinsamer Adressraum, zusätzlich eigener Stack - Kommunikation über gemeinsame Variablen Master- Thread FORK Team von Paralleler  Fork-join-Prinzip Threads Bereich - Master-Thread erzeugt weitere Threads JOIN - Parallele Ausführung des Bereichs - Synchronisation der Threads am Ende - Beenden der Slave-Threads 8 WIRTSCHAFTS OpenMP-Direktiven INFORMATIK  Einbinden der Datei omp.h zu Beginn  Parallelisierung mittels Compiler-Direktiven #pragma omp  Direktive wird ignoriert, wenn Compiler OpenMP nicht unterstützt - Programm wird seriell ausgeführt - Identischer Quelltext für Ein- und Multiprozessor-System 9 WIRTSCHAFTS Gliederung INFORMATIK  Einführung  Vergleich von OpenMPI und MPI  Grundlagen  Parallelisierung von Programmbereichen - Parallele Bereiche - Parallelisierung von Schleifen - Parallelisierung unabhängiger Abschnitte  Koordination und Synchronisation von Threads  Zusammenfassung 10 WIRTSCHAFTS Parallele Bereiche INFORMATIK  parallel-Direktive: #pragma omp parallel [Parameter [, Parameter]…] { Anweisungsblock }  Grundlegendes Konstrukt  Threads arbeiten Anweisungsblock mit gemeinsamen oder privaten Variablen ab (single program multiple data, SPMD)  Synchronisation am Ende des parallelen Bereichs  Parallele Bereiche können geschachtelt werden  Parameter: - Bestimmung der Thread-Anzahl ( num_threads(x) ) - Variablendeklarationen (gemeinsame vs. private Variablen) 11 WIRTSCHAFTS Parameter: Variablendeklarationen INFORMATIK  shared() - Gemeinsame Variablen der Threads  Lesen und Schreiben findet auf gleichem Datenbereich statt  private() - Jeder Thread erhält uninitialisierte Kopie der Variablen  Nur der jeweilige Thread kann diese Lesen und Schreiben  default(shared | private | none) - shared: Variablen sind standardmäßig gemeinsam - private: Variablen sind standardmäßig privat - none: Alle Variablen müssen explizit gekennzeichnet werden  Weitere Variablendeklarationen: - firstprivate, lastprivate, copyin, reduction 12 WIRTSCHAFTS Parallele Bereiche: Beispiel INFORMATIK #include int nummer; int main() { #pragma omp parallel private(nummer) num_threads(4) { // Nummer des aktuellen Threads nummer = omp_get_thread_num(); printf("Thread-Nummer: ",nummer); } } Mögliche Ausgabe: Thread-Nummer: 0 Thread-Nummer: 2 Thread-Nummer: 1 Thread-Nummer: 3 13 WIRTSCHAFTS Gliederung INFORMATIK  Einführung  Vergleich von OpenMPI und MPI  Grundlagen  Parallelisierung von Programmbereichen - Parallele Bereiche - Parallelisierung von Schleifen - Parallelisierung unabhängiger Abschnitte  Koordination und Synchronisation von Threads  Zusammenfassung 14 WIRTSCHAFTS Parallelisierung einer for-Schleife INFORMATIK Speicher A[1] 4 Prozessoren: for(i=1,i<=25,i++) a[i] = b[i] + c[i] A[100] for(i=26,i<=50,i++) B[1] for(i=1,i<=100,i++) a[i] = b[i] + c[i] a[i] = b[i] + c[i] for(i=51,i<=75,i++) a[i] = b[i] + c[i] B[100] for(i=76,i<=100,i++) C[1] a[i] = b[i] + c[i] C[100] 15 WIRTSCHAFTS Parallelisierung einer for-Schleife INFORMATIK  Work-Sharing-Konstrukt  Verteilung der Iterationen auf mehrere Threads  Jede Iteration wird von genau einem Thread ausgeführt  for-Direktive: #pragma omp #pragma omp parallel for [Parameter…] for [Parameter…] for (Index=Startwert; Test; Inkrementierung) { Schleifenrumpf }  Voraussetzungen: - Iterationen unabhängig voneinander - Anzahl Iterationen vor Ausführung bestimmbar - Innerhalb eines parallelen Bereichs (oder kombinierte Direktive) 16 WIRTSCHAFTS Parallelisierung einer for-Schleife INFORMATIK for (i=Startwert; Test; Inkrementierung) Anforderungen an Schleifenkopf:  i: Variable vom Typ int  Startwert: x  Test: i op x , mit op  { <, ≤, >, ≥ }  Inkrementierung: ++i, --i, i++, i--, i += x, i -= x, i = i + x, i = i - x  x: Schleifenunabhängiger Integer-Ausdruck 17 WIRTSCHAFTS Parameter for-Direktive: schedule INFORMATIK  Steuert Aufteilung der Iterationen auf die Threads  Lastverteilung  schedule(static, block_size) - Iterationen werden in Blöcke der Größe block_size zusammengefasst - Verteilung der Blöcke auf die Threads bereits vor Ausführung  schedule(dynamic, block_size) - Iterationen werden in Blöcke der Größe block_size zusammengefasst - Nach Bearbeitung eines Blockes erhält Thread neuen Block  schedule(guided, block_size)   - Exponentiell abnehmende max Anzahl _ offene_ Iterationen;block _ size         Blockgröße im Zeitverlauf    Anzahl _Threads    - Beispiel: 64 Iterationen, 2 Threads, block_size=4: 1. 64/2=32, 2. 32/2=16, 3. 16/2=8, 4. 8/2=4, 5. 4 18 WIRTSCHAFTS Beispiel for-Direktive: Primzahlenausgabe INFORMATIK #include #include int main() { int zahl, teiler, treffer; printf ("Primzahlen: \n"); #pragma omp parallel for private(teiler,treffer) \ schedule(dynamic,100) for (zahl = 2; zahl < 100000; zahl++) { treffer = 0; #pragma omp parallel for private(teiler, treffer) // Überprüfung ob 2 bis zahl Teiler von zahl for (teiler = 2; teiler < zahl; teiler++) { if (zahl % teiler == 0) { Mögliche Ausgabe: treffer = 1; } Primzahlen: } 2, 3, 5, 7, 11, if (treffer == 0) { 13, 101, 19, printf ("%d, ", zahl); } 23, 113, 29, } […], 99991, } 19 WIRTSCHAFTS Parameter for-Direktive: ordered INFORMATIK  Ausführung erst, wenn alle vorherigen Iterationen den Anweisungsblock beendet haben  ordered-Parameter der for-Direktive hinzufügen  ordered-Direktive vor entsprechenden Anweisungsblock: #pragma omp ordered { Anweisungsblock } 20 WIRTSCHAFTS Beispiel: Primzahlenausgabe, aufsteigend INFORMATIK #include #include int main() { int zahl, teiler, treffer; printf ("Primzahlen: \n"); #pragma omp parallel for private(teiler, treffer) \ schedule(static,1) ordered for (zahl = 2; zahl < 100000; zahl++) { treffer = 0; // Überprüfung ob 2 bis zahl Teiler von zahl for (teiler = 2; teiler < zahl; teiler++) { if (zahl % teiler == 0) { treffer = 1; } Ausgabe: } Primzahlen: #pragma omp ordered 2, 3, 5, 7, 11, if (treffer == 0) { 13, 19, 23, 29, printf ("%d, ", zahl); } 31, 37, 41, 43, } 47, […], 99991, } 21 WIRTSCHAFTS Gliederung INFORMATIK  Einführung  Vergleich von OpenMPI und MPI  Grundlagen  Parallelisierung von Programmbereichen - Parallele Bereiche - Parallelisierung von Schleifen - Parallelisierung unabhängiger Abschnitte  Koordination und Synchronisation von Threads  Zusammenfassung 22 WIRTSCHAFTS Parallelisierung unabhängiger Abschnitte INFORMATIK  Work-Sharing-Konstrukt  Abschnitte werden auf Threads verteilt  Jeder Abschnitt wird von genau einem Thread ausgeführt  sections-Direktive: #pragma omp sections [ Parameter [, Parameter …] ] { [ #pragma omp section { Anweisungsblock_1 } ] [ #pragma omp section { Anweisungsblock_2 } ] }  Abschnitte müssen unabhängig voneinander sein  section-Direktive nur innerhalb der sections-Direktive 23 WIRTSCHAFTS Gliederung INFORMATIK  Einführung  Vergleich von OpenMPI und MPI  Grundlagen  Parallelisierung von Programmbereichen  Koordination und Synchronisation von Threads - Kritische Abschnitte - Atomare Operationen - Synchronisation - Ausführung ausschließlich des Master-Threads  Zusammenfassung 24 WIRTSCHAFTS Race Conditions INFORMATIK  Beispiel:  A=0  2 Threads führen parallel aus: A = A + 1  Mögliche Ergebnisse: - A=2 - A=1  Ergebnis hängt vom zeitlichen Ablauf der Operationen ab  Lösungsmöglichkeiten: - Kritische Abschnitte - Atomare Operationen 25 WIRTSCHAFTS Kritische Abschnitte INFORMATIK  Wechselseitiger Ausschluss (mutual exclusion)  Abschnitte werden zu kritischen Abschnitten deklariert  Höchstens ein Thread darf gleichzeitig im kritischen Abschnitt mit gleichem name sein  critical-Direktive: #pragma omp critical [(name)] { kritischer_Abschnitt } 26 WIRTSCHAFTS Atomare Operationen INFORMATIK  Zuweisung wird „am Stück“ (atomar = unteilbar) ausgeführt  atomic-Direktive: #pragma omp atomic Zuweisung  Zuweisung darf folgende Form haben: - x++, x- - - ++x, - - x - x binop= skalarer_Ausdruck  binop  { +, -, *, /, &, ^, |, <<, >> }  skalarer_Ausdruck darf nicht auf x referenzieren und ist nicht Teil der atomaren Operation 27 WIRTSCHAFTS Synchronisation von Threads INFORMATIK  barrier-Direktive: #pragma omp barrier  Thread setzt Ausführung erst fort, wenn alle Threads die barrier-Direktive erreicht haben  Bezieht sich nur auf Threads des eigenen „Teams“  Direktive muss von allen oder von keinem Thread erreicht werden - Sonst: Verklemmung (Deadlock) 28 WIRTSCHAFTS Ausführung nur durch Master-Thread INFORMATIK  Master-Direktive: #pragma omp master { Anweisungsblock }  Anweisungsblock wird ausschließlich von Master-Thread bearbeitet  Bei verschachtelter Parallelisierung: Master-Thread des innersten parallelen Bereichs  Alle anderen Threads ignorieren den Block 29 WIRTSCHAFTS Gliederung INFORMATIK  Einführung  Vergleich von OpenMPI und MPI  Grundlagen  Parallelisierung von Programmbereichen  Koordination und Synchronisation von Threads  Zusammenfassung 30 WIRTSCHAFTS Zusammenfassung INFORMATIK  Einheitlicher Standard für Programmierung von Parallelrechnern mit gemeinsamem Speicher  Ermöglicht leichte Parallelisierung bestehender Programme (inkrementelle Parallelisierung)  Parallelisierung mittels Compiler-Direktiven  Fork-join-Prinzip  Unterstützung namhafter Hersteller  http://www.openmp.org/ 31 Westfälische Wilhelms-Universität WIRTSCHAFTS Münster INFORMATIK WIRTSCHAFTSINFORMATIK Vielen Dank für die Aufmerksamkeit
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks