Sprachen

Beyond Graphics - Strömungssimulation in der GPU - SS 2005, WS 2005/06

Thema: 
Entwurf und Entwicklung einer Softwareumgebung zur numerischen Strömungssimulation unter Ausnutzung der Leistungsföhigkeit moderner Grafikkarten und entsprechender 3D-Gittermanipulationstechniken.
Zeitraum: 
SS 2005, WS 2005/06
Umfang: 
8 SWS pro Semester
Veranstalter: 

Dipl.-Inform. Claus-Peter Alberts, Informatik VII (Graphische Systeme),
OH16, R.101, Tel.:6134, E-Mail: Claus-Peter.Alberts@cs.uni-dortmund.de
Dipl.-Inform. Christian Becker, Mathematik III,
Vogelpothsweg 87, R.1051, Tel.: 5934, E-Mail: Christian.Becker@mathematik.uni-dortmund.de
Dipl.-Inform. Dominik Gäddeke, Mathematik III,
Vogelpothsweg 87, R.1014, Tel.: 7218, E-Mail: Dominik.Goeddeke@mathematik.uni-dortmund.de

Einzelpräsentation: 

Donnerstag, 27.01.2005, 16 Uhr, Mathetower, Raum 1048

Teilnehmer: 
1. Bachmann Daniel
2. Beben Przemyslaw
3. Becker-Adam Till
4. Braun Andre
5. Ehrenberg Andreas
6. Heine Matthias
7. Groß Christian
8. Hein Michael
9. Miemczyk Matthias
10. Münster Raphael
11. Senne Mark Stefan
12. Sykorra Sacha Mirko
13. Wohlgemuth Klaus
Thematik: 

Strömungsvorgänge treten in der Natur in einer Vielzahl verschiedenster Situationen auf, man denke beispielsweise an meteorologische Vorgänge wie Wind- und Meeresströmungen, Luft- und Benzinströmungen in Automotoren, Turbinen und Triebwerken sowie Umströmungen zur Analyse des Luftbzw. Wasserwiderstandes komplexer Objekte wie Automobile oder Schiffe. Um diese Vorgänge qualitativ und quantitativ zu untersuchen, gibt es zwei grundsätzliche Vorgehensweisen: Im Experiment wird ein Modell der Wirklichkeit, häufig in verändertem Maßstab, konstruiert und an diesem dann Messungen durchgeführt. In der Automobilindustrie platziert man beispielsweise während der Designphase ein verkleinertes Modell eines Prototyps in einem Windkanal, um seinen Luftwiderstand zu messen. In der Simulation geht man im Gegensatz dazu abstrakter vor, ein Simulationszyklus besteht aus vier wesentlichen Schritten:

  • Modellbildung: Ein physikalisches Phänomen wird durch eine Reihe von mathematischen Gleichungen beschrieben. Für die Strömungssimulation sind dies die sogenannten Navier- Stokes-Gleichungen, ein System partieller Differenzialgleichungen. Eine Lösungsformel für diese Gleichungen existiert nicht, daher ist man auf numerische Verfahren angewiesen, die eine Näherungslösung iterativ berechnen.
  • Diskretisierung: Das Modell wird diskretisiert, d.h. in eine für den Computer verarbeitbare Form gebracht. Typischerweise wird hier die Methode der Finiten Elemente (FEM, [14]) genutzt. Man erhält nach einiger mathematischer Arbeit große (lineare) Gleichungssysteme.
  • Berechnung: Die Lösung dieser Gleichungssysteme liefert große Mengen an diskreten Rohdaten.
  • Aufbereitung: Mit Hilfe geeigneter Visualisierungstechniken werden die Rohdaten in eine für den Anwender interpretierbare Form gebracht.

