Effiziente SPH-basierte Flüssigkeitssimulation mit Visualisierung auf einem GPU-Cluster

Titelangaben

Werner, Tim:
Effiziente SPH-basierte Flüssigkeitssimulation mit Visualisierung auf einem GPU-Cluster.
Bayreuth , 2015 . - 168 S. - (Bayreuth Reports on Parallel and Distributed Systems ; 7 )
(Masterarbeit, 2015, Universität Bayreuth, Fakultät für Mathematik, Physik und Informatik)

Volltext

	Format: PDF Name: master_thesis_werner_2015.pdf Version: Veröffentlichte Version Verfügbar mit der Lizenz Deutsches Urheberrechtsgesetz. Das Dokument darf zum eigenen Gebrauch kostenfrei genutzt werden. Darüber hinaus bedürfen die Vervielfältigung, Bearbeitung, Verbreitung und jede Art der Verwertung der schriftlichen Zustimmung des jeweiligen Rechteinhabers.
	Download (27MB)

Abstract

Dreidimensionale Flüssigkeitssimulationen sind in vielen Bereichen der Forschung und Entwicklung unverzichtbar. Eine sehr beliebte Methode für die dreidimensionale Flüssigkeitssimulation ist die sogenannte Smoothed-Particle-Hydrodynamics-Methode, welche kurz auch als SPH-Methode bezeichnet wird. Solche SPH-basierte Flüssigkeitssimulationen sind sehr rechenaufwändig. Dafür sind sie aber sehr gut parallelisierbar und besitzen einen mittelmäßigen Grad an Datenparallelität. Des Weiteren sind moderne GPUs parallele Rechner, welche die Instruktionen datenparallel per Single-Instruction-Multiple-Data (SIMD) abarbeiten. Deshalb sind sie für SPH-Simulationen gut geeignet. Auch sind die Speicherzugriffe einer SPH-Simulation extrem lokal. Deshalb eignen SPH-Simulationen sich auch sehr gut für einen GPU-Cluster. Es ist das Ziel der Masterarbeit eine SPH-Simulation auf einen GPU-Cluster zu implementieren, optimieren und untersuchen. Die Optimierungen und Untersuchungen sollen dabei im Hinblick auf die auf die Skalierbarkeit und die bestmögliche Ausnutzung der GPUs stattfinden. Des Weiteren ist für die Auswertung einer SPH-Simulation oft eine Visualisierung von Vorteil. Eine solche Visualisierung ist jedoch sehr rechenaufwändig. Deswegen beschäftigt sich die Arbeit zusätzlich damit, wie sie eine Visualisierung der SPH-Simulation in einem GPU-Cluster implementieren kann. Hierfür erklärt die Arbeit zunächst OpenGL- und CUDA-Grundlagen. Dafür wird als erstes der Hardware-Aufbau einer GPU erklärt. Auch wird die Ausführung von Programmen auf der GPU, den sogenannten Kernels, erläutert. Hierfür werden insbesondere die SIMT- beziehungsweise SIMD-Eigenschaften der GPU und die damit verbundene Warp-Ausführungseffizienz hervorgehoben. Ebenso wird erläutert, wie die GPU Latenzen überbrückt. Auch stellt die Arbeit die stark mit der Latenzüberbrückung verbundene Occupancy vor. Zudem wird auf die einzelnen Speicherbereiche einer GPU in CUDA eingegangen. Zusätzlich wird kurz die Programmierung von CUDA mit CUDA-C gezeigt. Schließlich demonstriert die Arbeit die grundlegende OpenGL-Funktionalität an einer einfachen OpenGL-Pipeline. Als Nächstes werden die physikalischen Grundlagen einer SPH-Simulation diskutiert. So diskretisiert ein SPH-Verfahren die Flüssigkeit zunächst durch einzelne Partikel. Dabei übernehmen die einzelnen Partikel die Strömungsgrößen der Flüssigkeit, die Dichte, und die Geschwindigkeit, an ihrer Position. Die Partikel dienen zudem als Stützstellen zur kurzreichweitigen Interpolation der Vektorfelder, Skalarfelder und Gradientenfelder von denjenigen Differentialgleichungen, welche die Flüssigkeit beschreiben. Für die Beschreibung der Flüssigkeit werden in dieser Arbeit die Kontinuitätsgleichung der Dichte und die Impulsgleichung verwendet. Durch die Interpolation wird die Ortsdiskretisierung ausgeführt, womit die SPH-Simulation die zeitlichen Änderungen der Strömungsgrößen der Partikel bestimmt. Da die Interpolation kurzreichweitig ist, handelt es sich bei ihr algorithmisch gesehen um ein Fixed-Radius-Near-Neighbors-Problem. Bei einem solchen Problem geht es immer darum, für jedes Partikel alle benachbarten Partikel innerhalb einer Cutoff-Distance zu finden. Anhand der gefundenen Nachbarn werden dann problemspezifische Berechnungen durchgeführt. Dabei ist zu beachten, dass die Lösung der Fixed-Radius-Near-Neighbors-Probleme bei einer SPH-Simulation immer einen Großteil der Rechenzeit ausmachen. Anschließend kann die Zeitdiskretisierung beziehungsweise Zeitintegration der zeitlichen Änderungen erfolgen, wofür die Arbeit das Prädiktor-Korrektor-Verfahren zweiter Ordnung verwendet. Mit Hilfe dieser Zeitintegration werden die Partikel dann bewegt. Danach beschreibt die Arbeit, wie die physikalischen Grundlagen zunächst in eine SPH-Simulation für eine einzige GPU umgesetzt werden. Für die Lösung der Fixed-Radius-Near-Neighbors-Probleme der SPH-Simulation wird eine Space-Partitioning-Datenstruktur benötigt. Die Arbeit verwendet eine spezielle Gitterdatenstruktur, in welche die Partikel einsortiert werden. Für die Konstruktion des Gitters wird ein atomarer Counting-Sort-Ansatz verwendet. Für die Berechnungen selbst verwendet die Arbeit den Linked-Cell-Ansatz. Bei ihm wird über die Partikel parallelisiert. Für jedes Partikel werden die benachbarten Gitterzellen nach Nachbarpartikeln innerhalb der Cutoff-Distance durchsucht, um mit ihnen die SPH-Interpolation ausführen zu können. Da die Fixed-Radius-Near-Neighbors-Berechnungen einen Großteil der Laufzeit des Programms ausmachen, wird versucht diese in Kombination mit dem verwendeten Linked-Cell-Ansatz weiter zu optimieren. Dabei wird besonderen Wert darauf gelegt, die Auswirkungen der limitierenden Latenzen zu reduzieren und die Datenparallelität zu erhöhen. Die Untersuchungen finden beispielhaft anhand von zwei Fixed-Radius-Near-Neighbors-Problemen aus der SPH-Simulation statt. Das eine Problem berechnet die zeitlichen Änderungen der SPH-Simulation, während das andere Problem die Dichten der SPH-Simulation mit einem Shepard-Filter normiert. Durch die Optimierungen lassen sich zwar die Laufzeiten beider Fixed-Radius-Near-Neighbors-Probleme deutlich reduzieren. Dennoch verursachen die Latenzen und die nur mittelmäßige Datenparallelität weiterhin große Performanceverluste. Als Nächstes wird die Simulation um eine Visualisierung erweitert. Bei der Visualisierung verwendet die Arbeit eine Ellipsoid-Splatting-Technik, um die einzelnen Partikel als Ellipsoide auf den Bildschirm zu projizieren. Für dieses Splatting muss zunächst für jedes Partikel die Anisotropie der Partikelverteilung an dessen Stelle per Fixed-Radius-Near-Neighbors-Berechnung bestimmt werden. Aus dieser Anisotropie lassen sich die Hauptachsen der Ellipsoide berechnen. Anschließend werden die Ellipsoide mit OpenGL gezeichnet, wodurch die GPU ein Tiefenbild und ein Dickebild erstellt. Nun wird das Tiefenbild per Screen-Space-Curvature-Flow geglättet, damit der Betrachter die Wölbungen der Ellipsoide im finalen Renderergebnis nicht mehr erkennen kann. Zuletzt wird das geglättete Tiefenbild und Dickebild zum finalen Renderergebnis zusammengesetzt. Dabei dient das Dickebild dafür die Durchsichtigkeit der Flüssigkeit zu bestimmen und das Tiefenbild dafür die Reflexion der Flüssigkeitsoberfläche zu bestimmen. Zu Letzt wird die Simulation mitsamt Visualisierung so erweitert, dass sie effizient auf einem GPU-Cluster ausgeführt werden kann. Anschließend wird sie in Hinblick auf die Skalierbarkeit und die Ausnutzung der GPUs untersucht. Für die Modifikationen wird das Volumen der Simulation und damit die in dem Volumen enthaltenen Partikel eindimensional in Scheiben auf die einzelnen GPUs aufgeteilt. Für sowohl die Bewegung der Partikel durch die Zeitintegration als auch für die Berechnungen der Fixed-Radius-Near-Neighbors-Probleme ist jedoch eine Kommunikation zwischen den GPUs des Clusters notwendig. Deshalb wird die Simulation so modifiziert, dass sie gleichzeitig einen Netzwerktransfer und ein Berechnen auf den GPUs erlaubt. Zusätzlich verwendet die Arbeit eine Lastbalancierung, die die Scheibendicke anhand der Kernel-Laufzeiten variiert, so dass die GPUs des Clusters gleichmäßig ausgelastet werden. Ebenso werden die Berechnungen der Visualisierung auf die Knoten des Clusters per Compositing-Technik aufgeteilt. Dafür berechnet jede GPU zunächst mit ihren eigenen Partikeln ein Tiefenbild und ein Dickebild, die dann über das Netzwerk per Min-Operation beziehungsweise per Additionsoperation zu einem einzigen Tiefenbild und Dickebild reduziert werden. Die Reduktion der Tiefenbilder und Dickebilder findet asynchron in einer Pipeline statt, damit die GPUs währenddessen weiter die SPH-Simulation berechnen können. Anschließend findet der Screen-Space-Curvature-Flow und das finale Shading auf einem separaten Knoten des Clusters statt, so dass die GPUs der anderen Knoten nicht ungleichmäßig ausgelastet werden. Die Untersuchungen zeigen, dass die Simulation sehr gut mit der Partikelzahl bei konstanter GPU-Zahl skaliert. Auch skaliert sie sehr gut mit der GPU-Zahl bei konstanter Partikelzahl. Wird die Partikelzahl der Simulation bei konstanter GPU-Zahl zu groß, so treten kleine Performanceeinbrüche wegen verringerter Cache-Trefferraten auf. Werden zu wenige Partikel bei zu vielen GPUs simuliert, so geht ebenfalls Performance verloren, da in diesem Fall die Netzwerkbandbreite limitiert. Zusätzlich wird die Laufzeit dadurch ein bisschen erhöht, dass die GPUs des Clusters trotz Lastbalancierung ein wenig auf ihre Berechnungen untereinander warten müssen. Wird die Problemgröße groß genug gewählt so lässt sich im Cluster beinahe der optimale Speedup erzielen.

