Paralleles Rechnen ist die Zusammensetzung der Ergebnisse mehrerer Teilberechnungen zu einem Gesamtergebnis. Es existieren mehrere Gründe wie z.B. die Ausführungsdauer. Durch das Parallele Rechnen ist es bei Simulationen möglich viel Zeit zu sparen und die Ergebnisse schneller zu erhalten. Ein anderer Grund ist die Ressourcenbeschränktheit. 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 miteinander verbinden. Der letzte Grund den wir erwähnen ist die Komplexe Problemdarstellung. Es gibt Simulationen die so komplex sind, dass um ein Ergebnis zu erhalten, eine Parallele Bearbeitung die einzige Möglichkeit ist. Paralleles Rechnen wird in vielen verschiedenen Bereichen wie z.B. in der Wirtschaft (Big Data, Data Mining...) und in der Forschung (Physik, Mathematik...) verwendet.
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 Teilberechnungen zu einem Gesamtergebnis [14]. Es existieren mehrere Gründe wie Z.B. die Ausführungsdauer [10]. Durch das Parallele Rechnen ist es bei Simulationen 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 miteinander verbinden. Den letzten Grund den wir erwähnen ist die Komplexe Problemdarstellung [14]. Es gibt Simulationen die so komplex sind, dass um ein Ergebnis zu erhalten, eine Parallele Bearbeitung die einzige Möglichkeit ist. Paralleles Rechnen wird in vielen verschiedenen Bereichen wie Z.B. in der Wirtschaft (Big Data, Data Mining...) und in der Forschung (Physik, Mathematik...) verwendet [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 GegenSatz 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 stetigen 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 Gitterpunkte. 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 dazugehö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 Bewegungsrichtung, Cïj(x,t) ist der Kollisionsoperator, fi(x,t) ist die diskrete Verteilungsfunktion.
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 gemeinschaftlich 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 bezeichnet. 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 Bereichs wir der Mastethread weiter ausgeführt. Es ist zu bemerken dass innerhalb eines parallelen Abschnittes ein anderer entstehen kann.Der Thread der zu diesen 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 Auslastung de CPUs ermöglicht [7].Ausserdem ist sie nur eine Spracherweiterung von c, C++ und Fortan. Ein weiterer Vorteil ist, dass der Quellcode des Programms 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 eine ü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 gemeinsamen Speicher sondern jeder hat seinen eigenen. Also kann kein Prozessor auf die Daten eines anderen Prozessoren zurückgreifen. In der folgenden Grafik 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 Ebene 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 hohe 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 Nachrichtenaustausch 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) genannt [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 Videospielindustrie 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 benutzen 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 Steuerungsund Cachebaustein. Der Grund für dieses Vorgehen ist dass die Berechnung von Bildpunkten unabhängig voneinander ausführbar sind. Der CPU hingegen besitzt einen großen Steuerungs- und Cachebaustein. Es wäre nicht Vorteilhaft die letzteren durch Kerne zu ersetzen weil der CPU sehr komplexe und viel Speicherzugriff 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 Schnittstelle 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 Ergebnisse werden an den Hauptspeicher über der GPU Speicher transferiert.
[...]