OpenMP (Open Multi Processing) wird vom The Open MP Architecture Review Board weiterentwickelt und standarsisiert. Das ARB ist eine non-profit-Organisation mit ständigen und zeitweiligen Mitgliedern. Wer? Die üblichen Verdächtigen:
AMD (Dibyendu Das), CAPS-Entreprise (Francois Bodin), Convey Computer (John Leidel), Cray (James Beyer), Fujitsu (Matthijs van Waveren), HP (Uriel Schafer), IBM (Kelvin Li), Intel (Jay Hoeflinger), Microsoft (Niklas Gustafsson), NEC (Kazuhiro Kusano), NVIDIA (Yuan Lin), Oracle Corporation (Nawal Copty), Signalogic (Chris Johnson), The Portland Group, Inc. (Michael Wolfe), Texas Instruments (Andy Fritsch)
ANL (Kalyan Kumaran), ASC/LLNL (Bronis R. de Supinski), cOMPunity (Barbara Chapman), EPCC (Mark Bull), LANL (John Thorp), NASA (Henry Jin), ORNL (Oscar Hernandez), RWTH Aachen University (Dieter an Mey), Texas Advanced Computing Center (Kent Milfeld)
Das ARB ist Eigentümer der Marke OpenMP.
Literatur zum High performance computing:
siehe 1 auf Seite pageref
added features only
| 198x | Herstellereigene Direktiven für SMP-Rechner |
| 1991 | PCF (Parallel Computing Fortran) |
| 1994 | ANSI X3H5 |
| 1995 | Compaq KAP Fortran |
| 199x | SGI, Cray, KAI, ASCI: first draft |
| 199x | DEC, HP, IBM, Intel joined |
| 10'1997 | OpenMP Fortran 1.0 |
| 10'1998 | OpenMP C/C++ 1.0 |
| 11'1999 | OpenMP Fortran 1.1 |
| 11'2000 | OpenMP Fortran 2.0 (copyprivate, threadprivate, timers, num_threads, workshare) |
| 3'2002 | OpenMP C/C++ 2.0 (num_threads, copyprivate, wtick, wtime, c99-vla) |
| 5'2005 | OpenMP 2.5 (keine Sprachänderungen; Neugestaltung des Textes; C/C++/Fortran) |
| 5'2008 | OpenMP 3.0 (tasks, atomicity, auto, ICV) |
| 7'2011 | OpenMP 3.1 (final, mergeable, taskyield, min, max, omp_infinalICV bind-var) |
| 11'2012 | OpenMP 4.0 Release Candidate |
Ziele von OpenMP: standardisiert, lean and mean, ease of use, portable
Keine Ziele: DMP, Effizienz, Checks
Absoft Pro, Compaq Fortran, Fujitsu-Siemens Fortran 95, GNU, HP, IBM XL, Intel Software Development, Lahey/Fujitsu Fortran 95 , Portland Group Compilers and Tools, SGI MIPSpro, Sun Studio, PathScale
Intel, PGI und Gnu unterstützen OpenMP 3.1 und 3.1 nicht nicht voll (Juni 2012, siehe [Bar], 5. Compiling OpenMP Programs).
http://www.compunity.org/resources/compilers/index.php
OpenMP 2.5 ist ab gcc 4.2 seit dem 9.3.2006 verfügbar. gcc 4.4 stellt OpenMP 3.0 und gcc 4.7 OpenMP 3.1 bereit.
Übersetzung: gcc -fopenmp ...
-fopenmp impliziert -frecursive und damit Stackbenutzung für lokale Variable.
Anzahl der Threads: export OMP_NUM_THREADS=5, setenv OMP_NUM_THREADS 5
Übersetzung: icc -openmp ...
Anzahl der Threads: export OMP_NUM_THREADS=5
Übersetzung: pgcc -mp ...
Anzahl der Threads: export OMP_NUM_THREADS=5
use thread safe compilers only; name ends with _r
Mit OMP werden Parallelprogramme im shared memory Modell geschrieben.
OMP ist eine einfache Spracherweiterung von Fortran, C und C++. Die Implementierung erfolgt durch Pragmas und spezielle OMP-Kommentare.
OMP besteht aus wenigen abstrakten Anweisungen und Bibliotheks-Funktionen. Der Rest wird automatisch und für den Programmierer unsichtbar abgewickelt (Start und Ende von Threads...). Das macht OMP-Programme relativ leicht entwickelbar und den Umstieg auf parallele Programme evolutionär; ein sequentielles Programm kann gezielt an hotspots parallelisiert werden und ist sofort wieder lauffähig. Inkrementell kann die Parallelisierung fortgesetzt werden. Jede Parallelisierung ist lokal.
Man kann bei vorsichtiger Parallelisierung jederzeit zur sequentiellen Version zurückkehren.
OMP ermöglicht die Auslastung moderner CPUs wie Sandybridge oder Interlagos auf relativ leichte Weise.
OMP ist ein offener, herstellerunabhängiger Standard und somit portabel.
OMP enthält kaum Hilfen zur Fehlersuche und bürdet dem Programmierer die Last der Fehleranalyse und -suche auf. Deadlocks und Data races sind problemlos erzeugbar und erschweren die Entwicklung robuster Programme. Hilfstools wie Thread checker (Intel) sind fast unverzichtbar.
Die Beschleunigung sequentieller Programme alleine durch OMP ist trotz schneller Anfangserfolge sehr begrenzt (siehe [Rab08]).
Figure
Interthreadkommunikation erfolgt über shared Variable. Synchronisation mit Hilfe des Speichers ist maschinen- und compilerabhängig teuer (250, 1000, 10000 Takte bei schnellen Compilern, manchmal bis 200000 Takte in speziellen Kombinationen; siehe [Hag12]).
Ein OMP-Programm beginnt in einem Thread, kann jederzeit in mehrere Threads aufgespalten und wieder zu einem Thread zusammengeführt werden. Wann wieviele Auspaltungen in wieviele Threads erfolgen, kann vom Programmierer frei festgelegt werden. Die Anzahl der Threads kann auch außerhalb des Programms entschieden werden.
Die folgende Skizze löst ein Problem in drei konkurrierenden Algorithmen. Der schnellste Algorithmus liefert die Lösung, die dann in einer parallelen Schleife verifiziert wird. Das Programm besteht aus drei sequentiellen Phasen und zwei Threadteams mit drei und sieben Threads. Die Threadteams werden im Fork-join Modell erzeugt. Am Ende jeder parallelen Phase erfolgt eine implizite Synchronisation.
http://www.uni-regensburg.de/EDV/kurs_info/brf09510/hpc/openMP/hola.c
OMP-Anweisungen sind meist zusätzliche Compileranweisungen (Direktiven), die auf jeweils eine Anweisung in der Programmiersprache wirken. Sie werden von nicht-OMP-Compilern weggelassen.
Präprozessorvariable: _OPENMP
Fortran-Sentinel: !$OMP
Die Direktiven werden durch Clauses ergänzt, in denen die parallelen Eigenschaften von Variablen definiert werden (shared, private), Reduktionsoperationen angewiesen werden oder die genaue parallele Ausführung festgelegt wird (collapse, schedule, nowait).
Vorsicht: OMP-Pragmas wirken auf die (eine!) nachfolgende Anweisung. Diese darf nicht schon in der OMP-Pragma-Zeile beginnen.
// falsch: #pragma omp parallel {
In Fortran wird nicht nur der Anfang eines Threadteams sondern auch sein Ende mit OMP markiert.
!$OMP PARALLEL
omp_set_num_threads() Anzahl der gerade im Team arbeitenden Threads
omp_get_num_threads()
omp_get_max_threads()
omp_get_thread_num() Nummer eines Threads im gerade arbeitenden Team
omp_get_thread_limit()
omp_get_num_procs()
omp_get_num_threads()
sections loops tasks single
#pragma omp parallel
for (i = 0; i < N; i++)
int p = omp_get_num_threads(); // Aktuelle Threadanzahl
#pragma omp parallel
#pragma omp parallel
Nachteilig bei Variablen verschiedener Thread in derselben cache line
Portionsgröße chunk c
#pragma omp parallel
Die letzte Portion kann ist der Rest, der kleiner sein kann.
#pragma omp parallel
#pragma omp parallel
double t = OMP_GET_WTIME();
Wichtigste Aufgabe von OMP: Lastverteilung.
Wichtigste Lastverteilung: Schleifenlastverteilung.
#pragma omp for
Die Anweisung in einer parallelen Zone verteilt die Last der nachfolgenden Schleife auf die Threads. Das kann ein Programm beschleunigen, wenn die Arbeit in kürzerer Zeit erledigt wird. Das kann auch bremsen, wenn die Lastverteilung und -koordination mehr Zeit verbraucht, als eingespart wird.
Abkürzung:
#pragma omp parallel for
Die Schleife ist nicht frei, sondern muss in kanonischer Form vorliegen, d.h. sie folgt etwa denselben Vorgaben wie die UPC-forall-Schleife:
Die Schleife muss in C eine for-Schleife sein. while und do sind verboten. Analog ist in Fortran DO WHILE verboten.
Bei Schleifenbeginn muss die Anzahl der Schleifendurchläufe feststehen. Dasselbe gilt für alle eingeschachtelten inneren Schleife, die von der Parallelisierung betroffen sind. Diese Schleifenkontrolle muss für alle Threads identisch sein.
Die Schleifenvariable darf in der Schleife nicht zusätzlich geändert werden.
Das Ergebnis der Schleife muss unabhängig von der Reihenfolge der Durchläufe sein. Die einzelnen Durchläufe dürfen keine Abhängigkeiten aufweisen.
Die Schleife darf nicht mit break oder goto verlassen werden. continue ist erlaubt, wenn es nur in der innersten Schleife vorkommt. exit ist ebenfalls erlaubt. In C++ ist ein throw verboten, wenn sein catch außerhalb des throwenden Threads liegt.
Die Schleifenvariable muss vom Typ integer, Zeiger oder Iterator (C++) sein. Der Iterator muss ein Random access iterator sein.
Die Schleifenvariable wird mit var = lb initialisiert.
Die Schleifenvariable wird mit < <= > >= le getestet.
Die Schleifenvariable wird im Schleifenkopf mit ++ -- += -= li geupgedatet.
lb, le und li sind bei Schleifenbeginn berechnete Werte, die während der Schleife nicht mehr geändert werden dürfen.
Maximal ein schedule, maximal ein collapse, maximal ein ordered und amximal ein nowait.
chunk_size muss eine schleifeninvariante integer mit positivem Wert sein, der bei allen Threads identisch ist. chunk_size ist bei runtime und auto verboten.
OpenMP ist in der Anzahl der Threads sehr flexibel. Die tatsächliche Parallelität ist natürlich durch die reale Anzahl der Prozessoren beschränkt.
p = omp_get_num_procs ();
Ist die Anzahl der Threads in einem Team kleiner, dann bleiben vorhandene Resourcen unbenutzt. Ist sie größer, werden Threads hintereinander vom selben Prozessor ausgeführt. Natürlich ist es günstig, die Anzahl der Threads mit der Anzahl der Prozessoren zu korrelieren.
In jeder parallelen Zone kann die Anzahl der Threads mit der Klausel num_threads(p) explizit festgelegt werden.
Ist das nicht erfolgt, gilt der in einer omp_set_num_threads(p)-Anweisung festgelegte Wert von p, der in der internen Variablen (ICV) nthreads-var gespeichert wurde.
Ohne einen solchen Aufruf gilt der Wert aus der Umgebungsvariablen OMP_NUM_THREADS.
Die Threads eines Teams können am Ende einer parallelen Reduktion eine gemeinsame Reduktion durchführen. Das wird mit einer Reduktionsklausel festgelegt:
reduction(op:list)
Der Parameter op bestimmt die Operation und der Anfangswert der Reduktionsvariablen.
In C sind die erlaubten Operatoren und die Anfangswerte
+ 0, - 0, * 1, & ~0, | 0, ^ 0, && 1, || 0, max n, min x
In Fortran sind die erlaubten Operatoren und die Anfangswerte
+ 0, - 0, * 1, .and. .true., .or. .false., .eqv. .true., .neqv. .false., max n, min x iand alle Bits 1, ior 0, ieor 0
Dabei sind x und n der größte bez. der kleinste mögliche Wert der Datentypes der Reduktionsvariablen.
Für alle Variablen der Liste wird in jedem Thread eine threadlokale Kopie erzeugt und initialisiert. Die Threads arbeiten mit ihren lokalen Kopie. Am Ende nach der Barriere werden alle lokalen Kopien in die gleichnamige Hauptvariable reduziert.
Ein nowait ist sinnlos und führt zu data races.
Nach einer parallelen Schleife wirkt eine implizite Barriere. Alle Threads müssen warten, bis auch der letzte die Schleife beendet hat.
Diese Barriere kann durch die Klausel nowait aufgehoben werden. Dann muss der Programmierer sicherstellen, dass anschließende Anweisungen fertiger Threads keine ggf. unvollständig geschriebenen Variablen von noch nicht fertigen Threads benutzen. Das kann im Einzelfall schwierig sein und ist meistens falsch.
#pragma omp for collapse(n)
Mit collapse können mehrere Schleifen (die nächsten n) zusammen von einem Thread-Team bearbeitet werden. Der Parameter n ist eine konstante positive ganze Zahl.
Schedule regelt die Verteilung der Schleifendurchläufe auf die Threads. Die Angabe erfolgt in der clause schedule(type,chunk).
Die Schleife wird in zusammenhängende Iterationsgruppen der Größe chunk zerlegt, die round-robin an die Threads des Teams vergeben werden. Ohne chunk-Angabe ist die Gruppe maximal, d.h. es gibt soviele Iterationsgruppen wie Threads.
Jeder Thread arbeitet somit ein fast gleich großes zusammenhängendes Stück ab.
Die portionierten Teile werden der Reihe nach vom jeweils einem Thread übernommen. Ideal, wenn die Teile nicht gleich lange brauchen. Ohne Portionsgröße gilt chunk = 1.
Die Portionsgröße nimmt ab. Jeder freie Thread erhält eine Portion der Größe Anzahl der noch fehlenden Iterationen / Anzahl der Threads im Team. Mit zunehmender erledigter Arbeit sinkt also die Portionsgröße. Der Portionsparameter ist die Mindestgröße.
Compiler oder Programm steuert die Verteilung.
runtime: Das Programm steuert die Verteilung.
Ein Thread wartet auf eine gesperrte Resource, die nie wieder frei wird.
Zwei Threads greifen auf eine gemeinsame Variable zu. Mindestens einer schreibt in diese Variable. Die Zugriffe sind nicht synchronisiert; ihre Reihenfolge ist nicht definiert; das Ergebnis hängt jedoch von der Reihenfolge ab.
Mindestens ein Thread beendet seine Arbeit nicht.
Ohne data race greifen zwei Threads auf verschiedene Variable in derselben Cache line zu. Das geschieht häufig in Feldern. Dabei werden in den L1 caches die cache Gültigkeiten entwertet, was zu Geschwindigkeitsverlusten und hohem Datenverkehr im cache führt.
Speicher ist im shared memory Modell zwar in allen threads zugreifbar, oft aber trotzdem einzelnen threads zugeordnet. Bei Fehlzuordnungen muss er unter Zeitverlust über core links zugegriffen werden.
Intel Thread checker
http://www.uni-regensburg.de/EDV/kurs_info/brf09510/hpc/openMP/bitonic.c
http://www.uni-regensburg.de/EDV/kurs_info/brf09510/hpc/openMP/bitonicomp.c
OpenMP-Standard:
TTH-Seite: