Paralleles Rechnen

Inhaltsverzeichnis

1 Einleitung

2 Lattice Boltzmann Grundlagen
2.1 Einführung
2.2 Die Lattice Boltzmann Methode

3 Parallelisierungmethoden
3.1 OpenMP
3.1.1 Grundlagen
3.1.2 Vorteile und Nachteile von OpenMP
3.2 MPI
3.2.1 Definition
3.2.2 Message-Passing-Modell
3.2.3 Vorteile und Nachteile von MPI
3.3 GPGPU
3.3.1 Grundlagen
3.3.2 Vor- und Nachteile von GPGPU

4 Parallelisierung von Lattice Boltzmann
4.1 Mit MPI
4.2 Mit OpenMP
4.3 Mit GPGPU

1 Einleitung

Paralleles Rechnen ist die Zusammensetzung der Ergebnisse mehrerer Teilbe­rechnungen zu einem Gesamtergebnis [14]. Es existieren mehrere Gründe wie Z.B. die Ausführungsdauer [10]. Durch das Parallele Rechnen ist es bei Simula­tionen möglich viel Zeit zu sparen und die Ergebnisse schneller zu erhalten. Ein anderer Grund ist die Ressourcenbeschränktheit [14]. Simulationen können die Kapazitäten (z.B. Speicherkapazität) eines einzigen Computers Übertreffen. Um trotzdem die Simulation durchzuführen, könnte man mehrere Computer mitein­ander verbinden. Den letzten Grund den wir erwähnen ist die Komplexe Pro­blemdarstellung [14]. Es gibt Simulationen die so komplex sind, dass um ein Er­gebnis zu erhalten, eine Parallele Bearbeitung die einzige Möglichkeit ist. Paral­leles Rechnen wird in vielen verschiedenen Bereichen wie Z.B. in der Wirtschaft (Big Data, Data Mining...) und in der Forschung (Physik, Mathematik...) verwen­det [5].

2 Lattice Boltzmann Grundlagen

2.1 Einführung

Generell ist es sehr schwierig Gleichungen der Strömungssimulation zu lösen. Um dennoch Ergebnisse zu erhalten, wurden verschiedene Methoden entwickelt wie z.B. die Finite-Differenzen-Methode (FDM), die Spektralmethode oder die Lattice-Boltzmann-Methode. Die Lattice-Boltzmann-Methode basiert im Gegen­Satz zu anderen zu anderen Methoden auf die Lattice-Boltzmann- Gleichung und nicht auf Gleichungen die aus der Strömungsmechanik resultiere [3]. Dadurch ist sie einfacher zu implementieren als andere Methoden. Bei der Lattice-Boltzmann- Methode ist es außerdem nicht notwendig ein Poissongleichung zu lösen, was an sich keine einfache Aufgabe ist. Trotz vieler Vorteile hat die Lattice-Boltzmann- Methode auch Nachteile wie z.b. dass viel Speicherkapazität benutzt wird, oder durch ihre Zeitabhängigkeit ist sie nicht sehr effizient bei der Simulation von ste­tigen Strömungen.[12]

2.2 Die Lattice Boltzmann Methode

Der Raum, in dem die Simulation stattfindet, ist kontinuierlich. Damit die Lattice- Boltzmann-Methode angewendet wird muss dieser Raum erst mal diskretisiert werden [3]. Somit erhalten wir eine begrenzte Anzahl an Gittern und Gitterpunk­te. Die Fluidpartikeln könne sich zwischen benachbarten Gitterknoten bewegen, wie wir im folgenden Beispiel sehen:

Sei der Raum zwei-Dimensional. Für den Punkt 0 haben wir 8 benachbarte Gitterpunkte und somit 8 Bewegungsrichtungen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Darstellung des D2Q9-Modells auf einem Gitterpunkt mit den da­zugehörigen Geschwindigkeiten. Die Nummerierung der Pfeile entspricht der Richtung i.

[3]

Durch Berechnungen auf die wir nicht näher eingehen werden ergibt sich die Lattice-Boltzmann-Gleichung [12]:

Abbildung in dieser Leseprobe nicht enthalten

Ar ist der Zeitschrift, Ci ist die Geschwindigkeit entsprechend der Bewegungs­richtung, Cïj(x,t) ist der Kollisionsoperator, fi(x,t) ist die diskrete Verteilungs­funktion.

