OpenMP und inkrementelle Parallelisierung - (article in german)

Dieser Artikel ist erschienen im entwickler magazin - Heft 2.07  - Abdruck mit freundlicher Genehmigung der Zeitschrift: http://derentwickler.de

 

OpenMP und inkrementelle Parallelisierung.

In diesem Artikel wird der inkrementelle OpenMP Ansatz zur Parallelisierung von sequentiellen Programmen vorgestellt. Der Schwerpunkt liegt auf der praktischen Darstellung von einfachen Programmbeispielen und nicht auf der Vollständigkeit der Beschreibung des OpenMP Standards. Das OpenMP Interface ist zu mächtig und vielfältig, um es in einem Artikel beschreiben zu wollen. Das Ziel dieses Artikels ist es, in kurzen Beispielen in die wesentlichen Grundlagen einzuführen.

Dr. Mario Deilmann, Intel GmbH

Einführung 

Wie im ersten Artikel dieser Serie ausführlich beschrieben wurde, bedeutet die Einführung von Mehrprozessorsystemen nur dann einen Performancegewinn, wenn die vorhandene Software angemessen parallelisiert und skaliert. Die verschiedenen parallelen Programmieransätze bieten ganz allgemein die Möglichkeit, ein Programm in einzelne nebenläufige Einheiten oder Programmfäden (Threads) zu zerlegen. Bei der Parallelisierung einer seriellen Anwendung gibt es verschiedene Vorgehensweisen bei der praktischen Umsetzung. Bei Anwendung des inkrementellen Ansatzes werden Schritt für Schritt die rechenintensiven Bereiche einzeln parallelisiert (OpenMP). Diese Methodik steht im Mittelpunkte dieses Artikels. Wie bereits im ersten Artikel zur Programmierung von Multiprozessorsystemen beschrieben, ist der OpenMP Standard das einfachste Modell für die inkrementelle Implementierung eines parallelen Programms. Der OpenMP Standard wird seit 1997 gemeinschaftlich von verschiedenen Compiler- und Hardwareherstellern weiterentwickelt (www.openmp.org). Der Standard, der mittlerweile in der Version 2.5 vorliegt, definiert die Shared-Memory-Programmierung für die Sprachen C/C++ und Fortran. Die Parallelisierung findet bei OpenMP auf Algorithmenebene statt. Dazu definiert der Standard spezielle Compiler-Direktiven, die die zu parallelisierenden Programmteile auf ein Team von Threads verteilen. Das theoretische Modell, das diesem Ansatz zugrunde liegt, ist das Fork/Join Modell (siehe Kasten: Fork-Join Modell). Dabei wird die Zahl der Threads zur Laufzeit automatisch durch die vorhandenen Prozessorkerne bestimmt. Die Parallelisierung mit OpenMP findet auf Bereichs- bzw. Schleifenebene statt. Der OpenMP Standard umfasst Konstrukte für die Verwaltung der Threadvariablen und deren Gültigkeitsbereiche sowie Konstrukte zur Synchronisation. Jede OpenMP Implementierung stellt zudem ein eigenes Application-Programming-Interface (API) zur Verfügung, um das Laufzeitverhalten der OpenMP Programme zu modifizieren. Der entscheidende Vorteil der OpenMP Parallelisierungen ist die Tatsache, dass das serielle Programm zu jeder Zeit erhalten bleibt. Der Nachteil ist, dass stets Teile des Programms seriell bleiben und somit der maximale Speedup durch das Gesetz von Amdahl begrenzt wird. Amdahls Gesetz [1] gibt eine Abschätzung des maximal zu erwartenden Speedups in Abhängigkeit des seriellen Programmteils. Eine gute Einführung in die OpenMP Programmierung findet sich in [2].

Inkrementelle parallele Programmierung mit OpenMP 

