Shared Memory mit OpenMP#

Bei Shared Memory Systemen haben alle Prozessoren/Kerne Zugriff auf einen gemeinsamen Speicher.

_images/sharedmemory.svg — Fig. 1 Shared Memory Architektur#

Der gemeinsame Speicher ermöglicht das parallele Programmiermodell “Threading”. Dabei erhält ein Prozess (= ein Programm in Ausführung) mehrere Ausführungsstränge - die sogenannten Threads. Die Threads können parallel auf mehreren Prozessorkernen gleichzeitig ausgeführt werden oder auch zeitlich versetzt aber verwoben auf einem Kern. Alle Threads teilen sich den gleichen Programmcode und die gleichen globalen Daten. Jeder Thread hat jedoch seinen eigenen Zustand bestehend aus:

Instruction Pointer: zeigt auf die Stelle im Code, die dieser Thread als nächstes ausführt. Das heißt die Threads können unterschiedliche Code-Teile ausführen, z.B. ein Thread lädt Daten während ein anderer eine Berechnung durchführt
Stack Pointer: zeigt auf die Stelle im Hauptspeicher, der vom Thread als Stack benutzt wird. Die Stacks der Threads sind überschneidungsfrei. Hier werden lokale Variablen, Funktionsparameter und Rücksprungadressen abgespeichert. Das heißt zwei Threads können gleichzeitig die gleiche Funktion ausführen aber mit unterschiedlichen Werten und am Ende zu unterschiedlichen Stellen zurückspringen
Register File: keine Datei auf der Festplatte sondern eine Bezeichnung für alle Register in einem Prozessorkern. Die folgende Abbildung illustriert die gemeinsamen und getrennten Ressourcen.

_images/threadsspeicher.svg — Fig. 2 Threads mit geteiltem Speicher#

Die Kommunikationen zwischen den Threads erfolgt überlicherweise implizit indem die Threads auf die gleichen Speicherbereiche zugreifen. Dabei kann es zu Race Conditions kommen: das Verhalten des Programms ist von der zeitlichen Reihenfolge der Zugriffe aus unterschiedlichen Threads abhängig. Das Verhalten wird hiermit unvorhersehbar. Ein einfaches Beispiel:

Die globale Variable x hat den Wert 1
Thread A liest die Variable x aus und gibt den Wert auf dem Bildschirm aus
Thread B liest die Variable x aus, erhöht sie um eins und schreibt sie wieder in den Hauptspeicher
Thread C schreibt den Wert 5 in die Variable 1 Auch wenn wir die Threads A, B, C benannt haben gibt es keine vordefinierte Reihenfolge wie sie ausgeführt werden. Mögliche Ergebnisse für die Bildschirmausgabe sind u.a.:
“1”: Thread A wird zuerst ausgeführt, dann B und C oder C und B
“2”: Thread B, Thread A, Thread C (Thread B zur Hälfte, Thread C, Thread B zur 2. Hälfte, Thread A)
“5”: Thread C, Thread A, Thread B oder Thread B, Thread C, Thread A
“6”: Thread C, Thread B, Thread A

Um solche Race Conditions zu verhinden müssen die Zugriffe synchronisiert werden. Dies bedeutet das die Zugriffe in wohl definierte Reihenfolgen gebracht werden. Möglichkeiten zur Synchronisation werden wir weiter unten besprechen. Generell bedeutet Synchronisation aber, dass Threads ab und an warten müssen bis sie weitermachen dürfen. Dabei kann es zu Performanceverlusten kommen und zum Deadlock: Thread A wartet auf Thread B und Thread B wartet auf Thread A - es kommt zum Stillstand.

Eine weitere Schwierigkeit bei Shared Memory Systemen ist, dass die einzelnen Prozessoren und Prozessorkerne typischerweise eigene Caches haben und diese konsistent gehalten werden müssen.

Die manuelle Erstellung von Thread z.B. in Java mit new Thread(...).start() oder in C mit der pthreads Bibliothek ist sehr flexibel aber bietet damit auch sehr viele Möglichkeiten Fehler zu machen insbesondere beim Thema Synchronisation. In diesem Kapitel werden wir betrachten wie OpenMP auf gängige Threadingmuster setzt, die dann mit weniger Fehlermöglichkeiten genutzt werden können. In Java stehen mittlerweile auch einige Higher-Level-Threadingmodelle wie z.B. Fork-Join zur Verfügung, die viele Fehlerquellen vermeiden.

OpenMP: Übersicht#

OpenMP (Open Specification for Multi Processing) ist eine Spezifikation für die Programmierung von Shared Memory Systemen mit Threads. Die Spezifikation wird von einer non-profit Organisation verwaltet. OpenMP hat das Ziel die Programmierung zu vereinfachen indem es gängige Parallelisierungsmuster anbietet.