Die wissenschaftliche Disziplin des CFD (computational fluid dynamics) [15, 9] beschäftigt sich mit der Vorhersage von Strömungsvorgängen durch eben diese Simulationen. CFD ist ein interdisziplinäres Forschungsgebiet, es beinhaltet Aspekte aus so verschiedenen Bereichen wie den klassischen Naturwissenschaften, der angewandten Mathematik, der Informatik und den Ingenieurwissenschaften.
In der Projektgruppe sollen vor allem die Bereiche Diskretisierung und Berechnung betrachtet werden, die aus Sicht der Informatik hochinteressante Aspekte beinhalten. Als Fallbeispiel soll das Szenario des virtuellen Windkanals dienen, bei dem ein dreidimensionales, komplexes Objekt, gegeben durch eine Beschreibung seiner Oberfläche, in einem Kanal fixiert und von einer Seite des Kanals eine Strömung eingeleitet wird. Als Beschreibungsform für die Geometrie kommen prinzipiell alle aus der Computergrafik bekannten Darstellungen wie Oberflächentriangulierungen, NURBS-Patches, Unterteilungsflächen etc. in Betracht [1]. Mit der Methode der Finiten Elemente [14] wird das Differenzvolumen zwischen Objekt und Kanal (also der Bereich, in dem beim Experiment tatsächlich Strömungsvorgänge auftreten würden) in viele kleine hexaederförmige Elemente zerlegt. All diese Elemente überdecken zusammen das Simulationsgebiet, ihre Gesamtheit wird Rechengitter genannt. Dieses Rechengitter bildet zunächst eine rein geometrische Diskretisierung des Strömungsgebiets. Ein gutes Rechengitter muss optimal an die konkrete Situation angepasst sein, es müssen alle Details der Geometrie aufgelöst werden. Aus der Oberflächenbeschreibung sind hierzu Gittermanipulationstechniken [7, 13, 4] bekannt. Man kann die Seitenflächen der Hexaederzellen, die keine Nachbarn haben, als Oberflächennetz (s. Abb. 1a) auffassen.

(a) (b)

Abbildung 1: (a) Beispiel für eine einfache Kugelgeometrie. Die Seitenflächen der Hexaeder, die geometrisch die Kugelapproximation bilden, sind hervorgehoben. (b) Beispiel für ein deformiertes Gitter (oben) und das Geschwindigkeitsfeld einer darauf berechneten Strömung (unten).

Eine Aufgabe der Projektgruppe besteht nun darin, Deformationsansätze aus dem zweidimensionalen, vgl. Abb. 1b, auf den Fall eines Volumengitters zu erweitern. Dabei ist darauf zu achten, dass die Gitterelemente gewissen Qualitätskriterien genügen, beispielsweise dürfen die einzelnen Zellen sich nicht gegenseitig durchdringen.
Die Größe der im nächsten Schritt zu lösenden Gleichungssysteme in der Simulation kann in realistischen Fällen schnell mehrere Millionen an Unbekannten betragen. Die Auflösung in endlicher Zeit auf handelsüblichen PCs ist illusorisch. Der klassische Ausweg besteht in der Verwendung paralleler Algorithmen auf Super- oder Clustercomputern. Die Nutzung solcher Maschinen kann jedoch jedes Budget explodieren lassen. Eine sehr aktuelle Entwicklung bietet eine vielversprechende Lösungsmöglichkeit: Aktuelle Grafikkarten sind im Vergleich zu Clustercomputern bezahlbar. Ihre Prozessoren (GPUs) können als streaming processors aufgefasst werden. Mit der C-ähnlichen Hochsprache Cg (C for graphics, [10, 12]) oder dem Microsoft-Pendant HLSL (high level shading language, [11]) besteht die Möglichkeit, diese Prozessoren komfortabel und effizient zu programmieren. Ein aktueller Trend, der in der Projektgruppe verfolgt werden soll, besteht in der Nutzung der Rechenkraft der Grafikkarte für allgemeine Anwendungen außerhalb des Renderings (general purpose computations on the GPU, [6]). Erste Veröffentlichungen, wie [3, 8, 5], übertragen einfache numerische Lösungsverfahren in eine GPU-Implementierung und versprechen im Vergleich zu einer reinen CPUImplementierung eine Beschleunigung um einen Faktor 5 bis 15. Das Themengebiet ist sehr aktuell, allgemein gültige Zugänge existieren noch nicht. In der Projektgruppe sollen zunächst existierende Spezialfälle aus den Veröffentlichungen extrahiert und in einer Bibliothek gebündelt werden. Die Bibliothek soll Basisfunktionalitäten bieten, so dass beliebige numerische Algorithmen in die GPU portiert werden können. Für die portierten Verfahren soll ein Leistungsvergleich im Bezug auf Geschwindigkeit und Speichertransfer zwischen GPU und CPU durchgeführt werden.
Alle hier aufgeführten Teilgebiete sollen abschließend in einer Simulationsumgebung mit einer gra- fischen Benutzerschnittstelle zusammengefasst werden.
Das System soll mit objektorientierten Software-Entwurfsmethoden entwickelt werden [2]. Dabei sollen entsprechende Software-Entwurfswerkzeuge eingesetzt werden, beispielsweise TOGETHER. Beim Entwurf ist ferner auf die Erweiterbarkeit mit weiteren Deformationsansätzen bzw. weiteren numerischen Verfahren zu achten. Die Erstellung des GPU-basierten Moduls soll durch strukturierte Analyse/Entwurf, Harel-Automaten und Petri-Netze [2] unterstützt werden. Die Implementierung soll in der Programmiersprache C++ unter Nutzung von QT, OpenGL und Cg erfolgen.