Die Motivation der OpenMP Entwickler war es, eine einfache Methode zur Verfügung stellen, um eine Anwendung in parallele Threads zu zerlegen, ohne dass sich die Programmierer um die Handhabung der einzelnen Threads wie erzeugen, synchronisieren und beenden, Gedanken machen müssen. Außerdem sollte es nicht notwendig sein zu spezifizieren, wie viele Threads überhaupt erzeugt werden müssen, um eine sinnvolle Parallelisierung zu gewährleisten. Zu diesem Zwecke wurde ein plattformunabhängiger Satz von Compiler Pragmas, Direktiven, Funktionsaufrufen und Umgebungsvariablen definiert, die den Compiler anweisen, wie und wo die Threads in der Anwendung eingesetzt werden. Ein Fokus liegt dabei auf der Parallelisierung von Schleifen und nebenläufigen Bereichen. Die OpenMP Initiative kommt aus dem Bereich des wissenschaftlichen Höchstleistungsrechnens. Bei dieser Art von Anwendungen wird in der Regel ein Großteil der Arbeit in den verschiedenen Schleifenkonstruktionen erledigt. Die meisten Schleifen können mit OpenMP einfach dadurch parallelisiert werden, dass man ein Pragma vor die Schleife einfügt. Damit bleiben all die komplexen Details des Threadhandlings dem Compiler und der OpenMP Laufzeitumgebung überlassen. Damit bleibt dem Programmierer mehr Zeit um herauszufinden, welche Schleifen überhaupt parallelisiert werden sollen und welche Algorithmen es lohnt umzustrukturieren. Eine sinnvolle Parallelisierung kann auch mit OpenMP dadurch realisiert werden, dass man sich auf die "hotspots“, also die zeitraubenden Bereiche in der Anwendung konzentriert. Die Effizienz und Einfachheit von OpenMP kann man sehr schön am folgenden Beispiel sehen. Die hier betrachtete Schleife wandelt ein 32-Bit RGB (Rot, Grün, Blau) Pixel in ein 8-Bit Graustufenpixel um. Ein einziges Pragma, welches direkt vor die Schleife gesetzt wird, ist alles, was für eine erfolgreiche Parallelisierung erforderlich ist: 

#pragma omp parallel for

for (i=0; i < numPixels; i++)

{

pGrayScaleBitmap[i] = (unsigned BYTE)

(pRGBBitmap[i].red * 0.299 +

pRGBBitmap[i].green * 0.587 +

pRGBBitmap[i].blue * 0.114);

}

 OpenMP und der Compiler

 Die Verwendung der OpenMP Pragmas erfordert einen OpenMP kompatiblen Compiler und threadsichere Bibliotheken. Die allermeisten Compiler unterstützen mittlerweile den OpenMP Standard. Einer der letzten Compiler, der den OpenMP Standard offiziell unterstützten wird, ist der GNU GCC in der Version 4.2 (gcc.gnu.org) mit der freien OpenMP Implementierung GOMP (gcc.gnu.org/projects/gomp). Allerdings gibt es jetzt schon Linux Distributionen, wie Fedora Core 5 mit einem modifizierten GCC 4.1 Compiler, der OpenMP unterstützt. Damit gibt es dann auf fast jeder Plattform einen OpenMP Compiler und die mit OpenMP parallelisierten Programme laufen mit Ausnahme der API Funktionen plattformunabhängig. Eine perfekte Wahl ist der Intel® C/C++ und Fortran Compiler in der Version 9.1. Das Hinzufügen der folgenden Kommandozeilenoption (/Qopenmp für Windows oder -openmp für Linux) oder der entsprechende Checkbutton in der Microsoft/Eclipse IDE weist den Compiler an, die OpenMP Pragmas zu akzeptieren und eine geeignete Anzahl von Threads zu erzeugen. Zu beachten ist, dass die Anzahl der erzeugten Threads der Anzahl von CPU Kernen oder logischen CPU's entspricht, d.h. auf einem Ein-Prozessorkern-System wird nur ein Thread erzeugt. Dieses Verhalten kann allerdings durch Modifikation der Umgebungsvariablen omp_num_threads verändert werden. Wenn Sie dagegen den /Qopenmp Parameter auf der Kommandozeile weglassen, ignoriert der Compiler die OpenMP Pragmas. Dies stellt eine sehr einfache Weise dar, um die serielle Version des Programms zu erzeugen. Ist OpenMP durch den Compiler eingeschaltet, definiert der Compiler die Variable _OPENMP. Mit diese Definition kann dann sehr einfach im Programm geprüft werden, dass OpenMP vorhanden ist:

 