Die Programmierschnittstelle von OpenMP steht für C, C++ und Fortran zur Verfügung und besteht aus:

Compiler-Direktiven (#pragmas in C), um parallele Regionen und deren Eigenschaften zu definieren
Funktionen (#include <omp.h>), z.B. um rauszufinden in welchem Thread man sich befindet
Umgebungsvariablen, z.B. um die Anzahl der Threads auszulesen/zu verändern

Die Spezifikation ist über die Versionen immer komplexer geworden aber viele Anwendungen (und wir) nutzen nur einen übersichtlichen Kern. OpenMP ist portabel, da es von vielen Compilern auf unterschiedlichen Plattformen unterstützt wird.

Die Grundidee von OpenMP ist, dass das Programm in sequenzielle und parallele Abschnitte aufgeteilt wird und welche Code-Teile/Daten in welcher Art synchronisiert werden müssen. Der Compiler kümmert sich dann, um die Erstellung von Threads, die Zuweisung von Arbeit an die Threads und die Synchronisation.

Das Ausführungsmodell ist in der folgenden Abbildung dargestellt:

_images/forkjoin.svg — Fig. 3 Fork-Join-Modell OpenMP#

Die sequenziellen Programmteile werden in einem Hauptthread ausgeführt. Wenn ein paralleler Abschnitt kommt wird das Programm “geforked” - die Wege des Programms gabeln sich und alle Wege werden in parallelen Threads ausgeführt. Mit etwas Fantasie erkennt man auch in der Abbildung am Anfang der parallelen Region eine Gabel. Am Ende der parallelen Region kommt es zum “join” und die Wege werden wieder vereint.

Ein Beispielprogramm, das die Funktion omp_get_thread_num() verwendet um die ID des aktuellen Threads zu bestimmen:

// Include-Datei für OpenMP:
#include <omp.h>
#include <stdio.h>

int main()
{
    // Ganz normal sequenzieller Code:
    printf("Hello\n");
    // Nun kommt ein paralleler Abschnitt:
    #pragma omp parallel
    {
        printf("World from %i\n", omp_get_thread_num());
    }
    // Paralleler Abschnitt zu Ende, nun wieder sequenziell:
    printf("Done");
}

Bei der Übersetzung muss dem Compiler meist ein OpenMP-Parameter übergeben werden, z.B. gcc -fopenmp helloworld.c. Der Output auf einem 4-Kern-System (es werden standardmäßig so viele Threads erzeugt, wie es Kerne gibt) wäre z.B.:

Hello
World 1
World 4
World 0
World 2
Done

Die Reihenfolge der “World”s ist nicht definiert. Hierfür haben wir keine Angaben im Quelltext gemacht. Jedoch sorgt OpenMP für Synchronisierung: das “Hello” kommt vor und das “Done” nach allen “World”s. Hierfür erzeugt OpenMP implizit eine “Barrier” am Ende des parallelen Abschnitt, d.h. es geht erst weiter, wenn alle Threads den parallelen Abschnitt durchlaufen haben.

Die Direktiven in Form von #pragmas werden von Compilern, die kein OpenMP verstehen einfach ignoriert. Damit kann das Programm auch sequenziell kompiliert und ausgeführt werden. Durch das Einbauen neuer paralleler Abschnitte kann das Programm nach und nach parallelisiert werden.

Wir betrachten die folgenden Direktiven/Programmiermodelle:

Parallele Regionen (#pragma omp parallel)
Parallelisierte For-Schleifen (#pragma omp parallel for)
Sections (#pragma omp sections)

Dabei betrachten wir auch:

Speichermodelle für Variablen - wie werden diese von Threads geteilt
Manuelle Synchronisation

Der Reference Guide OpenMP enthält alle Direktiven und deren Parameter, die wir nicht im Detail durchgehen.

Parallele Regionen#

Die Nutzung von parallelen Regionen haben wir bereits im Hello World Beispiel gesehen. Die Arbeitsaufteilung muss manuell vorgenommen werden. Dies ist besonders einfach bei unabhängigen Arbeitssträngen, z.B. eine Monte-Carlo-Simulation, wo das Ergebnis als Durchschnitt einer großen Zahl von unabhängigen Simulation ausgehend von zufälligen Startpunkten berechnet wird:

#define DURCHLAEUFE 1024
int main()
{
    int durchlaufe_pro_thread = DURCHLAEUFE / omp_get_num_threads();
    double total_result = 0.0;
    #pragma omp parallel
    {
        double result = simulation(rand());
        #pragma omp critical
        total_result += result / DURCHLAEUFE;
    }
    printf("Ergebnis: %f\n", total_result);
}

Wichtig ist die Direktive #pragma omp critical, die dafür sorgt, dass die folgende Zeile als kritischer Abschnitt behandelt wird, d.h. immer nur ein Thread kann die Anweisung zur gleichen Zeit ausführen. Damit wird eine Race Condition vermieden, die zu einem Lost Update führt.

Parallelisierte For-Schleifen#

Mit einfachen parallelen Regionen können z.B. über die Thread ID auch Aufteilungen eines Problems in Unterbereiche gemacht werden. Häufig lässt sich die Aufgabe jedoch sehr einfach als For-Schleife darstellen und das Ziel ist, dass die Durchläufe auf unterschiedliche Threads aufgeteilt werden. Dafür gibt es die #pragma omp parallel for-Direktive.

Betrachten wir beispielsweise die Addition von zwei Vektoren in sequentieller Form:

for(i=0;i<N;i++) { a[i] += b[i]; }

Wenn wir nun mit der einfachen parallelen Region die Schleife auf Threads aufteilen wollen wird es einigermaßen komplex, z.B.:

#pragma omp parallel
{
    int id, i, nthreads;
    id = omp_get_thread_num();
    nthreads = omp_get_num_threads();
    for(i=id; i<N; i += nthreads) {
        a[i] += b[i];
    }
}

Deutlich einfacher geht es mit einer OpenMP-Direktive für For-Schleifen:

#pragma omp parallel
#pragma omp for
for(i=0;i<N;i++) { a[i] += b[i]; }

Hier wird der Indexraum (hier 0 bis N-1) automatisch auf die Threads aufgeteilt. Wie diese Aufteilung zu erfolgen hat kann mit schedule auch genauer angegeben werden. In diesem Falle ist es geschickter als im manuell gestalteten Programm. Dort sind wir immer um nthreads Elemente gesprungen und hatten häufige Cache Misses. Das erklärt die beobachtete Performance bei einer beispielhaften Ausführung mit N = 2^26 auf einem 6-Kern-Prozessor:

Sequenziell: 0.159 Sekunden
Manuell Parallel: 0.076 Sekunden
Parallel for: 0.032 Sekunden

Der vollständige Programmcode ist zu finden unter: https://github.com/sspeiser/hpc-uebungen/tree/main/beispiele/openmp

ÜBUNG: Passwort cracken mit OpenMP

Parallele For-Schleifen mit Reduktion#

Im Beispiel Monte-Carlo-Simulation haben wir eine gemeinsame Variable total_result in allen parallelen Threads aktualisiert. Race Conditions haben wir über eine explizite Synchronisation per kritischen Abschnitt vermieden. Da wir davon ausgehen, dass die Simulation deutlich mehr Zeit verbraucht als das Update von total_result war der Synchronisationsoverhead für uns zu vernachlässigen. Wenn wir nun aber z.B. die Summe über ein großes Array berechnen wollen ist das Update der gemeinsamen Variable sum dominant in der Schleife und der Overhead bei einem kritischen Abschnitt viel zu groß. Z.B. sequenziell:

double sum = 0.0;
for(i=0;i<N;i++) { sum += a[i]; }

Parallel ohne Synchronisation liefert ein falsches Ergebnis - Lost Updates:

sum = 0.0;
#pragma omp parallel for
for(i=0;i<N;i++) {
   sum += a[i];
}

Parallel mit Synchronisation ist viel langsamer als der Sequenzielle Code, da die Berechnung sequenziell läuft aber noch die Koordination über die Threads hinzukommt:

sum = 0.0;
#pragma omp parallel for
for(i=0;i<N;i++) {
    #pragma omp critical
    sum += a[i];
}

Da dies ein häufiges Problem ist gibt es Reductions:

sum = 0.0;
#pragma omp parallel for reduction (+:sum)
for(i=0;i<N;i++) {
    sum += a[i];
}

Hier wird für die Variable sum eine lokale Kopie in jedem Thread angelegt und mit einem “neutralen” Wert für die Operation initialisiert. In unserem Beispiel der Wert 0 für die Operation +. Am Ende werden die lokalen Kopien der Threads und der ursprüngliche Wert vor der Schleife (hier ebenso 0) per Operator zusammengerechnet (hier: addiert). Anbei exemplarische Laufzeiten:

Sequenziell:                   0.158 Sekunden
Parallel ohne Synchronisation: 0.193 Sekunden, falsches Ergebnis
Parallel mit Synchronisation:  5.105 Sekunden
Parallel mit Reduction:        0.025 Sekunden

Neben + gibt es weitere Operatoren, z.B. *, -, min, max, &, | - siehe Reference Guide OpenMP.

OpenMP Sections#

Bisherige Direktiven haben den gleichen Code für unterschiedliche Datenausschnitte auf die Threads verteilt. Mit Sections können wir unterschiedlichen Code in unterschiedlichen Threads ausführen:

double x, y, z, total;
#pragma omp parallel sections
{
    #pragma omp section
    x = berechneX();
    #pragma omp section
    y = berechneY();
    #pragma omp section
    z = berechneZ();
}
total = x + y + z;

Hier werden x, y und z parallel in eigenen Threads berechnet. Die Funktionen können völlig unterschiedlich sein. Am Ende der sections-Direktive ist eine implizite Barrier, d.h. es wird gewartet bis alle Berechnungen fertig sind, dann wir aufaddiert.

Mit Sections können auch rekursive Programme parallelisiert werden, z.B.:

void quicksort(float *a, int start, int ende)
{
    int teiler = teile(a, start, ende);
    #pragma omp parallel sections
    {
        #pragma omp section
        quicksort(a, start, teiler - 1);
        #pragma omp section
        quicksort(a, teiler + 1, ende);
    }
}

Synchronisation#

Die einfachste Form der Synchronisation ist die implizite Barrier am Ende von allen parallelen Abschnitten - hier wird gewartet bis alle Threads fertig mit dem Abschnitt sind. Eine Barrier kann explizit in einem Block gesetzt werden mit #pragma omp barrier. Andererseits kann auch eine implizite Barrier deaktiviert werden, wenn nowait hinter eine Direktive gesetzt wird.

Eine weitere Art der Synchronisation kann mit #pragma omp single erreicht werden - hier wird gekennzeichnet, dass der nachfolgende Block nur von einem einzelnen Thread ausgeführt wird.

Kombiniertes Beispiel:

#pragma omp parallel
{
    berechne_teilprobleme();
    #pragma omp barrier
    #pragma omp single
    {
        tausche_daten_zwischen_teilproblemen();
    }
    finalisiere_teilprobleme();
}

Neben dem kritischen Abschnitt (#pragma omp critical), der von jedem Thread nur einzeln ausgeführt wird (also nicht parallel), gibt es die vereinfachte Variante #pragma omp atomic, um nur eine einzelne Lese-/Schreiboperation als kritisch zu markieren.

Low-level Synchronisationsmechanismen wie explizite Locks sind hier nicht Gegenstand aber auch mit OpenMP realisierbar.

Speichermodell#

Standardmäßig sind Variablen, die vor einer parallelen Region deklariert werden, geteilt (shared) von allen Threads und Variablen, die in der Region deklariert werden, privat für jeden Thread. Mit den shared oder private Keywords können diese Standard explizit benannt oder eben auch umgeändert werden. Die Index-Variablen von Schleifen sind immer privat. Bei geteilten Variablen muss auf Synchronisation geachtet werden und ggfs. die Flush-Operation verwendet werden. Flush stellt sicher, dass eine oder alle geteilte Variablen konsistent im Speicher für alle Threads abgelegt werden. Dies ist mit Aufwand verbunden, da - insbesondere durch Caching - nicht immer alle Prozessoren die gleiche Sicht auf den Speicher haben. OpenMP arbeitet mit einem Speichermodell mit schwacher Konsistenz, d.h. es nimmt für eine bessere Performance Inkonsistenzen zwischen Threads in Kauf. Wenn die Konsistenz hergestellt werden muss geschieht dies durch explizites oder implizites Flush (z.B. am Ende einer parallelen Region).

OpenMP und SIMD#

Aktuelle Versionen von OpenMP können For-Schleifen nicht nur auf mehrere Prozessorkerne aufteilen, sondern auch per SIMD parallelisieren. Dies geht denkbar einfach mit der Direktive #pragma omp parallel for simd. Die Kombination ist auch möglich indem man z.B. eine äußere Schleife mit Threads und eine innere mit SIMD parallelisiert.

Grenzen des parallelen Speedups#

Wir haben bereits gesehen:

paralleles Rechnen bringt Komplexität im Code und Synchronisationsprobleme mit sich - auch wenn sich das bei unseren OpenMP-Beispielen in Grenzen hält
das parallele Rechnen häufig durch Speicherzugriffe ausgebremenst wird.

Im Sinne der Komplexitätsreduktion sollte nur so weit optimiert werden, wie es einen Vorteil bringt.

ÜBUNG: Untersuchungen zu CPU und Hauptspeicher als limitierende Faktoren

HPC Skript

Shared Memory mit OpenMP

Contents