PG Homepage: 
Hier wird alles besprochen
Minimalziele: 
  • Dokumentierter Systementwurf.
  • Dokumentierte Implementierung einer GPU-Bibliothek.
  • Dokumentierte Implementierung der Simulationsumgebung.
  • Demonstration der Funktionalität anhand einer vollständig durchgeführten Simulation.
Teilnahmevorraussetzungen: 
  • Stammvorlesung Graphische Systeme (bzw. Mensch-Maschine-Interaktion). [V]
  • Spezialvorlesungen Rendering oder Geometrisches Modellieren. [W]
  • Kenntnisse in objektorientierter Programmierung in C++ oder Java. [W]

Legende: [V] vorausgesetzt, [W] wünschenswert, Mathematikkenntnisse, die über das Vordiplom hinausgehen, sind trotz des mathematischen Anwendungsgebiets nicht notwendig.

Literatur: 

[1] S. Abramowski und H. Müller: Geometrisches Modellieren, BI-Wissenschaftsverlag, 1992
[2] H. Balzert, Lehrbuch der Software-Technik, Spektrum akad. Verlag, 2000
[3] J. Bolz, I. Farmer, E. Grinspun und P. Schröder: Sparse Matrix Solvers on the GPU: Conjugate Gradients and Multigrid, ACM Siggraph 2003, http://multires.caltech.edu/pubs/
[4] M. Botsch und L. Kobbelt: Multiresolution Surface Representation Based On Displacement Volumes, Eurographics 2003
[5] Z. Fan, F. Qiu, A. Kaufman und S. Yoakum-Stover: GPU Cluster for High Performance Computing, Proceedings of the ACM/IEEE Supercomputing Conference 2004, to appear
[6] General Purpose Computations on the GPU, http://gpgpu.org
[7] L. Kobbelt et.al: Geometric Modelling Based on Polygonal Meshes, MPI Informatik, MPI-I-2000-4-002
[8] J. Krüger und R. Westermann: Linear Algebra Operators for GPU Implementation of Numerical Algorithms, ACM Siggraph 2003, http://wwwcg.in.tum.de/Research/GPU
[9] D. Kuzmin: Skript zur Vorlesung CFD, Universität Dortmund, SS2003, http://www.mathematik.uni-dortmund.de/lsiii/download
[10] R. Mark, R. Glanville, K. Akeley und M. Kilgard: Cg, A system for programming graphics hardware in a C-like language, ACM 2003
[11] Microsoft MSDN, http://msdn.microsoft.com/library/default.asp?url=/library/en-us/directx9_c/directx/graphics/programmingguide/programmablepipeline/hlsl/programmablehlslshaders.asp
[12] NVIDIA Corp., Cg Toolkit, http://developer.nvidia.com/object/cg_toolkit.html
[13] P. Schröder: Subdivision,Multiresolution and the Construction of Scalable Algorithms in Computer Graphics, Multivariate Approximation and Applications, Cambridge University Press 2001, http://multires.caltech.edu/pubs/
[14] H.R. Schwarz: Methode der finiten Elemente, B.G. Teubner Verlag, 3.Auflage, 1991
[15] P. Wesseling: Principles of computational fluid dynamics, Springer 2001

Rechtliche Hinweise: 
Die Ergebnisse der Projektarbeit inklusive der dabei erstellten Software sollen der Fakultät für Informatik uneingeschränkt zur freien Forschung zur Verfügung stehen. Darüber hinaus sind keine Einschränkungen der Verwertungsrechte an den Ergebnissen der Projektgruppe und keine Vertraulichkeitsvereinbarungen vorgesehen.