Programme parallelisieren


Parallele Programmierung

Damit ein Programm mehrere CPU-Kerne oder sogar mehrere Computer (auf dem Cluster als "Nodes", also Knoten bezeichnet) eines Clusters gleichzeitig nutzen kann, muss dieses Verhalten im Quellcode des Programms implementiert sein. Man sagt, dass Programm muss "parallelisiert" worden sein, um mehrere Ressourcen parallel nutzen zu können.

In den meisten Programmiersprachen wird die Parallelisierung mit gemeinsamem Speicher (shared memory) vom verteilten Rechnen (distributed memory) getrennt betrachtet. Das Programm nutzt also entweder mehrere CPU-Kerne gleichzeitig oder mehrere Nodes gleichzeitig. Es ist auch möglich beides im selben Programm zu realisieren.

Um in einem Programm überhaupt mehrere Aufgaben gleichzeitig, also parallel abarbeiten zu können, muss das Problem in Teilaufgaben, sogenannte "Tasks" zerlegt werden. Sollten zum Beispiel alle Iterationen einer for-Schleife in beliebiger Reihenfolge abarbeitbar sein, ist es eine gute Idee die Iterationen als einzelne Tasks aufzufassen, welche voneinander unabhängig parallel abgearbeitet werden können. Um den Programmablauf zu beschleunigen sollte natürlich gerade in den Teilen des Programms nach Parallelisierungsmöglichkeiten gesucht werden, welche eine hohe Laufzeit haben.

Unser Workload-Manager "Slurm" bezeichnet das Aufteilen des Programms auf verschiedene Nodes als Zerlegen in "Tasks". So gibt --ntasks indirekt die Anzahl der zu nutzenden Nodes an. Um anzugeben wie viele Teilprobleme nun auf jedem Node parallel abgearbeitet werden sollen, kann --cpus-per-task oder auch --tasks-per-node verwendet werden.

Bei Problemen mit parallelisiertem Quellcode sowie Performanceproblemen können Sie sich unter Kontakt melden.


Programme die mehrere Nodes nutzen

Beim verteilten Rechnen kommunizieren die einzelnen vernetzten Nodes über Nachrichten miteinander. Klassisch ist hierbei das auf dem Linux-Cluster in verschiedenen Implementierungen nutzbare Programmiersystem MPI (Message Passing Interface), welches Nachrichtenaustausch zwischen mehreren gestarteten Prozessen ermöglicht.

Da ein MPI Prozess nicht direkt auf die Daten eines anderen MPI Prozesses auf einen anderen Knoten zugreifen kann, sondern sich diese schicken lassen muss, spricht man in diesem Zusammenhang von einem Programmiersystem mit "distributed memory".

Nach oben


Programme die mehrere CPU-Kerne nutzen

Zur Parallelisierung von Berechnungen innerhalb eines Nodes sollten statt MPI Programmiersysteme wie OpenMP (Open Multi-Processing), pthreads (POSIX-Threads) oder Java Threads (heute Java Concurrency) eingesetzt werden, welche die Parallelisierung mittels Threads ermöglichen. Threads sind Teile eines Prozesses, welche vom Betriebssystem gleichzeitig bearbeitet werden können. Threads bearbeiten Tasks, welche wieder "Teilprobleme" der vom Programm zu erfüllenden Aufgabe darstellen.

Threads können direkt auf den Speicher von anderen Threads zugreifen, was sehr viel schneller geht, als sich diese Daten bei einem Programmiersystem wie MPI als Nachrichten zuzusenden. Man spricht in diesem Zusammenhang von "shared memory".

Nach oben


Programme die "hybrid" mehrere Nodes und auf diesen mehrere CPUs nutzen

MPI unterstützt zwar nur die Verteilung von Berechnungen auf Prozesse, jedoch können auf einem Node mehrere Prozesse gestartet werden. Es ist also prinzipiell möglich, mit MPI mehrere Nodes und in diesen Nodes gleichzeitig mehrere CPUs zu nutzen. Der Vorteil ist hierbei, dass kein weiteres Programmierkonstrukt implementiert werden muss, was das Programmieren natürlich erleichtert.

Damit ein Programm besonders effizient arbeiten kann, sollte einer der oben genannten Programmiersprachen, welche mit shared memory arbeiten, mit MPI kombiniert werden, wobei MPI dann nur für die knotenübergreifende Kommunikation genutzt wird.

Nach oben


NUMA

Bei allen Nodes des Linux-Clusters handelt es sich um NUMA-Systeme. NUMA steht für "Non-Uniform Memory Access". Das bedeutet, dass es mehrere CPUs in jedem Knoten gibt, wobei jede seinen eigenen Arbeitsspeicher erhält. In den meisten Fällen sind im Linux-Cluster 2 physikalische CPUs (=Sockets) auf einem Mainboard verbaut, welche wiederum eine bestimmte Anzahl an Kernen haben.

Befindet sich ein Thread auf einer CPU und benötigt Daten aus dem Arbeitsspeicher der anderen CPU, ist der Zugriff problemlos möglich, dauert jedoch länger, als wenn die Daten im Arbeitsspeicher der anfragenden CPU gelegen hätten.

Will man ein Programm so weit optimieren, dass auch NUMA behandelt wird, ist folgendes zu beachten: Meist gilt die sogenannte "first-touch policy". Das bedeutet, dass die Daten erst bei ihrem ersten Zugriff im entsprechenden Arbeitsspeicher platziert werden. Die Konsequenz daraus ist, dass Daten wie Arrays möglichst von dem Thread angelegt und initialisiert werden sollten, der sie später bearbeitet und nicht von einem Master-Thread.

Normal ist es dem Betriebssystem erlaubt, Threads zwischen CPU-Kernen hin und her wechseln zu lassen. Wird dabei sogar der Socket gewechselt, werden die Threads von "ihren Daten" entfernt. Der Programmierer kann die sogenannte "Thread Affinity" einstellen und damit Threads exakt an bestimmte CPU-Kerne binden. Er kann also dafür sorgen, das Threads die auf den gleichen Daten arbeiten auch bei der gleichen CPU liegen und so den gleichen Arbeitsspeicher (mit schnellem Zugriff) teilen.

Nach oben