Abstract in weiterer Sprache

Three dimensional liquid simulations are very important in many fields of research and design. A very popular method for a three dimensional liquid simulation is the so called smoothed particles hydrodynamics method, which is also abbreviated as the SPH method. Such a SPH based liquid simulation is very computationally expensive. But it is also very parallelizable and has a mediocre data parallelism. In addition modern GPUs are parallel computers, which process their instruction data parallel according to the single instruction multiple data model (SIMD model). That is why they are very eligible for such a SPH simulation. Furthermore a SPH simulation also performs very local memory accesses. Thus a SPH simulation is eligible for a GPU cluster, too. That is why this master thesis aims to implement a SPH based liquid simulation in a GPU cluster. Also the thesis aims to optimize and examine the simulation regarding the scalability and the utilization of the GPUs. Additionally a visualization of a liquid simulation is advantageous for the evaluation of its results. But a liquid visualization is also computationally expensive. Therefore this thesis will implement a visualization of the SPH simulation, which is performed by the GPU cluster. For this purpose the thesis first explains OpenGL and CUDA basics. First the hardware structure of a GPU will be explained. Furthermore the execution of GPU programs, so called kernels, is explained. Therefore the SIMD properties or precisely the SIMT properties of a GPU and the related warp execution efficiency are illustrated. Also this thesis explains the latency hiding behavior of the GPUs and the related concept of the occupancy. Next the different memory types of CUDA are presented. Finally the thesis demonstrates the basic OpenGL functionality based on a simple OpenGL pipeline. Subsequently the thesis explains the physical basics of a SPH based liquid simulation. The SPH method discretizes the liquid by particles. Each particle carries properties of the liquid within the volume of the particle, namely the mass, the density and the velocity. Those particles and their properties are used for the short ranged and spatial interpolation of the scalar, vector and gradient fields of the partial differential equations, which define the liquid. This thesis uses the continuity equation of the density and the momentum equation for the definition of the liquid. The interpolation performs a spatial discretization of the partial differential equations. This discretization results in the temporal changes for the variables of each particle. Since the interpolation is short ranged, it is algorithmically considered as a fixed radius near neighbors problem. Such a problem always consists of finding all neighboring particles for each particle within a given cutoff distance. The so found neighbors are used for performing problem specific computations. The solutions of the fixed radius near neighbors problems always need most of the run time of a SPH simulation. After the spatial discretization the liquid simulation performs the temporal discretization by using the temporal changes. Therefore this thesis uses a second order predictor corrector method. Thus the particles are moved. After that the thesis illustrates, how the physical basics are implemented within a SPH simulation, which is initially only computed by a single GPU. An efficient solution of a fixed radius near neighbors problem requires a spatial partitioning data structure. For that this thesis uses a special grid data structure, into which the particles are sorted. Furthermore it uses an atomic version of the counting sort algorithm for the construction of the grid. For the fixed radius near neighbors computation itself this thesis uses the linked cell approach. This approach computes each particle in parallel. For each particle the approach traverses the adjacent grid cells around the particle in order to find all neighbors within the cutoff distance. Then the found neighbor particles are used for the SPH interpolation. Since the fixed radius near neighbors computations are the most expensive part of a SPH Simulation, this thesis tries to optimize those computations in combination with the chosen linked cell approach. Therefore it tries especially to increase the quite low data parallelism and to improve the latencies, which both have a big impact on the performance. Those improvements are carried out by using two fixed radius near neighbors problems of the SPH simulation as a example. The first problem calculates the temporal changes of the particle attributes. The other problem is the so called Shepard filter, which normalizes the densities of the particles. By those optimizations the run time of both problems are greatly reduced. But still latencies and a mediocre data parallelism cost much performance. Next this thesis extends the SPH simulation by a visualization. Therefore is uses an ellipsoid splatting technique, which projects every particle as an ellipsoid onto the screen. Before the visualization can perform the splatting, it has to calculate the main axis of the ellipsoids by determining the anisotropy of the particle distribution around each particle. The anisotropy has again to be calculated by solving a fixed radius near neighbors problem. Then those ellipsoids are rendered with OpenGL in order to create a thickness image and a depth image. Since each ellipsoid causes a curvature in the depth image, which will be visible in the final image later on, the depth image has to be blurred. For blurring the thesis uses the screen space curvature flow method. Finally the thickness image and the depth image are both composed to create the final result of the visualization. Therefore the visualization uses the thickness image to determine the transparency of the liquid and the depth image to determine the reflectivity of the liquid. Finally the thesis extends the SPH simulation together with visualization, so that both of them can be performed within a GPU cluster. After that both of them are examined regarding the GPU utilization and the scalability. For the extension the volume of the simulation and thereby the particles within the volume have to be partitioned among the GPUs of the Cluster. The thesis uses a one dimensional partitioning scheme, where every GPU obtains a single slice of the volume and all particles within this volume. Furthermore a slow network communication between the different GPUs of the cluster is needed in order to move the particles and to perform the fixed radius near neighbors computations. In order to increase the GPU utilization the thesis implements the communication in a way that it will be performed simultaneously with the SPH computations. Additionally the thesis implements a load balancing algorithm in order to increase the utilization of the GPUs. The load balancing algorithm changes the thickness of the slices according to the run times of the SPH kernels. The computations of the visualization are also distributed among the GPUs of the cluster by using a compositing technique. For this compositing technique each GPU renders a depth image and a thickness image using only its own particles. After that the thickness images and the depth images of all GPUs are reduced to a single thickness image and a single depth image over the network. The reduction is performed asynchronously in a pipeline, so that the GPUs do not have to wait in order to continue with the SPH calculations. Furthermore the screen space curvature flow and the final Shading are executed on a special node with a single GPU, in order that the renaming GPUs are more evenly utilized. Finally the examinations revealed, that the simulation scales very well with the amount of used GPUs and simulated particles. If the amount of particles, which are simulated by a constant amount of GPUs, becomes too big, the performance degrades a bit because of lower cache hit rates. Furthermore there is some performance loss if too few particles are simulated by too many GPUs. This is caused by a limitation of the network bandwidth. The simulation also loses some performance because the GPUs still have to wait for the computations of each other a bit in spite of the load balancing. If the problem sizes are chosen large enough the cluster almost achieves an optimal speed up.