Lehrstuhl für Informatik mit Schwerpunkt Programmierung
Abschlussarbeiten

Abschlussarbeiten

Fertiggestellte Habilitationsschriften

  • "Automatic Parallelization of Loop Programs for Distributed Memory Architectures" (Martin Griebl, Dezember 2004) 
    Präsentiert alle nötigen Übersetzungsphasen in der automatischen, modellbasierten Parallelisierung. Die Schwerpunkte liegen einerseits auf der Verfeinerung des Modells duch geeignetes Partitionieren der Indexräume und andererseits auf der Kachelung des parallelen Programms zur Anpassung des Kommunikationsaufwands an die Parameter der Zielarchitektur (Prozessorenzahl, Verhältnis von Kommunikations- zu Berechnungszeit).
  • "Abstraction and Performance in the Design of Parallel Programs" (Sergei Gorlatch, Juli 1997) 
    Präsentiert einen formalen, methodischen Ansatz, der von vielen komplexen architekturabhängigen Details der Parallelprogrammierung abstrahiert, um somit dem Anwender einen großen Teil der Entwicklungsarbeit zu ersparen. Beschreibt Methoden der Umwandlung abstrakter Spezifikationen in effiziente Algorithmen durch korrektheitserhaltende Transformationen in einem funktionalen Kalkül und Experimente mit Zielprogrammen auf einem Parallelrechner. 

Fertiggestellte Dissertationen

