Dualcore-Prozessoren sind längst Standard, Quadcores im Kommen. Mit OpenMP geben Sie ihren Programmen Zugriff auf diese Rechenleistung.

Wer vor kurzem einen neuen Rechner gekauft hat oder wegen eines geplanten Neukaufs momentan die Werbeprospekte durchforstet, der kennt Begriffe wie “Dual Core” und “Quad Core”. Fast alle aktuellen Rechner bringen CPUs mit zwei oder gar vier Prozessorkernen mit – früher ein exklusiver Luxus für teure Server oder Workstations.

Linux kann mit solchen Mehrprozessorsystemen seit langem umgehen, und die Distributoren installieren inzwischen als Standard mehrprozessorfähige SMP-Kernel. Diese schaffen die Grundvoraussetzungen, um die multiplen Cores auch tatsächlich zu nutzen. Aber schafft das auch die Software?

Das Programm top zeigt die Auslastung der CPUs an. Was es in Abbildung 1 zeigt, sieht ja schon ganz gut aus. Xaos, ein Programm zur Berechnung von Fraktalen, belegt 100 Prozent CPU-Leistung. Der Schein trügt jedoch: Der Rechner ist insgesamt nur zu knapp 60 Prozent ausgelastet. Ein Druck auf die Taste [ 1] führt jede CPU separat auf. In diesem Modus (Abbildung 2) erkennt man die Nutzlast der einzelnen Kerne schnell: Eine CPU rechnet brav (90 Prozent Last), die andere dreht Däumchen (0.3 Prozent Last).

top die Gesamtauslastung aller CPUs an …” width=”300″ height=”173″ /> Abbildung 1: In der Vorgabe zeigt top die Gesamtauslastung aller CPUs an …

Abbildung 2: … auf Wunsch aber auch die Auslastung jedes einzelnen Prozessorkerns.

Mehrspurig

Normalerweise arbeitet der Rechner in C/C++ oder sonstigen prozeduralen Programmiersprachen geschriebene Programme sequenziell ab, also einen Befehl nach dem anderen. Das lastet allerdings nur einen Prozessorkern aus. Um die Rechenleistung effizienter zu nutzen, kann man entweder mehrere Programme gleichzeitig ausführen oder ein Programm parallelisieren.

Die seit 1997 gemeinschaftlich von verschiedenen Hardware- und Compilerherstellern entwickelte Programmierschnittstelle OpenMP bietet eine sehr einfache und portable Möglichkeit, Programme in C/C++ und Fortran zu parallelisieren. Das kann die Performance eines Programms deutlich steigern – allerdings nur dann, wenn die CPU wirklich viel rechnen muss und sich die Aufgabe auch tatsächlich parallelisieren lässt. Bei rechenintensiven Problemen ist das jedoch häufig der Fall, denn solche Aufgaben sickern oft aus dem Dunstkreis von Clustern auf den PC, und Cluster-Abarbeitung setzt zwangsläufig Parallelisierung voraus.

Eins, zwei, viele

Mithilfe von OpenMP lassen sich existierende serielle Programme sehr einfach durch die Angabe einiger weniger zusätzlicher Compiler-Direktiven effektiv parallelisieren. Solche Compiler-Direktiven sehen folgendermaßen aus:

#pragma omp Direktivenname [Klauseln]

Compiler ohne OpenMP-Implementation, wie etwa ältere GCC-Versionen vor 4.2, ignorieren diese Compiler-Direktiven schlicht, sodass man den Quelltext weiterhin auch als seriellen Code kompilieren kann:

$ gcc -Wall test.c
test.c: In function 'main':
test.c:12: warning: ignoring #pragma omp parallel

OpenMP-spezifischer Code lässt sich mithilfe der Direktive #ifdef auch bedingt kompilieren, wozu OpenMP das Makro _OPENMP definiert.

Ein OpenMP-Programm startet ganz normal als serielles Programm mit einem Thread. Ein Befehl kommt nach dem nächsten. Das erste OpenMP-Statement, das Sie kennenlernen, dient der Erzeugung mehrerer Threads:

… ein Thread
#pragma omp parallel
{ … viele Threads }
… ein Thread

Abbildung 3 veranschaulicht diese Aufteilung in mehrere Threads und das Wiedervereinigen zu einem einzelnen.

Abbildung 3: Das Fork-Join-Modell von OpenMP.

Arbeitsteilung

Nun haben Sie mehrere Threads erzeugt, momentan tun aber alle noch das selbe. Hier besteht Optimierungspotential, die Arbeit sollen mehrere Threads gleichzeitig erledigen. Dazu gibt es in C zwei Möglichkeiten. In der besonders im Forschungsumfeld beliebten Programmiersprache Fortran existiert noch eine dritte, “Parallel Workshare”.

Die erste Variante, parallele Sektionen, dient dazu, parallel ausführbare Programmbereiche – also Programmcode, der nicht direkt voneinander abhängt – auch tatsächlich parallel auszuführen. Um das zu erreichen erzeugt #pragma omp parallel mehrere Threads. Auf diese Weise lassen sich mehrere unabhängige Programmteile in einzelnen Threads ausführen. Es kann beliebig viele parallele sections geben (Listing 1, Variante 1). Sie dürfen auch die beiden Compilerdirektiven parallel und sections mit #pragma omp parallel sections zu einer zusammenfassen.

Die zweite Variante, parallele for()-Schleifen, dient dazu, Schleifen zu parallelisieren, was vor allem bei rechenintensiven mathematischen Programmen relevant ist (Listing 1, Variante 2). Abbildung 4 zeigt, wie das funktioniert. Auch hier dürfen Sie #pragma omp parallel und #pragma omp for zu #pragma omp parallel for zusammenfassen.

parallel for.” width=”223″ height=”300″ /> Abbildung 4: Eine Schleife mit dem Pragma parallel for.

… /* ein Thread */
#pragma omp parallel /* viele Threads */
{
#pragma omp sections
#pragma omp section
…  /* Programmteil A läuft parallel zu B und C */
#pragma omp section
…  /* Programmteil B läuft parallel zu A und C */
#pragma omp section
… /* Programmteil C läuft parallel zu A und B */
}
… /* ein Thread */

… /* ein Thread */
#pragma omp parallel [Klauseln …]
#pragma omp for [Klauseln …]
for (i=0;i<N;i++) {
    a[i]= i*i; /* parallelisiert */
    }
… /* ein Thread */

Gültigkeitsbereiche

Bei der Shared-Memory-Programmierung können mehrere CPUs auf die selben Variablen zugreifen. Das sorgt für Effizienz und spart Kopierarbeit. In manchen Fällen benötigt allerdings jeder Thread seine eigene Kopie der Variablen – etwa bei den Schleifenvariablen von parallel abgearbeiteten for()-Schleifen.

Bei OpenMP-Direktiven angegebene Klauseln (Tabelle “Klauseln”) legen diese Eigenschaften von Variablen fest. Solche Klauseln hängen Sie an das OpenMP-#pragma an, beispielsweise:

#pragma omp parallel for shared(x, y) private(z)

Irrtümer bei der shared()/private() Deklaration von Variablen zählen zu den häufigsten Fehlerursachen in parallelisierten Programmen.

Reduktion

Inzwischen wissen Sie, wie Sie Threads erzeugen und die Arbeit auf mehrere Threads aufteilen. Was aber, wenn alle Threads an einem Gesamtergebnis arbeiten sollen, etwa, um die Werte eines Arrays aufsummieren? Dazu gibt es die Klausel reduction() (Listing 2).

Der Compiler erzeugt eine lokale Kopie jeder Variable in reduction() und initialisiert diese abhängig vom Operator (beispielsweise 0 für +, 1 für *). Bearbeiten beispielsweise drei Threads je ein Drittel der Schleife, so summiert der Master-Thread am Ende alle Teilsummen auf.

a = 0 ; b = 0 ;
#pragma omp parallel for private(i) shared(x, y, n) reduction(+:a, b)
for (i=0; i<n; i++) {
    a = a + x[i] ;
    b = b + y[i] ;
    }

Wer ist schneller?

Die Fehlersuche in parallelisierten Programmen hält einige Tücken bereit. Besonders schwer lassen sich solche Fehler finden, die in seriellen Programmen gar nicht und auch bei paralleler Abarbeitung nicht immer auftreten. In diese Kategorie fallen so genannte Race Conditions: Mehrere Programmteile laufen parallel, und je nachdem, welcher Thread schneller fertig ist, verändert dies das Ergebnis. Der Code in Listing 3 füllt erst ein Array parallel mit Werten und versucht anschließend, die Summe dieser Werte parallel zu errechnen.

#ifdef _OPENMP
#include <omp.h>
#endif
#include <stdio.h>
int main() {
    double a[1000000];
    int i;
    #pragma omp parallel for
    for (i=0; i<1000000; i++) a[i]=i;
    double summe = 0;
    #pragma omp parallel for shared (summe) private (i)
    for ( i=0; i < 1000000; i++) {
        #pragma omp critical (summierung)
        summe = summe + a[i];
    }
    printf("summe=%lf\n",summe);
}

Ohne das OpenMP-Statement #pragma omp critical (summierung) in Zeile 13 könnte folgendes passieren:

• Thread 1 liest den aktuellen Wert von summe in ein CPU-Register.
• Thread 2 liest den aktuellen Wert von summe in ein CPU-Register.
• Thread 2 addiert a[i+1] zum Wert im Register dazu.
• Thread 2 schreibt den Wert im Register zurück in die Variable summe.
• Thread 1 addiert a[i] zum Wert im Register.
• Thread 1 schreibt den Wert im Register in die Variable summe.

Weil Thread 2 hier Thread 1 überholt und damit quasi das Rennen gewonnen hat, wurde a[i+1] nicht korrekt dazusummiert. Thread 2 berechnet zwar die Summe und schreibt diese auch in die Variable summe, Thread 1 überschreibt sie allerdings sofort wieder mit einem falschen Wert.

Das #pragma omp critical sorgt dafür, dass dies nicht passieren kann: Alle Threads führen den kritischen Code aus, aber nur jeweils einer zu einem Zeitpunkt (siehe Abbildung 5). Daher führt das Beispiel in Listing 3 die Summierung korrekt aus, ohne dass ein parallel laufender Thread dazwischenpfuschen kann.

Für elementare Operationen (beispielsweise i++) gibt es auch noch #pragma omp atomic, das einen Befehl atomar ausführt. Schreibzugriffe auf shared()-Variablen sollten Sie immer mit #pragma omp critical “sichern”.

Abbildung 5: Kritische Regionen werden nicht zeitgleich ausgeführt.

Sind schon alle da?

In manchen Fällen besteht die Notwendigkeit, alle Threads zu synchronisieren. Mit #pragma omp barrier errichten Sie dazu eine virtuelle Barriere: Alle Threads warten, bis auch der letzte von ihnen an der Barriere angekommen ist, erst dann geht es in der Abarbeitung weiter (Abbildung 6). Diese Barrieren sollten Sie mit Bedacht einsetzen, da sie den Leistungsvorteil der parallelen Abarbeitung schmälern – wartende Threads erledigen keine Arbeit. Listing 4 zeigt ein Beispiel, bei dem eine Barriere notwendig ist.

Abbildung 6: Die Threads warten, bis alle an der Barriere angekommen sind.

#pragma omp parallel shared (A, B, C)
{
  Berechnungsfunktion(A,B);
  printf("B wurde aus A berechnet\n");
#pragma omp barrier
  Berechnungsfunktion(B,C);
  printf("C wurde aus B berechnet\n");
}

Die Berechnungsfunktion() kalkuliert aus dem ersten Argument das zweite. Die Argumente könnten hier etwa ganze Arrays sein, die Berechnungsfunktion beispielsweise eine aufwendige mathematische Matrizenoperation. Hier müssen Sie #pragma omp barrier anwenden – ansonsten könnten einige Threads schon mit der zweiten Berechnung anfangen, obwohl andere noch nicht mit der Berechnung der Werte in B fertig sind.

Einige OpenMP-Konstrukte (wie etwa parallel, for, single) beinhalten eine implizite Barriere, die Sie gegebenenfalls durch Anhängen der Klausel nowait explizit deaktivieren, etwa mit #pragma omp for nowait. Weitere Synchronisationsmechanismen sind:

• # pragma omp master {Code}: Code, der nur einmal und nur vom Master-Thread ausgeführt wird.
• # pragma omp single {Code}: Code, der nur einmal – aber nicht unbedingt vom Master Thread – ausgeführt wird
• # pragma omp flush (Variablen): Sorgt für eine konsistente Sicht auf den Speicher durch Zurückschreiben der zwischengespeicherten Variablen vom Cache in den Hauptspeicher.

Bibliotheksfunktionen

OpenMP stellt einige zusätzliche Funktionen zur Verfügung. Einige Beispiele finden Sie in der Tabelle “OpenMP-Funktionen”. Um diese zu nutzen, müssen Sie in C/C++ die Header-Datei omp.h einbinden. Damit sich die Programme auch ohne OpenMP übersetzen lassen, empfiehlt es sich, die betreffenden Stellen mit #ifdef _OPENMP bedingt zu kompilieren:

#ifdef _OPENMP
#include <omp.h>
threads = omp_get_num_threads();
#endif

Mit den Locking-Funktionen “sperrt” ein Thread eine Ressource, indem er sich mit omp_set_lock() exklusiven Zugriff reserviert. Andere Threads können dann mit omp_test_lock() abfragen, ob die Ressource gesperrt ist. Das kommt beispielsweise zum Einsatz, wenn mehrere Threads in eine Datei schreiben sollen, auf die nur jeweils einer Zugriff haben darf. Bei Verwendung der Locking-Funktionen gilt es Vorsicht walten zu lassen, da man sonst leicht einen Deadlock verursacht.

Eine solche gegenseitig Blockierung passiert, wenn Threads Ressourcen benötigen, diese aber überkreuz sperren: Thread 1 hat beispielsweise Ressource A erfolgreich reserviert und wartet, bis er Ressource B verwenden darf, bei Thread 2 ist es genau umgekehrt. Beide Threads kommen dann nicht weiter und warten ewig.

Umgebungsvariablen

Einige Umgebungsvariablen steuern das Laufzeitverhalten von OpenMP-Programmen, die wichtigste davon ist OMP_NUM_THREADS. Sie legt fest, wieviele Threads in parallelen Regionen gleichzeitig rechnen, denn zu viele Threads bremsen die Abarbeitung, statt sie zu beschleunigen. Mit export OMP_NUM_THREADS=1 läuft beispielsweise ein paralleles Programm in der Bash mit nur einem Thread – also wie ein normales serielles Programm.

OpenMP-Praxis

Um OpenMP in eigenen Programmen zu nutzen benötigen Sie einen Rechner mit mehr als einer CPU oder einer Multicore-CPU sowie einen OpenMP-fähigen Compiler. Der GNU-Compiler kennt OpenMP seit Version 4.2, darüberhinaus gibt es für Linux noch den Sun-Compiler (gratis, [2]) und den Intel Compiler (Linux-Version gratis für nichtkommerziellen Einsatz, [3]).

In Listing 5 sehen Sie eine OpenMP-Version des klassischen Hello-World-Programms. Um OpenMP zu aktivieren, verwenden Sie beim Aufruf von GCC die Option -fopenmp. Die Kommandos zum Übersetzen des Programms und die Ausgabe zeigt Listing 6.

# helloworld.c (OpenMP-Version)
#
#ifdef _OPENMP
#include <omp.h>
#endif
#include <stdio.h>
int main(void)
{
  int i;
#pragma omp parallel for
  for (i = 0; i < 4; ++i)
  {
    int id = omp_get_thread_num();
    printf("Hello World from thread %d\n", id);
    if (id==0)
      printf("There are %d threads\n", omp_get_num_threads());
  }
  return 0;
}

$ <b>gcc -Wall -fopenmp helloworld.c<b>
$ <b>export OMP_NUM_THREADS=4<b>
[…]
$ <b>./a.out<b>
Hello World from thread 3
Hello World from thread 0
Hello World from thread 1
Hello World from thread 2
There are 4 threads