#ifdef _OPENMP

openmp_function();

#endif

 

Zu einem fertigen OpenMP Programm gehört noch die OpenMP Laufzeitbibliothek, die vom Compiler automatisch dazu gelinkt wird. Einen schematischen Aufbau des Zusammenspiels der verschiedenen Komponenten zeigt die Grafik (siehe Kasten: OpenMP Laufzeitumgebung). Die allgemeine Form aller OpenMP Pragmas ist:

 

#pragma omp directive-name [comma delimited optional clauses]

 

Wenn die Zeile nicht mit pragma omp beginnt, handelt es sich nicht um ein OpenMP Pragma. Die vollständige Liste der Pragmas ist in dem OpenMP Standard spezifiziert. Der Intel® C/C++ Compiler 9.1 unterstützt die OpenMP 2.5 Spezifikation. Die vollständige OpenMP 2.5 Spezifikation kann man kostenlos von der OpenMP Website (www.openmp.org) herunter laden.

Die C-Laufzeit Bibliotheken welche threadsicher ausgelegt sind, werden mit der /MD oder /MDd (debugfähige Version) ausgewählt. In der Microsoft IDE werden diese Bibliotheken unter Code-Erzeugung in der Kategorie für die C/C++ Projekt-Einstellungen ausgewählt.

 

Einfache Parallelisierung mit OpenMP

 

Die allgemeine Form des OpenMP Pragmas zur Parallelisierung einer for-Schleife ist:

 

#pragma omp parallel for [comma delimited optional clauses]

 

Betrachtet man die Schleife im ersten Beispiel etwas genauer, stellt man fest, das das Beispiel ein so genanntes worksharing Konstrukt verwendet, um die Arbeit auf die Threads zu verteilen. Wenn das worksharing mit dem for-Konstrukt verwendet wird, wie im Beispiel gezeigt, werden die Wiederholungen der Schleife auf verschiedene Threads verteilt. Die OpenMP Laufzeitumgebung legt fest, wie viele Threads erzeugt, synchronisiert und nach Beendigung des Konstrukts beendet werden müssen.

 

Es gibt allerdings einige Beschränkungen bei der Parallelisierung von Schleifen mit OpenMP:

 

  • Die Schleifenvariable muss vom Typ signed integer sein. Unsigned integer wie DWORD's oder andere Typen sind nicht erlaubt.

  • Der Vergleichsoperator muss in der Form loop_variable <, <=, >, oder >= loop_invariant_integer sein.

  • Der dritte Ausdruck bzw. der Inkrement-Ausdruck muss entweder eine ganze schleifeninvariante Zahl addieren oder subtrahieren.

  • Wenn der Vergleichsoperator < oder <= ist muss die Schleifenvariable bei jeder Iteration inkrementiert und bei einem Vergleichsoperator der Form > oder >= dekrementiert werden.

  • Die Schleife muss ein basic block sein, das bedeutet, dass keine Sprünge vom Inneren der Schleife nach Außen erlaubt sind, mit Ausnahme der exit() Anweisung, die die gesamte Anwendung beendet. Falls goto und/oder break Anweisungen verwendet werden, müssen diese innerhalb der Schleife erfolgen. Das gleiche gilt für Ausnahmebehandlungen so genannte exceptions; diese müssen innerhalb der Schleife gefangen werden.

     

Obgleich diese Beschränkungen ein wenig limitierend klingen, ist es in der Regel doch relativ leicht möglich die Schleifen so zu formulieren, dass man den Bedingungen von OpenMP gerecht wird. Die folgenden Beispiele veranschaulichen, wie einfach dieses OpenMP Pragma eingesetzt werden kann. In der täglichen Programmierpraxis kann es etwas komplexer sein und es müssen ggf. zusätzliche Details beachtet werden, aber die folgenden Beispiele sind trotzdem gut geeignet um zu zeigen, wie einfach Parallelisierung mit OpenMP oft sein kann. Im ersten Beispiel besteht die Aufgabe darin, in einer Schleife die Werte eines Feldes auf den Bereich von 0 bis 255 zu beschränken:

 

