Abgeschlossene Arbeiten

  • Identifying potential instances of patterns in code

    Masterarbeit

    Betreuer/in: Jan-Patrick Lehr, M.Sc.

  • Traceability and Reproducibility of Benchmark Results

    Bachelorarbeit

    Betreuer/innen: Jan-Patrick Lehr, M.Sc., Alexander Hück, M.Sc.

  • Implementation of an Instrumentation Automation Framework

    Masterarbeit

    Betreuer/in: Jan-Patrick Lehr, M.Sc.

  • Hybride Parallelisierung und Performanceoptimierung graphenbasierter, mechanischer Simulationen von Super-Kohlenstoff-Nanoröhrchen

    Bachelorarbeit

    Motivation:

    Superkohlenstoff-Nanoröhrchen (eng. Super Carbon Nanotubes, kurz SCNTs) entstehen durch Komposition von Kohlenstoff-Nanoröhrchen mittels Y-Verbindungen zu Strukturen höherer Ordnung und stellen somit sehr strukturierte Formen dar.

    Die Modellierung SCNTs mittels gerichteter Graphen ermöglicht die Identifikation und Ausnutzung von Symmetrie und Hierarchie während der Berechnung. Des Weiteren erlaubt ein Matrix-freier Lösungsvorgang, kombiniert mit dem Zwischenspeichern von Zwischenwerten, das effiziente und vollständige Ausnutzen des vorhandenen Arbeitsspeichers. Die Symmetrien und Selbstähnlichkeiten innerhalb der Röhrchen legen außerdem eine strukturbasierte Zerlegung der SCNTs nahe. Die Simulation der resultierenden unabhängigen Teile kann auf verschiedenen Rechenknoten durchgeführt werden. Durch angepasste Reihenfolge der Berechnungen ist auch eine Überlappung von Kommunikation und Berechnungen denkbar, um den Overhead der Parallelisierung zu reduzieren.

    Beschreibung der Arbeit:

    Im Rahmen dieser Arbeit sollen die folgenden Ziele erreicht werden:

    • Bestehende Konzepte zur Zerlegung, Aufteilung und verteilten Berechnung von graphenbasierten SCNTs sollen im bestehenden Simulationscode (C++11) mittels MPI realisiert werden.

    • Die Geschwindigkeit der neu entwickelten Lösung soll mit verschiedenen Eingabedaten und variierender Anzahl von Knoten gemessen und gegebenenfalls optimiert werden.

    • Ein Umordnen der Berechnungen macht eventuell eine Anpassung der vorhandenen OpenMP Parallelisierung und des Datenpreprocessing nötig, was ebenfalls umgesetzt werden muss.

    Die Arbeit kann als Bachelor- oder Master-Thesis bearbeitet werden, wobei im Rahmen einer Masterarbeit auch die Untersuchung der Parallelisierbarkeit eines am Lehrstuhl entwickelten Formates für komprimierte Graphen untersucht werden soll.

    Empfohlene Kenntnisse:

    • Gute Kenntnisse in C++

    • Grundlagen der Parallelisierung mit MPI und OpenMP (z.B. aus der Vorlesung „Programmierung Paralleler Rechnerarchitekturen)

    • Die Bereitschaft sich in entsprechende Bereiche der benötigen Graphentheorie sowie das vorhandene Simulations-Framework einzuarbeiten

    weiter

    Betreuer/in: Dr. Michael Burger

    Ausschreibung als PDF

  • Implementing Algorithmic Differentiation Capabilities in the Universal Laminar Flame Solver

    Bachelorarbeit

    Bearbeiter/in: Sebastian Kreutzer

    Betreuer/in: Alexander Hück, M.Sc.

  • Optimierte Multiplikation von Vektoren und dünn besetzten Matrizen fester Struktur auf Multicore-CPUs und GPUs

    Bachelorarbeit

    Motivation

    Die Multiplikation dünn besetzter Matrizen mit Vektoren (Sparse-Matrix-Vector-Multiplication) muss in vielen wissenschaftlichen Simulationsanwendungen durchgeführt werden. Die Algorithmen zur Berechnung derartiger Produkte sind stets durch die Speicherbandbreite limitiert (memory-bound) und sind daher in ihrer Skalierbarkeit bei paralleler Ausführung beschränkt.

    Dementsprechend existiert eine Reihe von Datenformaten zum Abspeichern derartiger Matrizen, die sich je nach verwendeter Architektur (Multi-Core-System, Grafikkarte) unterscheiden können.

    Ebenso gibt es in der Literatur diverse Strategien zur Optimierung, sowohl für dünn besetzte Matrizen von denen bestimmte Eigenschaften bekannt sind, als auch für solche über die a priori keine Aussage möglich ist.

    Beschreibung der Arbeit

    Im Rahmen dieser Arbeit soll anhand bestehender Lösungen ein entsprechendes Datenformat, sowie ein optimierter Algorithmus für die Multiplikation von Matrizen mit einer bestimmten, für jede Problemgröße identischen Struktur und einem dichten Vektor konzipiert werden. Hierzu ist eine ausgiebige Literaturrecherche nötig, deren Ergebnisse zu dokumentieren sind. Anschließend sollen die Konzepte für Mehrkern-Prozessor-Systeme und Grafikkarten umgesetzt und ihre Leistungsfähigkeit, ihre parallele Skalierbarkeit, sowie der Speicherverbrauch mit bestehenden Lösungen verglichen werden.

    Die Arbeit kann als Bachelor- oder Master-Thesis bearbeitet werden, wobei im Rahmen einer Masterarbeit auch die Implementierung einer heterogenen Lösung vorgesehen wird, bei der sowohl CPU als auch GPU gleichzeitig am Berechnungsvorgang beteiligt sind. Auch sollen mögliche Preprocessing Schritte genauer betrachtet werden.

    Die Ergebnisse der Arbeit sollen abschließend zusammen mit dem Betreuer in einen bestehenden Forschungscode zur Simulation von Kohlenstoffnanoröhren integriert werden.

    Empfohlene Vorkenntnisse

    • Gute Programmierkenntnisse in C/C++,

    • Kenntnisse in der GPU Programmierung (OpenCL, CUDA) ,

    • Grundkenntnisse im Parallelen Rechnen (OpenMP, Beschleuniger)

    • Gute Englisch-Lesekenntnisse (zum Verständnis der Literatur)

    weiter

    Bearbeiter/in: Tristan Wirth

    Betreuer/in: Dr. Michael Burger

    Ausschreibung als PDF

  • Effiziente Datenstruktur zur Abspeicherung von Tupel- basierten Graphen

    Bachelorarbeit

    Motivation:

    Zur Konstruktion von Kohlenstoffnanoröhren wurde ein neuartiges, Graph Algebra basiertes Verfahren entwickelt. Aus diesem resultieren Graphen, deren Knoten nicht wie in traditionellen Ansätzen mittels Ganzzahlwerten oder Zeichenketten identifiziert sind, sondern mittels n-dimensionalen Tupel (xn, xn-1, …, x1, x0). Dieses System erlaubt pro Knoten eine Kodierung wichtiger Informationen wie Verlauf des Konstruktionsprozesses, Symmetrieeigenschaften und Geometrie. Somit liegt es nahe dieses Tupel-System auch als Basis des Speicherformates zu benutzen. Die während und nach der Konstruktion vorkommenden Tupel sind nicht vollständig besetzt, das heißt, es sind nicht alle denkbaren Kombinationen vorhanden.

    Beschreibung der Arbeit:

    Im Rahmen dieser Arbeit soll eine neue Speicherstruktur für Tupel-basierte Graphen konzipiert und implementiert werden. Für viele Speicherstrukturen wie Baum-basierte Ansätze oder Hash-Tabellen existieren verschiedene Varianten, die für verschiedene Datensätze unterschiedlich gut funktionieren. Vor allem perfektes Hashing stellt, in seinen verschiedenen Formen, einen viel versprechenden Ansatzpunkt dar. Allerdings wird hierzu eine schnell zu berechnende, konfliktfreie Hash-Funktion benötigt wird. Daher sollen in einem ersten Schritt bestehende Verfahren analysiert und auf ihre Tauglichkeit hin bewertet werden. Anschließend soll mit den dort gewonnenen Erkenntnissen die neue Lösung entworfen, implementiert und getestet werden.

    Die Arbeit kann als Bachelor- oder Master-Thesis bearbeitet werden, wobei im Rahmen einer Masterarbeit zusätzlich eine genaue Analyse des Verhaltens und der Leistungsfähigkeit der neuen Lösung mittels Softwaretools, sowie gegebenenfalls weiteres Tuning gefordert wird. Ebenso soll ein existierendes Verfahren zum räumlichen, perfekten Hashing implementiert und bezüglich der Geschwindigkeit mit der neu entworfenen Lösung verglichen werden.

    Empfohlene Vorkenntnisse:

    • Gute Programmierkenntnisse in C/C++,

    • Kenntnisse der Speicherarchitektur moderner Rechner

    • Grundkenntnisse im Bereich Graphentheorie

    • Gute Englisch-Lesekenntnisse (zum Verständnis der Literatur)

    weiter

    Bearbeiter/in: Giang Nam Nguyen

    Betreuer/in: Dr. Michael Burger

    Ausschreibung als PDF

  • Erweiterung des Forschungscodes mismo hinsichtlich einer neuartigen Benutzerschnittstelle zur Implementierung beliebiger numerischer Methoden im Kontext allgemeiner Diskretisierungsverfahren

    Masterarbeit

    Bearbeiter/in: Jonas Marczona B.Sc.

    Betreuer/innen: Prof. Dr. Christian Bischof, Dr. Michael Burger

  • Ableitungsberechnung auf GPUs mit Matlab

    Bachelorarbeit

    Automatisches Differenzieren[1] (AD) ist eine Methode, numerische Programme automatisiert so zu modifizieren, dass die Ableitungen der ursprünglichen Berechnungen effizient bestimmt werden können. Das Werkzeug ADiMat (Automatisches Differenzieren für Matlab) wird am Fachgebiet SC entwickelt und ermöglicht AD von Matlab-Funktionen. Es beinhaltet zwei verschiedene Implementierung des Vorwärtsmodus und eine Implementierung des Rückwärtsmodus von AD.

    Insbesondere im Vorwärtsmodus ist es oft von Interesse zahlreiche Richtungsableitungen gleichzeitig zu berechnen. Die Laufzeit des mit AD erstellten Programms steigt linear mit der Anzahl der Richtungsableitungen. Der Einsatz von Parallelverarbeitung bei der Berechnung der Richtungsableitungen liegt nahe. Da die Ableitungsberechnung sich in vielen Fällen als Folge von (Matrix-)Multiplikationen darstellt, ist auch der Einsatz von GPUs denkbar. weiter

    Bearbeiter/in: Benjamin Richter

    Betreuer/in: Alexander Hück, M.Sc.

    Ausschreibung als PDF

  • Adaptierung des Shallow Water Codes zur Simulation seichter Gewässer für den Intel Xeon Phi

    Bachelorarbeit

    In vielen Ingenieurswissenschaften nimmt die Simulation von realen Vorgängen (Verbrennungen, Strömungen von Gasen oder Flüssigkeiten, Partikelbewegungen, …) einen großen Stellenwert ein. Durch rechnergestützte Simulationen ist es zum Beispiel möglich schon während der Entwicklung die Auswirkungen bestimmter Parameterveränderungen auf das Verhalten eines neu zu konstruierenden Systems zu analysieren. Simulationen, welche große Systeme mit vielen Freiheitsgraden nachbilden, besitzen allerdings oft sehr hohe Laufzeiten für die Berechnung.

    Um diese Berechnungszeiten zu verkürzen, wird durch Anpassungen an den existierenden Simulationsprogrammen versucht, sich die Leistung zu Nutze zu machen, welche moderne parallele Hardware in verschiedener Form bietet. Zu nennen sind hier zum Beispiel Rechencluster, GPGPU-Anwendungen oder Intels Xeon Phi Coprozessor. Diese Architekturen ermöglichen es dem Entwickler die Rechenlast von Anwendungssoftware auf verschiedene Einheiten zu verteilen, um auf diese Weise kürzere Laufzeiten zu erreichen. Hierbei kommen je nach Zielarchitektur verschiedene Techniken wie OpenMP, Cilk Plus, Intel TBB, MPI oder OpenCL zum Einsatz.

    Im Rahmen dieser Arbeit soll ein bestehender Simulationscode für das Verhalten seichter Gewässer auf Intels Xeon Phi Coprozessor adaptiert werden. Hierzu ist zunächst eine Parallelisierung für SMP-Systeme (z.B. mittels OpenMP) durchzuführen, um die inhärente Parallelität der Berechnung auszunutzen. Anschließend erfolgt die Portierung auf den Xeon Phi mit einer Analyse des Verhaltens auf dem Coprozessor.

    In einem weiteren Schritt sollen verschiedene Codeoptimierungen durchgeführt und ihre Vorteile untersucht werden. Hierzu zählen vor allem die Implementierung eines kürzlich beschriebenen, optimierten Verfahrens zur Berechnung dünnbesetzter Matrizen[1] und die Restrukturierung des Codes, um die 512bit breiten SIMD-Einheiten durch Vektorisierung zu nutzen. Ein weiterer Punkt ist die Untersuchung des Einflusses verschiedener Parameter auf die Laufzeit der Software. Hierbei sind vor allem das die Anzahl der parallel zu berechnenden Threads und deren Scheduling zu nennen.

    Als weitere Arbeitsschritte sind der Performancevergleich mit den vorhandenen Cluster Knoten oder eine MPI Parallelisierung denkbar.

    Voraussetzungen für die Bearbeitung der Thesis sind:

    • Gute C/C++ Kenntnisse

    • Grundkenntnisse der parallelen Programmierung (OpenMP, Cilk Plus oder Intel TBB)

    Im Rahmen dieser Arbeit werden sie sich Wissen über:

    • Wissenschaftliches Arbeiten

    • Praktische Anwendung von Parallelisierungstechniken

    • Vektorisierung von Berechnungen

    • Arbeiten mit Acceleratoren

    aneignen und

    • Eine schriftliche Ausarbeitungen von ca. 40 Seiten verfassen.

    weiter

    Betreuer/innen: Dr. Michael Burger, Dr. Christian Iwainsky