Beim Sun-Compiler heisst die entsprechende Compiler-Option -xopenmp, bei Intel -openmp. Intels Compiler informiert sogar den Programmierer, wenn etwas parallelisiert wurde (Listing 7)

$ <b>icc -openmp helloworld.c<b>
helloworld.c(8): (col. 1) remark:
OpenMP DEFINED LOOP WAS PARALLELIZED.

Was bringt’s wirklich?

Als Beispielprogramm, um die Performancesteigerung mit OpenMP zu demonstrieren, berechnen wir in Listing 8 die Kreiszahl Pi [4] mit der Formel von Gregory-Leibniz (siehe Abbildung 7). Dabei handelt es sich bei weitem nicht die effizienteste Methode, um Pi zu berechnen – aber unser Ziel ist nicht Effizienz, sondern die CPUs möglichst lange intensiv auszulasten.

Die for()-Schleife haben wir hier mit OpenMP parallelisiert – und tatsächlich bringt dieses Vorgehen die gewünschte Leistungsoptimierung (Listing 9). Das Programm läuft mit zwei CPUs doppelt so schnell wie mit einer, da sich fast die gesamte Berechnung parallelisieren lässt. Beobachten Sie den Ablauf des Programms mit top, dann sehen Sie, dass zwei CPUs ausgelastet sind und pi-openmmp tatsächlich 200 Prozent CPU-Leistung verbraucht.

Das klappt allerdings nicht bei jeder Aufgabe so schön. Bei anderen Problemstellungen muss häufig ein Teil des Programms seriell laufen, und bei sequenzieller Abarbeitung bringen zusätzliche CPUs nichts: Der Leistungszuwachs fällt dann deutlich geringer aus. Hier kommt das Amdahlsche Gesetz ([5], siehe Kasten “Das Amdahlsche Gesetz”) zum Tragen.

Abbildung 7: Formel zur Berechnung von Pi von Gregor Leibniz.

# pi-openmp.c (Berechnung der Kreiszahl)
#
#include <stdio.h>
#define SCHRITTZAHL 1000000000
int main(int argc, char *argv[])
  {
  long i;
  double pi = 0;
  #pragma omp parallel for reduction(+: pi)
  for (i = 0; i < SCHRITTZAHL; i++) {
    /* pi/4 = 1/1 - 1/3 + 1/5 - 1/7 + …
       um nicht das Vorzeichen ständig wechseln
       zu müssen (s=1; in jedem Schritt s=s*-1),
       summieren wir immer gleich zwei Elemente
       dazu. */
       pi += 1.0/(i*4.0 + 1.0);
       pi -= 1.0/(i*4.0 + 3.0);
  }
  pi = pi * 4.0;
  printf("Pi = %lf\n", pi);
  return 0;
  }

$ <b>gcc -Wall -fopenmp -o pi-openmp pi-openmp.c<b>
$ <b>export OMP_NUM_THREADS=1 ; time ./pi-openmp<b>
Pi = 3.141593
real    0m31.435s
user    0m31.430s
sys     0m0.004s
$ <b>export OMP_NUM_THREADS=2 ; time ./pi-openmp<b>
Pi = 3.141593
real    0m15.792s
user    0m31.414s
sys     0m0.012s

Das Amdahlsche Gesetz

Als “Speedup” bezeichnet man die Beschleunigung eines Programms durch Parallelisierung. Im Idealfall braucht die Programmausführung bei N Prozessoren nur 1/N der Zeit des seriellen Programms. Diesen Idealfall nennt man linearen Speedup. In der Praxis lässt sich ein linearer Speedup häufig nicht erreichen – das liegt an den nicht parallelisierbaren Teilen eines Programms.

Bezeichnet man den Anteil des Programms, der sich parallelisieren lässt, als P (und folglich als (1-P) den nicht parallelisierbaren Teil) sowie die Anzahl der verfügbaren Prozessoren als N, errechnet sich der maximale Speedup nach der Formel in Abbildung 8.

Abbildung 8: Amdahls Gesetz.

Beträgt beispielsweise der serielle Anteil (1-P) des Programms 1/4, kann der Speedup nicht größer ausfallen als 4 – egal, wie viele Prozessoren zum Einsatz kommen.