/* Limitiere array auf 0 <= x <= 255 */

for (i=0; i < numElements; i++)

{

if (array[i] < 0)

array[i] = 0;

else if (array[i] > 255)

array[i] = 255;

}

 

Um diese Aufgabe zu parallelisieren fügt man das OpenMP Pragma (parallel for)einfach vor den Schleifenanfang ein:

 

#prgama omp parallel for

for (i=0; i < numElements; i++)

{

[...]

}

 

Im zweiten Fall soll die folgende Schleife eine Tabelle mit Quadratwurzel für die Zahlen 0 bis 100 erzeugen. Wenn man sich die Bedingungen für eine OpenMP Parallelisierung anschaut stellt man leicht fest, dass hier eine Bedingung nicht erfüllt ist. Zur Erinnerung: Die Schleifenvariable muss vom Typ signed integer sein

 

double value; roots[100];

for (value = 0.0; value < 100.0; value++)

{

roots[(int)value] = sqrt(value);

}

 

Die Lösung ist aber nicht schwer zu finden, da man dieses Problem leicht umgehen kann, in dem man die Schleifenvariable als Integer definiert. Jetzt braucht man nur noch das OpenMP Pragma einzufügen und voilà, die Schleife ist parallelisiert.

 

int value;

double roots[100];

#pragma omp parallel for

for (value = 0; value < 100; value ++)

{

roots[value] = sqrt((double)value);

}

 

Datenabhängigkeiten und Wettläufe

 

In der Praxis kommt es häufig vor, dass, obwohl eine Schleife alle Bedingungen für eine OpenMP Parallelisierung erfüllt und der Compiler die Schleife erfolgreich parallelisiert hat, es durch die Verwendung derselben Ressourcen (Speicher, Konsole, etc.) von Seiten des Benutzers zu nichtdeterministischem Verhalten kommen kann. In der Regel ist die gemeinsame Benutzung derselben Speicherzelle das Hauptproblem. Diese unzulässigen Datenabhängigkeiten führen zu falschen Ergebnissen. Datenabhängigkeiten bedeuten, dass unterschiedliche Iterationen oder Schleifendurchläufe auf eine gemeinsame Speicherzelle schreibend zugreifen und den Wert der Variablen nichtdeterministisch verändern. Betrachten wir folgendes Beispiel zur Berechnung der Fakultät:

 

/* Vorsicht Datenabhängigkeit! */

/* Jede Iteration schreibt einen Wert den eine andere Iteration liest */

#pragma omp parallel for

for (i=2; i < 10; i++)

{

factorial[i] = i * factorial[i-1];

}

 

Der Compiler kompiliert diese Schleife ohne Probleme, aber das Programm rechnet in der parallelen Version falsch, da mindestens eine der Schleifendurchläufe von einer anderen Iteration datenabhängig ist . Diese Situation wird Wettlauf (engl. race condition) genannt. Gekennzeichnet ist eine race condition durch den Umstand, dass verschiedene Threads auf ein geteiltes Betriebsmittel, wie z.B eine Speicherzelle zugreifen. Der Scheduling-Algorithmus des Betriebssystems entscheidet, wann und in welcher Reihenfolge die Instruktionen der verschiedenen Threads relativ zueinander ausgeführt werden und wann ein Thread eine Zustandsänderung des Speichers vornimmt. Solche Zustandsänderungen sind dann besonders kritisch, wenn mehrere Threads auf die gleiche Speicherzelle zugreifen. Diese Fälle sind in der Praxis unvorhersehbar und oft nicht reproduzierbar, da sie vom zeitabhängigen Verhalten des Schedulers abhängig und somit nichtdeterministisch sind. Um dieses Problem zu umgehen, muss man entweder die Schleife anders hin schreiben oder einen anderen Algorithmus wählen. Das bedeutet also, dass man selbst, wenn ein Programm richtige Ergebnisse liefert, nicht sicher sein kann, dass es keine race condition gibt. Diese Wettläufe können erst durch ganz bestimmte Zustände (anderes Betriebssystem, langsamer Rechner) hervorgerufen werden. Werkzeuge wie der Intel® Thread Checker können helfen, solche Probleme aufzudecken, da sie alle race condition detektieren, nicht nur die, die zur Laufzeit auftreten. Traditionelle Debugger sind für das Auffinden von race conditions unbrauchbar, weil sie einen Thread stoppen und damit die Voraussetzungen für den Wettlauf und das Laufzeitverhalten ändern.

 