Diese Gleichung kann man in zwei Teile zerlegen die jeweils eine Bewegung der Fluidpartikeln definieren:

1. Der Kollisionsschritt in dem die neuen Verteilungsfunktionen ƒ* erzeugt werden anhand des Kollisionsoperator Ω/(/) :

Abbildung in dieser Leseprobe nicht enthalten

Mit T der Relaxionszeit und ff q die Gleichgewichtsfunktion.

2. Dem Strömungsschritt in dem die neuen Verteilungsfunktionen mit den neuen Gitterpunkten und Zeiten identifiziert werden:

Abbildung in dieser Leseprobe nicht enthalten

Die folgende Graphik verdeutlicht dieses Verfahren:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Darstellung der Verteilungen über einen Zeitschritt hinweg für eine Zelle mit ihren Nachbarn.

[3]

Der Kollisionsschritt und der Strömungschritt finden immer nacheinander statt. Der Algorithmus für die Lattice-Boltzmann-Methode ist:

Initialisieren;

for t G to, ...,tn do Randwerte setzten

for X G Ω״ do

- Kollision

Strömung

end

end

Algorithm 1: Pseudocode des Lattice Boltzmann Algorithmus

3 Parallelisierungmethoden

3.1 OpenMP

3.1.1 Grundlagen

ОрепМр steht für ״Open specifications for Multi Processing" und 1997 gemein­schaftlich von verschiedenen Hard-und Softwareherstellern entwickelt worden. Es ist eine Spezifikation für parallele Programmierung auf mehreren Multicore Prozessoren mit einem gemeinsamen Speicher [13]. In einem solchen System wird der Speicher von zwei oder mehrere Prozessoren geteilt. Die folgende Abbildung ist eine typische Darstellung eines solchen Systems:

Gemeinsamer Speicher

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Darstellung eines Systems mit gemeinsamen Speicher.

[13]

Das OpenMP ist ein Programmiermodell dass nach dem Fork-Join-Prinzip funktioniert [13]. Als erstes haben wir ein Thread, der Masterthread genannt wird.Dieser Masterthread wird ausgeführt bis das Programm an einem Bereich ankommt, dass mittels OpenMp parallelisiert werden kann.Der Masterthread wird zu einem Team von Threads umgewandelt. Dieser Vorgang wird als fork be­zeichnet. Der parallele Bereich wird jetzt von dem Masterthread und dem ganzen Team von Threads ausgeführt. Wenn der parallele Bereich zu ende ist wird das Team von Threads synchronisiert und beendet. Nur der Masterthread wird nicht beendet. Dieser Vorgang wird als join bezeichnet. Am Ende des parallelen Be­reichs wir der Mastethread weiter ausgeführt. Es ist zu bemerken dass innerhalb eines parallelen Abschnittes ein anderer entstehen kann.Der Thread der zu die­sen parallelen Abschnitt führt wird zum Masterthread im paralellen Bereich. Die folgende Abbildung verdeutlicht das Fork-join-Prinzip:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4: Darstellung des Fork-Join-Prinzip.

[13]

3.1.2 Vorteile und Nachteile von OpenMP

OpenMP ist ein sehr interessante Paralellisierungmethode weil sie Z.B. die Aus­lastung de CPUs ermöglicht [7].Ausserdem ist sie nur eine Spracherweiterung von c, C++ und Fortan. Ein weiterer Vorteil ist, dass der Quellcode des Pro­gramms nicht geändert werden muss, um auf ein System ausführbar zu sein dass OpenMP nicht unterstützt[13]. Dennoch hat OpenMP viele Nachteil wie Z.B. dass es nur auf Systemen mit gemeinsamen Speicher anwendbar und dies zur ei­ne überschreibung führen kann, weil die Prozessoren um die gleichen Variablen verfügen[7]. Außerdem ist die die Fehlersuche und Fehleranalyse sehr schwer bei OpenMP wegen der mangelnde Unterstützung.

3.2 MPI

3.2.1 Definition