Auswahl fertiggestellter Diplom- und Masterarbeiten

  • "A Performance Prediction Function based on the Exploration of a Schedule Search Space in the Polyhedron Model" (Dominik Danner, Februar 2017)
    Die Arbeit beschreibt eine Erweiterung des Tools Polyite zur iterativen Schedule-Optimierung im Polyedermodell um eine Performance-Vorhersage-Funktion für Schedules. Die Vorhersagefunktion setzt sich aus einer Reihe von Features zusammen, welche unterschiedliche Aspekte von Schedules ausdrücken. Die Güte der Vorhersagen wird evaluiert.
  • "Polyhedral Optimization for GPU Offloading in the ExaStencils Code Generator" (Christoph Woller, Oktober 2016)
    Der Codegenerator für Grafikprozessoren des Projekts "ExaStencils" wird um eine polyedrische Codegenerierung erweitert, die den gemeinsamen Speicher (shared memory) und den nur-lese Cache der GPU sowie räumliche Blockung als Optimierungstechniken unterstützen. Mittels Exploration wird nach den besten Schedules in ausgewählten Beispielen gesucht und die Praxistauglichkeit der Codegenerierung anhand eines Stencil-Problems aus der Anwendung untersucht.
  • "Combining the DKU Pattern with Polyhedral Optimization and Tiling" (Stefan Kronawitter, April 2013)
    Für das Divider-Kernel-Undivider Programmiermuster zur datenparallelen Ausführung von Programmen werden die benötigten Programmteile Divider, Kernel und Undivider automatisch mittels Methoden der polyedrischen Parallelisierung aus einer gegebenen Spezifikation oder sequenziellen Implementierung erzeugt.
  • "Performance Exploration of Selected Manually and Automatically Parallelized Codes on GPUs" (Franz Xaver Bayerl, März 2012)
    Diese Arbeit studiert die Performanz verschiedener Parallelisierungen der Matrixmultiplikation auf Grafikprozessoren.
  • "Enabling Polyhedral Optimizations in LLVM" (Tobias Grosser, April 2011)
    Diese Arbeit beschreibt Polly, eine Infrastruktur um Optimierungen basierend auf dem Polyedermodell in LLVM verfügbar zumachen.
  • "Alternative Features in Colored Featherweight Java" (Malte Rosenthal, Juli 2009)
    Diese Arbeit beschäftigt sich mit der Erweiterung eines Typsystems für Produktlinien um die Unterstützung von alternativen Features.
  • "Feature-Oriented Composition of XML Artifacts" (Jens Dörre, März 2009)
    Untersucht die Anwendbarkeit des Feature-Kompositionsansatzes für
    XML-Sprachen. Darin wird das prinzipiell sprachunabhängige, Grammatik-basierte Werkzeug FeatureHouse prototypisch für XML-Schema-basierte Sprachen erweitert. Solche semi-strukturierten Sprachen bilden allerdings eine umfassendere Sprachklasse als moderne Programmiersprachen, so dass sich zusätzliche Herausforderungen bei der Komposition ergeben.
  • "Extending a Task Farming Framework with Dependences to P2P Communications" (Philipp Claßen, Februar 2009)
    In dieser Arbeit wird das Master-Worker HOC ersetzt durch ein neues P2P-HOC. Dabei wird das taskfarming-Prinzip um peer-to-peer-Kommunikation erweitert, wodurch Skalierbarkeit und Effizienz des Zielprogramms verbessert werden.
  • "On Algorithmic and Heuristic Approaches to Integral Problems in the Polyhedron Model with Non-linear Parameters" (Stefan Schuster Juni, 2007)
    Diese Arbeit betrachtet Möglichkeiten, ganzzahlige Lösungen für Probleme, die im Polyedermodell mit nicht-linearen Parametern auftreten, exakt zu beschreiben. Speziell wird die Lösbarkeit linearer Diophantischer Gleichungssysteme, wie sie in Banerjee's Datenabhängigkeitsanalyse auftreten, untersucht.
  • "SPARK for Concurrent Programming" (Michael Haller, März 2006)
    SPARK ist eine Umgebung zur automatischen Verifikation von Ada-Programmen, die allerdings nur eine Teilsprache von Ada bedient. Unter anderem ist Nebenläufigkeit nicht zugelassen. Die Arbeit behandelt eine SPARK-Variante namens PassauSPARK, mit der Monitore in Prozess/Monitor-Programmen verifiziert werden können. Fallstudie ist ein prototypisches Betriebssystem für Routerknoten eines Rechnernetzes.
  • "Verteilung von allgemeinen Berechnungsinstanzen in automatisch generierten Schleifen" (Thomas Wondrak, November 2005)
    Die Parallelisierung im Polyedermodell basiert auf einer Verteilung von Berechnungsinstanzen im Raum. Es wird die Implementierung und Evaluierung einer Platzierungsmethode für Berechnungsinstanzen beschrieben, die replizierte Berechnung eines Wertes auf unterschiedlichen Prozessoren berücksichtigt und dabei auf einem flexiblen, compiler- und maschinenabhängigen Ansatz basiert.
  • "Automatic Code Generation for Distributed Memory Architectures in the Polytope Model" (Michael Claßen, September 2005)
    In dieser Arbeit wird ein Mechanismus zur automatischen Codegenerierung vorgestellt. Die entsprechende Implementierung ermöglicht es, effizienten Zielcode für Programme zu generieren, die im Rahmen des LooPo-Projektes parallelisiert worden sind. Besonderen Wert wird dabei auf den erzeugten Kommunikationscode für Systeme mit verteiltem Speicher gelegt. Dabei wird die Tiling-Technik verwendet, um die Granularität der Parallelität zu adjustieren. Als Zielsprache dient C++ in Verbindung mit der Kommunikationbibliothek MPI.
  • "Tuning MetaOCaml Programs for High Performance" (Tobias Langhammer, September 2005)
    Die Arbeit stellt eine umfangreiche quantitative Untersuchung dar, wie sich trotz Abstraktion in der Programmierung mit MetaOCaml Effizienzergebnisse erreichen lassen, die üblicherweise Hardware-nahen Sprachen wie C oder Fortran vorbehalten sind. Informationen zum Hintergrund mit weiteren Arbeiten von Herrn Langhammer sind auf der Metaprogrammierungs-Projektseite verfügbar.
  • "Extending the Polyhedron Model to Inequality Systems with Non-linear Parameters using Quantifier Elimination" (Armin Größlinger, September 2003)
    Das Polyedermodell erlaubt üblicherweise nur das lineare Auftreten von Parametern in Ungleichungen, d. h. Produkte von Parametern oder von Parametern und Variablen sind nicht erlaubt. Diese Arbeit untersucht Möglichkeiten, auch nicht-lineare Parameter im Polyedermodell zuzulassen, die beispielsweise für Tiling mit parametrischer Tile-Größe erforderlich sind. Das wesentliche mathematische Hilfsmittel um diese Verallgemeinerung zu erreichen, ist Quantorenelimination in den reellen Zahlen.
  • "Parallele Schleifenprogramme in Java" (Andreas Wolf, April 2000)
    Diese Arbeit beschreibt vier Java-Dialekte, die auf Parallelität hin ausgerichtet sind, und untersucht deren Anwendbarkeit als Zielsprache für parallelisierende Compiler im Bereich Hochleistungsrechnen.
  • "Codeoptimierung für strikte funktionale Programme" (Jan Laitenberger, Juni 1999)
    Diese Arbeit enthält eine Sammlung von Optimierungstechniken, die benötigt werden, wenn ein funktionales Programm nicht durch ein spezialisiertes Ausführungsprinzip, wie etwa die Graphreduktion, sondern im Kontext imperativer Skelette ausgeführt werden soll. Die im Rahmen der Arbeit entstandene Implementierung dieser Techniken umfasst mehrere Phasen des am Lehrstuhl entwickelten HDC-Compilers.
  • "Elimination von Funktionen höherer Ordnung in Hask­ell-Programmen" (Christian Schaller, September 1998)
    Mit Funktionen höherer Ordnung kann man verschachtelte Skelette auf eine saubere Art und Weise bescheiben. Allerdings ist die Analyse und Codegenerierung von funktionalen Programmen mit Funktionen höherer Ordnung problematisch. Diese Arbeit beschreibt ein Eliminationsverfahren für diese Funktionen in HDC-Programmen unter Verwendung von Monomorphisierung und Spezialisierung.
  • "Automatische Verifikation von Gleichheitsbeweisen in Haskell" (Robert Günz, August 1998)
    Die Arbeit besteht aus der Konstruktion eines automatischen Systems zur Prüfung von Gleichungsbeweisen in Haskell. Die in einer Beweisdatei enthaltenen Schritte werden anhand von Regeln verifiziert, die der Benutzer in einer Datenbasis spezifiziert. Um unter allen möglichen Kombinationen von Regelauswahl, Anwendungsstelle und Instanzierung eine zulässige Lösung zu finden, wird Backtracking verwendet. Ausdrücke werden teilweise ausgewertet, um durch syntaktischen Zucker bedingte Unterschiede auszugleichen.
  • "Formale Ableitung und Implementierung paralleler MPI-Programme aus Homomorphismen" (Holger Bischof, Januar 1998)
    Beschreibt die Entwicklung paralleler Programme mit Hilfe des Bird-Meertens Formalismus. Es wird eine Unterklasse der Divide-and-Conquer Algorithmen betrachtet, die verteilten Homomorphismen (DH), und eine parametrisierte Familie paralleler Implementierungen dafür hergeleitet. Weiterhin wird anhand der Fast Fourier Transformation die Anpassung an das DH-Format beschrieben, wobei hierfür noch spezielle Optimierungen vorgestellt werden.
  • "Transformation von Shared-Memory-Programmen zu Distributed-Memory-Programmen" (Peter Faber, November 1997)
    Beschreibt die Generierung von SPMD-Code für Rechner mit verteiltem Speicher.
  • "Partitionierung von parallelen Schleifenprogrammen" (Martina Wieninger, September 1997)
    Beschreibt eine LSGP Tiling Methode und ihre Adaption für parallel Schleifensätze, und eine LPGS Tiling Methode für parallele Schleifensätze.
  • "Parallelization of Loop Nests with General Bounds in the Polyhedron Model" (Max Geigl, März 1997)
    Der erste Teil beschreibt die Auswirkungen verschiedener Schleifenarten für die Zielcodegenerierung und integriert die Resultate in eine Klassenhierarchie. Der zweite Teil erweitert das Polyedermodell zu unvollständigen Schleifenverschachtelungen mit allgemeinen for-Schleifen, while-Schleifen und (einfachen) if-Statements.
  • "Schleifenparallelisierung in Haskell" (Nils Ellmenreich, Dezember 1996)
    Wendet die im Projekt LooPo implementierte Polytopenmethode der Schleifenparallelisierung auf Programme in der funktionalen Programmiersprache Haskell an. Bestimmte Haskell-Ausdrücke, nämlich Array-Comprehensions, können in der Kompilierphase automatisch ausgelagert und an LooPo zur Parallelisierung übergeben werden. Die Methode ist implementiert.
  • "Practical Methods for Scheduling and Allocation in the Polytope Model" (Wolfgang Meisl, September 1996)
    Beschreibt die Zeitabbildungsmethode von Darte/Vivien und die Raumabbildungsmethode von Darte/Dion/Robert, sowie einige Erweiterungen, und enthält Kommentare über die Implementierung in LooPo.
  • "Implementierung von parallelem Divide-and-Conquer auf Gittertopologien" (Marian Musiol, Mai 1996)
    Basierend auf den Arbeiten von Mou und Herrmann/Lengauer wurde ein geeignetes Kommunikationsschema für message-passing Parallelrechner entwickelt und auf einem Transputernetz implementiert. Der komplexitätsmäßig gute Algorithmus für die Multiplikation dichter Polynome von Karatsuba (1962) O(n^1.58..) dient als anspruchsvolle Fallstudie bei verteilten Ein-/Ausgabedaten, da jede Probleminstanz in drei Teilprobleme aufgespalten werden muss.
  • "Automatic Code Generation in the Polytope Model" (Sabine Wetzel, November 1995)
    Beschreibt Codegerierungsalgorithmen für nach der Methode von Lamport oder Feautrier generierte Raumzeitabbildungen. In LooPo implementiert.
  • "Automatische Methoden zur Parallelisierung im Polyedermodell" (Christian Wieninger, Mai 1995)
    Beschreibt und vergleicht zwei automatische Methoden zur Generierung von Raumzeitabbildungen: Lamports Hyperebenenmethode and Feautriers Arbeit über ein- und mehrdimensionale Raum- und Zeitverteilungen. Beide sind im Schleifenparallelisierer LooPo implementiert.

Auswahl fertiggestellter Bachelorarbeiten