Private und gemeinsame Daten mit OpenMP nutzen

 

Fast jede Schleife liest aus oder schreibt in den Speicher und es ist die Aufgabe des Programmierers zu regeln, welche Teile des Speichers von den verschiedenen Threads gemeinsam genutzt werden und welche Bereiche des Speichers für jeden Thread private Daten darstellen. Wenn Daten als shared bezeichnet werden, greifen alle Threads auf diese Speicher zu. Bei private deklarierten Daten bekommt jeder Thread eine eigene Kopie. Nachdem der Gültigkeitsbereich von OpenMP beendet ist, werden alle privaten Kopien zerstört. Standardmäßig ist jede Variable als shared deklariert. Eine Ausnahme bildet die Laufvariable der Schleife, welche sinnvollerweise natürlich immer private deklariert ist. Man kann auf folgende Weise Variablen bzw. Speicher als private deklarieren:

 

  • Durch Deklaration der Variable innerhalb des OpenMP parallel Ausdrucks

  • Durch Spezifizierung als private in der OpenMP Klausel.

 

Die folgende Schleife liefert ein falsches Ergebnis, da die Variable temp nicht private deklariert wurde und die verschiedenen Threads nichtdeterministisch schreibend auf diese Speicherzelle zugreifen.

 

#pragma omp parallel for

for (i=0; i < 100; i++)

{

temp = array[i];

array[i] = do_something(temp);

}

 

Es gibt wie bereits angedeutet zwei Möglichkeiten, diesen Fehler zu umgehen. Beide Möglichkeiten sind in den folgend Beispielen dargestellt:

 

#pragma omp parallel for

for (i=0; i < 100; i++)

{

int temp; /* Variable innerhalb der Schleife deklariert */

temp = array[i];

array[i] = do_something(temp);

}

 

/* Variable temp im OpenMP statement als private deklariert */

#pragma omp parallel for private(temp)

for (i=0; i < 100; i++)

{

temp = array[i];

array[i] = do_something(temp);

}

 

Bei der Parallelisierung mit OpenMP ist also anzuraten darauf zu achten, wie auf den gemeinsamen Speicher zugegriffen wird. Das betrifft natürlich auch Funktionen, die innerhalb der Schleife aufgerufen werden. Eine Besonderheit ist die Verwendung des Schlüsselwortes static bei der Deklaration von Variablen. Die mit static deklarierten Variablen sind immer shared, da sie nicht auf dem Stack abgelegt werden.

 

Verwendung von Reduktionen

 

Die Akkumulation einer Variablen in Schleifen wird sehr häufig verwendet. Da dieses Vorgehen standardmäßig zu einer race condition führt, da die akkumulierte Variable gleichzeitig von den verschiedenen Threads beschrieben wird, gibt es einen speziellen OpenMP Ausdruck, um dieses Problem zu vermeiden. Sieht man sich die folgende Schleife etwas genauer an, die das Skalarprodukt (dot product) berechnet ,fällt sofort auf, dass über die Variable dot akkumuliert wird. Die Variable muss shared deklariert sein, um das richtige Ergebnis zu erzielen, aber private um die race condition zu vermeiden:

 

float DotProduct (float *a, float *b, int N)

{

float dot = 0.0;

for (int i = 0; i < N; i++)

{

dot += a[i] * b[i];

}

return dot;

}

 

