IN KÜRZE
Schwierigkeit
Mittel
Benötigt
–
Dokumentation
Allgemein
Ein Cluster kann nur dann effektiv genutzt werden, wenn auf ihm viele Aufgaben parallel laufen können. Das ist leicht möglich, wenn viele kleine unabhängige Probleme gelöst werden müssen (embarassingly parallel). Muss allerdings ein einzelnes großes Problem mit vielen Daten, die voneinander abhängen, gelöst werden, muss bei der Entwicklung der Software ein großer Aufwand in die Parallelisierung gesteckt werden.
Parallelität bei einem Programm bedeutet, dass es mehrere Aufgaben gleichzeitig ausführen kann.
Parallelisierung von Software erfordert Fachwissen, das mit dieser Website alleine nicht im vollen Umfang vermittelt werden kann. Es werden aber hier ein paar grundlegende Konzepte und Begriffe vorgestellt, die Ihnen bei der Entwicklung von parallelen Programmen, der Parallelisierung von bestehender Software sowie bei der Optimierung einen ersten Anhaltspunkt geben sollen.
Das ZIMT bietet Angehörigen der Uni Siegen Unterstützung bei der Parallelisierung und Optimierung ihrer wissenschaftlichen Software an. Um eine Beratung zu vereinbaren, können Sie eine E-Mail an hpc-support@uni-siegen.de schicken oder in unsere Sprechstunde kommen.
Begriffe zum parallelen Programmieren
Im High Performance Computing (HPC) wird viel wissenschaftliche Software von den Wissenschaftlerinnen und Wissenschaftlern selbst geschrieben. Wenn Sie parallele Software selbst schreiben müssen, sind hier ein paar Grundbegriffe, die Ihnen als Anhaltspunkt dienen können.
Task- und Daten-Parallelismus
Werden mehrere Operationen gleichzeitig ausgeführt, spricht man von Task-Parallelismus. Wird dieselbe Operation auf viele Daten gleichzeitig angewendet, spricht man von Daten-Parallelismus. Im wissenschaftlichen Rechnen ist vor allem letzteres häufig, beispielsweise wenn die Bewegung von vielen Partikeln berechnet werden muss.
Prozesse und Threads
Wie auch auf der Seite über Linux-Grundlagen erläutert, laufen in Linux viele verschiedene Prozesse gleichzeitig. Allerdings kann ein einzelner Prozess auch mehrere sogenannte Threads starten, die Aufgaben gleichzeitig ausführen.
Shared und Distributed Memory
Man spricht von Shared-Memory-Parallelisierung, wenn die parallel laufenden Operationen auf denselben Arbeitsspeicher zugreifen. Da auf dem OMNI-Cluster jeder Knoten seinen eigenen Arbeitsspeicher hat, bedeutet Shared Memory, dass ein Prozess auf einem normalen Compute-Knoten mit bis zu 64 Threads gestartet werden kann (einer pro CPU-Kern des Knotens) und das Programm auf diesen einen Knoten und dessen Arbeitsspeicher beschränkt ist.
Wenn dies nicht ausreicht, ist eine Distributed-Memory-Parallelisierung notwendig. Bei einer solchen kann für jede parallele Aufgabe jeweils mindestens ein Prozess gestartet werden und jeder Prozess hat seinen eigenen zugewiesenen Arbeitsspeicher. Der Vorteil ist, dass diese Prozesse nicht zwangsläufig auf demselben Knoten sein müssen. Zu den Herausforderungen der Parallelisierung kommt noch hinzu, dass nun bestimmt werden muss, wann Prozesse welche Daten untereinander austauschen.
Die beiden Varianten können auch kombiniert werden, dann spricht man von hybrider Parallelisierung.
Programmiersprachen und Software
Die meisten Programmiersprachen unterstützen Parallelität in irgendeiner Weise, aber nicht alle legen gleich viel Gewicht auf komfortables paralleles Programmieren. Außerdem haben in vielen Sprachen die einzelnen Operationen einen großen Overhead, das heißt es müssen zusätzlich zu der vom Nutzer gewünschten Operation (beispielsweise Addition zweier Arrays) viele zusätzliche Operationen durchgeführt werden (z.B. Anlegen von Objekten) oder zusätzliche Informationen im Arbeitsspeicher abgelegt werden (z.B. Objekt-Metadaten). In der Regel werden deshalb im HPC-Bereich für performance-kritische Probleme eher vergleichsweise systemnahe Sprachen wie C oder Fortran verwendet, statt Sprachen mit hoher Abstraktion wie z.B. Python oder MATLAB (allerdings kommen auch Python und MATLAB im HPC zum Einsatz, wenn Einfachheit der Programmierung wichtiger ist). Als Faustregel lässt sich sagen, dass ein Fortran- oder C-Programm potenziell um zwei Größenordnungen schneller laufen kann als ein algorithmisch gleiches Python-Programm (“potenziell” deshalb, weil das Programm so geschrieben sein muss, dass es diesen Vorteil auch ausnutzt). Gerade Fortran ist deshalb im HPC-Bereich noch recht beliebt, obwohl es in vielen anderen Bereichen nicht mehr verwendet wird.
Es gibt zwei besonders wichtige Softwaretools für parallele Programme, MPI und OpenMP. Beide sind in Form von Bibliotheken verfügbar. Sie sind die am weitesten verbreiteten Parallelisierungsmethoden im wissenschaftlichen Rechnen. Sie werden insbesondere bei der Programmierung in C/C++ und Fortran verwendet, es gibt aber auch Interfaces zu vielen andere Sprachen (z.B. mpi4py für Python).
MPI
MPI steht für Message Passing Interface und ist ein Standard für Distributed-Memory-Parallelisierung. Es gibt mehrere Implementierungen des Standards, die gängigsten sind Open MPI (nicht zu verwechseln mit OpenMP) und Intel MPI, die beide auch auf dem Cluster installiert sind. MPI enthält eine Reihe von Funktionen, mit denen auf verschiedene Arten Daten zu anderen Prozessen kommuniziert werden können. Beispielsweise kann eine MPI_Send-Funktion Daten gezielt von einem zu einem anderen Prozess schicken, während ein MPI_Scatter Daten auf alle Prozesse verteilt. Die Schwierigkeit besteht darin, dass Sie als Entwickler entscheiden müssen, welche Information zu welchem Zeitpunkt kommuniziert wird. Eine allgemeine Einführung zu MPI in PDF-Form finden Sie hier.
OpenMP
OpenMP (MP steht für Multi-Processing) ist eine Programmierschnittstelle für Programme, die mehrere Threads nutzen (Shared-Memory-Parallelisierung). OpenMP existiert ebenfalls für C und Fortran, in beiden Fällen werden parallele Aufgaben im Code mittels Präprozessor-Direktiven gekennzeichnet, beispielsweise wird über einer for-Schleife #pragma omp parallel for (am Beispiel von C) eingefügt und diese Schleife dann parallel ausgeführt. OpenMP ist im Allgemeinen etwas leichter zu erlernen und schneller zu implementieren als MPI. Eine Einführung zu OpenMP befindet sich hier.
Optimierung und Effizienz
Beim Optimieren von Software sollte immer die Regel „keine Optimierung ohne vorherige Performance-Messung“ beachtet werden. Wenn Ihre Software zu lange läuft oder zu viel RAM benötigt, sollten Sie als erstes feststellen, wo im Code dies passiert. Es gibt einige Tools zur Performance-Messung, auch als „Profiler“ bezeichnet, zum Beispiel gprof, TAU oder Scalasca. Das erste ist ein allgemeines und oft eingesetztes Tool, während die anderen beiden auf HPC-Zwecke spezialisiert sind. Alle drei sind auf dem Cluster verfügbar.
Alle bisher genannten Überlegungen gelten für die sogenannte serielle Effizienz, d.h. die Effizienz eines einzelnen Prozesses. Im Gegensatz dazu beschreibt der Begriff parallele Effizienz ein Maß dafür, wie gut Software parallelisiert ist. Ein Programm, bei dem einer der Prozesse sehr viel Arbeit hat und die anderen im Leerlauf sind, wäre ein Beispiel für ein Problem mit der parallelen Effizienz. Wenn Sie Software optimieren, wird empfohlen, sich die serielle Effizienz zuerst anzusehen.
Hier sind einige Sachen, die Sie im Zusammenhang mit serieller Effizienz eventuell beachten müssen:
- Overhead: Wie oben beschrieben könnte ein Prozess zusätzliche Aufgaben erhalten, die nicht sofort offensichtlich sind. Erst wenn Sie Ihren Code profilieren, wird klarer, welche Zeit wofür verwendet wird.
- Skalierung: Zusätzlich zur Anzahl der Operationen, die für jeden Datenpunkt in Ihrer Rechnung notwendig sind, müssen Sie auch darauf achten, wie die Gesamtzahl an Operationen von der Anzahl der Datenpunkte abhängt. Wenn Sie zum Beispiel eine Matrix für Ihre N Datenpunkte erzeugen müssen, dann müssen N * N Operationen durchgeführt werden, um sie mit Zahlenwerten zu befüllen. Mit anderen Worten, egal wie simpel diese N * N Operationen sind, allein die Tatsache, dass Sie 4 mal so viele für ein doppelt so großes N durchführen müssen, beeinflusst Ihre Performance. Je größer Ihr N, desto mehr müssen Sie über die Skalierung nachdenken. Dies nennt man auch die algorithmische Komplexität. Zum Beispiel nennt man einen Algorithmus, der N Quadrat Operationen durchführen muss, einen Algorithmus mit Komplexität zweiter Ordnung.
- Cache-Größe: Moderne CPUs laden Daten vom Arbeitsspeicher (RAM) in kleinere Zwischenspeicher, die Caches genannt werden. Dieses Laden, sowie das Zurückschreiben der Daten in den RAM, benötigen Zeit. Je mehr Operationen durchgeführt werden, ohne Daten in den Cache oder aus diesem zu transportieren, desto effizienter das Programm.
Hier sind einige Sachen, die Sie im Kontext der Parallelität und der parallelen Effizienz beachten müssen:
- Lastbalance: Je länger einige Ihrer Prozesse/Threads auf andere warten müssen. Desto weniger effizient ist Ihr Code.
- Deadlocks: Es ist möglich, insbesondere bei MPI-Kommunikation, dass ein Code auf ewig hängenbleibt, weil alle Prozesse aufeinander warten.
- Race Conditions: Der Begriff Race Condition beschreibt eine Situation, wo dieselben Daten von mehreren Prozessen/Threads geschrieben oder gelesen werden, ohne dass diese Prozesse sich untereinander koordinieren. In so einem Fall verändert die vom Zufall bestimmte Reihenfolge, in der die Prozesse auf die Daten zugreifen, das Endresultat und kann sehr schwer detektierbare Fehler erzeugen.
Diese Liste ist keineswegs vollständig.