MPI steht für ״Message Passing Interface" und steht seit 1994 zu Verfügung. MPI ist eine Bibliothek und keine Pro grammier Sprache [2]. Diese Bibliothek besteht aus Funktionen. Die Kommunikation in einem parallelen System wird durch diese Funktionen spezifiziert. Die Grundlage dieser Funktionen basieren auf das Message-Passing-Modells. Somit ist MPI eine spezifische Umsetzung des Message- Passing-Modells.

3.2.2 Message-Passing-Modell

Message Passing wird der Nachrichtenaustausch zwischen den verschiedenen Prozessoren über ein Netzwerk genannt [4]. Die Prozessoren haben keinen ge­meinsamen Speicher sondern jeder hat seinen eigenen. Also kann kein Prozessor auf die Daten eines anderen Prozessoren zurückgreifen. In der folgenden Gra­fik wird ein einfaches Beispiel von Message Passing abgebildet.In dieser Grafik sendet der Prozessor Po eine Nachricht an den Prozessor P! über das Netzwerk [2]. Wendet man dieses Konzept von Message Passing auf einer Grösseren Ebe­ne an, erhält man das Message-Passing-Modell. Das heißt mit einem Netzwerk und einer festen Anzahl an Prozessoren und Prozessen [4]. Und wie oben schon erwähnt hat jeder der Prozessoren seinen lokalen Speicher und die Prozessoren kommunizieren über das Netzwerk miteinander.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5: Message-Passing-Modell

[2]

3.2.3 Vorteile und Nachteile von MPI

MPI kann auf Systemen mit gemeinsamen Speicher angewendet werden und auch auf Systemen mit Verteilten Speicher.Ausserdem ist MPI auf eine sehr ho­he Anzahl an Prozessoren skalierbar[13]. Ein weiterer Vorteil ist das MPI mit OpenMP kombinierbar ist. MPI besitzt denoch ein paar Nachteile.Das Netzwerk ermöglicht den Austausch zwischen den Prozessoren. Somit kann der Nachrich­tenaustausch zwischen den Prozzesoren dich das netzwerk beschränkt sein. Was zur einer Beschränkung der Leistung des Parallelisierungmodells führen kann. Dazu is es noch wichtig zu erwähnen dass die Fehlersuche und Fehleranalyse eine sehr schwiriege Aufgabe ist. [4].

3.3 GPGPU

3.3.1 Grundlagen

Die Verwendung von Grafikprozessoren (GPU) für nicht-grafische Berechnungen wird GPGPU (General Purpose Computation on Graphics Processing Units) ge­nannt [8]. Der GPU wurde für die Visualisierung entwickelt. Er besitzt sehr viele Kerne. Diese Kerne verfügen um wenig Rechenleistung weil die Visualisierung viele Berechnungen benötigt die aber nicht anspruchsvoll sind. Die Videospielin­dustrie hat sehr viel dazu beigetragen dass die Leistung der GPUs in den letzten Jahren sehr gestiegen ist. Dennoch ist die Idee das Potential zu nutzen viel später erstanden. Die folgende Grafik erklärt warum die Interrese um Gpus zu benut­zen ständig wächst:

Der GPU benötigt wenig Speicherzugriff und Steuerlogik[8]. Die führt dazu das Platz für weitere Kerne auf der Chipkarte zu Verfügung steht. Deswegen auch die hohe Anzahl an Kernen im Gegensatz zum CPU. Die Kernen des GPUs werden in Gruppen eingeteilt. Jeder dieser Gruppen verfügt über ein eigenen Steuerungs­und Cachebaustein. Der Grund für dieses Vorgehen ist dass die Berechnung von Bildpunkten unabhängig voneinander ausführbar sind. Der CPU hingegen be­sitzt einen großen Steuerungs- und Cachebaustein. Es wäre nicht Vorteilhaft die letzteren durch Kerne zu ersetzen weil der CPU sehr komplexe und viel Spei­cherzugriff erfordernde Aufgaben ausführen muss. Ein Kernel ist ein Programm das für die Ausführung auf ein GPU bestimmt ist.Es wird zuerst die Schnittstel­le initialisiert, welche die Kommunikation des CPUs und des Hauptspeicher mit dem GPU erstellt. Anschließlich werden von den Hauptspeicher an den Speicher vom GPU gesendet. Daraufhin führt der GPU den Kernel aus. Die erhaltene Er­gebnisse werden an den Hauptspeicher über der GPU Speicher transferiert.

[...]