Um dieses Problem zu umgehen, verwendet man den OpenMP Ausdruck für die Reduktion einer Variablen: reduction (operator:list). Durch Angabe der Variable bzw. einer Liste von Variablen und des verwendeten Operators wird das Problem elegant umgangen. Als Operatoren sind in C/C++ folgende mathematische und logische Operationen erlaubt: +, *, -, ^, |, &&, ||. Hier die parallele Funktion zur Berechnung des Skalarprodukts :

 

float DotProduct (float *a, float *b, int N)

{

float dot = 0.0;

 

#pragma omp parallel for reduction(+:sum)

for (int i = 0; i < N; i++)

{

dot += a[i] * b[i];

}

return dot;

}

 

 

Es gibt bei der Reduktion allerdings einige Dinge zu beachten. Die OpenMP Laufzeitumgebung erstellt lokale Kopien der Reduktionsvariablen für jeden Thread . Wenn die Threads beendet werden, werden die einzelnen Kopien zu der globalen Variablen addiert. Da bei den einzelnen Summationen der Threads schon gerundet wird, ist die Gesamtsumme möglicherweise unterschiedlich zu der Summe, die man erhält, wenn man die Reduktionsoperation seriell durchführt, da in diesem Fall nur ein einziges mal gerundet wird.

Lastverteilung bei Schleifeniterationen

 

Da es mitunter vorkommt, dass in den verschiedenen Schleifeniterationen unterschiedlich viel Arbeit zu tun ist, ist es unter diesem Gesichtspunkt ungeschickt, die Iterationen gleichmäßig auf die Threads zu verteilen. Deshalb bietet OpenMP die Möglichkeit, die Verteilung der Iterationen flexibel zu handhaben. Der OpenMP Ausdruck dafür ist:

 

schedule (type[,chunk])

 

Dieser Ausdruck wird an das parallel for angehängt. Standardmäßig ist der Typ schedule (static[,chunk]) eingestellt, d.h. jede Teilschleife besitzt eine Anzahl von chunk Durchläufen. Diese Teilschleifen werden statisch reihum über die Prozesse in der Folge der Prozessnummern verteilt. Dies ist ideal wenn alle Iterationen gleichviel Arbeit zu verrichten haben. Falls chunk nicht spezifiziert ist, gibt es ebenso viele Teilschleifen wie Prozesse. Bei dem Typ schedule (dynamic[,chunk]) werden die Teilschleifen dynamisch über die Prozesse verteilt. Die Iterationen werden in Blöcken der Größe chunk auf die Threads aufgeteilt. Standardmäßig ist der Wert für chunk gleich eins. Dieser Typ ist ideal für einen nicht vorhersehbaren Arbeitsaufwand für die einzelnen Iterationen. Das bedeutet aber natürlich, dass die OpenMP Laufzeitumgebung einen höheren Verwaltungsaufwand betreiben muss. Die letzte Möglichkeit ist, den Typ auf schedule (guided[,chunk])zu setzen, dabei wird die Größe der Teilschleifen von groß nach klein variiert. Die Iterationen werden in Blöcke (chunks) auf die Threads aufgeteilt, deren Größe exponentiell abnimmt. Mit dem Wert von chunk wird die minimale Blockgröße angegeben und ist, wenn nicht anders angegeben, mit eins vorbelegt. Dies ist ein Spezialfall von dynamic, um den zusätzlichen Verwaltungsaufwand zu reduzieren. Mit diesen drei Varianten hat man alle Freiheiten, die Schleifen optimal an die OpenMP Laufzeitumgebung zu übergeben. Wenn man sich nicht sicher ist, ob der gewählte Ansatz optimal ist, kann man mit verschiedenen Werten von chunk experimentieren. Im folgenden Beispiel ist ein Algorithmus zur Berechnung von Primzahlen dargestellt. Da es für große Zahlen immer aufwändiger herauszufinden ist ob diese prim sind, ist es sinnvoll die Last der Iterationen dynamisch zu verteilen:

 

#pragma omp parallel for schedule (dynamic) private (j, limit, prime)

for(i = start; i <= end; i += 2)

{

limit = (int) sqrt((float)i) + 1;

prime = 1;

for ( j=3; (prime && (j <= limit); j+=2 )

if (i%j == 0) prime = 0;

if (prime)

number_of_primes++;

}

 

Parallele Bereiche

 

Bisher haben wir nur die auf Schleifen beschränkte Parallelisierung kennen gelernt, OpenMP beherrscht aber noch eine weitere Konstruktion zur Lastverteilung, um nebenläufige, unabhängige Arbeitslast auf parallele Threads zu verteilen. Die Syntax dieses Konstrukts ist:

 

#pragma omp sections [clause[[,]clause]...] newline

{

[#pragma omp section new-line]

structured-block

[#pragma omp section new-line

structured-block]

...

}

 

Ein einfaches Beispiel für diese Art der Parallelisierung ist folgender Code:

 

#pragma omp parallel

{

#pragma omp for

for (i=0; i<x; i++)

Function0();

 

#pragma omp sections

{

#pragma omp section

{

Function1();

Function2();

Function3();

}

#pragma omp section

{

Function4();

Function5();

}

}

}

Das sections Konstrukt weist OpenMP an, die identifizierten Bereiche über die verschiedenen Threads zu verteilen. In dem obigen Beispiel wird erst eine Schleife auf die vorhandenen Threads verteilt. Ist die Aufgabe beendet, fügt OpenMP am Ende des Blocks einen impliziten Haltepunkt (barrier) ein, um alle Threads zu synchronisieren. Nachdem alle Threads beendet sind, übernimmt der Haupthread (master) die Kontrolle und erreicht das erste section Konstrukt. Jeder Thread bekommt eine section, also einen für die Parallelisierung definierten Bereich, zugeordnet. Gibt es mehr sections als Threads werden die restlichen sections von der OpenMP Laufzeitumgebung verteilt, sobald die ersten Threads mit ihrer Arbeit fertig sind (siehe Kosten: Parallelisierung von unabhängigen Bereichen). Im Gegensatz zu der Lastverteilung bei den Schleifen hat man bei den parallelen Bereichen keinen Einfluss, wie die Arbeit der OpenMP Laufzeitumgebung verteilt wird. Allerdings hat man immer noch die Kontrolle, welche Variablen shared oder private sind. Am Ende des section Ausdrucks gibt es wieder einen impliziten Haltepunkt. Dieses Vorgehensweise ist allerdings nicht immer ideal. Wenn man z.B. wie im obigen Beispiel vier Prozessorkerne hat, werden von der Laufzeitumgebung trotzdem nur zwei Threads erzeugt und zwar je einer pro section. Dies kann bei größeren oder komplexeren Bereichen schon problematisch sein und die Effizienz der Parallelisierung beeinträchtigen.

Compiler API und Intel's task queue Konstrukt

 

Das OpenMP Compiler API wird in der Regel dazu verwendet, das Laufzeitverhalten der OpenMP Programme zu verändern oder Informationen der Laufzeitumgebung zu erfragen (z.B.: Anzahl der Prozessorkerne) oder diese zu manipulieren. Dazu muss die OpenMP Header Datei omp.h eingebunden werden. Es stehen aber auch Funktionen zur Verfügung, die im Standard nicht definiert sind und speziell auf den verwendeten Compiler zugeschnitten sind. Um das im vorigen Abschnitt beschriebene Problem der ungleichen Lastverteilung zu umgehen, gibt es in der Intel® C/C++ Compiler API eine recht sinnvolle Erweiterung, das so genannte task queuing. Durch diese Erweiterung ist es möglich einen Threadpool zur Parallelisierung zu nutzen. Ein Threadpool ist ein Mechanismus, um asynchron arbeitende Threads zentral zu verwalten. Die Abarbeitung der Threads wird dadurch kontrolliert und optimiert. Außerdem wird dadurch eine optimale Priorisierung erreicht. Folgendes Codefragment zeigt, wie die task queuing Erweiterung eingesetzt wird:

 

#pragma intel parallel taskq

{

#pragma intel omp task

Function1();

#pragma intel omp task

Function2();

#pragma intel omp task

Function3();

#pragma intel omp task

Function4();

#pragma intel omp task

Function5();

}

 

Durch diese Erweiterung ist es ausgesprochen einfach, eine optimale Lastverteilung der vorhandenen Prozessorkerne zu erreichen. Allerdings ist die Verwendung dieser API Funktion nicht mehr portabel. Deshalb arbeiten wir bei Intel daran, diese Erweiterung in die nächste Version des OpenMP Standards zu integrieren.

Zusammenfassung

 

Das primäre Ziel der OpenMP Architekten war es, die Programmierer von den zeitaufwändigen, komplexen und fehleranfälligen Details des Threadhandlings zu befreien und die gewonnene Zeit dazu zu benutzen, sich den wichtigeren Bereichen der Parallelisierung zu widmen. Einer der Schlüssel zur Parallelisierung mit OpenMP liegt darin, dass auf sehr einfache und unkomplizierte Weise inkrementell die performancerelevanten Schleifen oder Bereiche auf die vorhandenen Prozessorkerne verteilt werden können, ohne dass man sich um das Erstellen, die Synchronisation und die Beendigung der Threads kümmern muss. Da der zugrunde liegende Mechanismus immer noch auf den Betriebssystem Threads basiert, kommt es auch in OpenMP Programmen zu Datenabhängigkeiten und Wettläufen, da auf gemeinsam genutzte Ressourcen zugegriffen wird. Dieses Problem ist aber allen shared-memory Ansätze eigen. Ich hoffe, dieser Artikel hat Lust gemacht sich mal mit Parallelisierung und OpenMP zu beschäftigen.

 

Alle in diesem Artikel erwähnten Intel-Softwaretools sind bei h.o.-COMPUTER

(www.hocomputer.de/intel) erhältlich.

 

Parallelisierung von unabhängigen Bereichen

 bild5.jpg

 

 bild6.jpg

Fork-Join Modell

 

Die nebenläufige Variante des Verzweigens ist das fork/join. Die Ausführung beginnt mit einem einzigen Prozess (Master). Wenn die OpenMP Laufzeitumgebung ein OpenMP Programm startet und an ein paralleles Konstrukt gelangt, wird ein Gruppe von Threads erzeugt. Fork bedeutet, dass durch paralleles Verzweigen neue nebenläufige Programmfäden aus dem Master Prozess hervorgehen, während der bisher aktive Programmteil weiter läuft. Jedes fork korrespondiert dabei eindeutig mit einem join, bei dem die beiden Zweige wieder zusammengeführt werden und der Master Thread mit der Ausführung fortfährt. Am Ende eines joins werden die Threads von der Laufzeitumgebung synchronisiert, falls nicht anders vorgegeben. Innerhalb einer parallelen Konstruktion können weitere parallele Konstrukte geschachtelt werden (nested parallelism). In diesem Fall wird der Thread, der ein weiteres paralleles Konstrukt enthält, zum Master Thread für diesen Bereich. Auch diese Bereiche können wiederum ein paralleles Konstrukt enthalten usw. siehe Grafik. Diese Art der Parallelisierung generiert komplexe Konstruktionen und Implikationen und wird im Rahmen dieses Artikels nicht behandelt.

 

Das bei OpenMP verwendete Modell für parallele Schleifen ist ein Spezialfall dieses Modells. Wenn die einzelnen Schleifendurchläufe unabhängig voneinander sind, kann statt der n-fachen Wiederholung des Schleifenkörpers eine n-fache Parallelisierung mit Threads stattfinden. Folgende Grafik veranschaulicht dies für das parallel for:

 

 

 

Dr. Mario Deilmann arbeitet seit 2003 als Senior Software Engineer bei der Firma Intel und ist im Bereich des technischen Consulting für den Intel Compiler tätig.

Links & Literatur

[1] Gene Amdahl: Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities, AFIPS Conference Proceedings

[2] Rohit Chandra et. al: Parallel Programming in OpenMP, Morgan Kaufmann

For more complete information about compiler optimizations, see our Optimization Notice.
Tags: