Abschlußarbeiten

• Auswahl fertiggestellter Diplomarbeiten
• Fertiggestellte Dissertationen
• Fertiggestellte Habilitationen

Auswahl fertiggestellter Diplomarbeiten

• "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, Mar. 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, Nov. 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, Sept. 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, Sept. 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, Sept. 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, Apr. 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 umfaßt mehrere Phasen des am Lehrstuhl entwickelten HDC-Compilers.
• "Elimination von Funktionen höherer Ordnung in Haskell-Programmen" (Christian Schaller, Sept. 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, Aug. 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, Jan. 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, Nov. 1997)
  Beschreibt die Generierung von SPMD-Code für Rechner mit verteiltem Speicher.
• "Partitionierung von parallelen Schleifenprogrammen" (Martina Wieninger, Sept. 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, Dez. 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, Sept. 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 muß.
• "Automatic Code Generation in the Polytope Model" (Sabine Wetzel, Nov. 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.

Fertiggestellte Dissertationen

• "Code Optimization in the Polyhedron Model - Improving the Efficiency of Parallel Loop Nests" (Peter Faber, Oktober 2007)
  Bringt die Elimination gemeinsamer Ausdrücke zur automatischen Schleifenparallelisierung mit dem Polyedermodell. Ausdrücke mit gemeinsamem Wert werden identifiziert. Eine Berechnung dieses Wertes wird in Raum und Zeit platziert, und weitere Zugriffe auf diesen Wert werden per Referenz installiert.
• "PolyAPM: Comparative Parallel Programming with Parallel Abstract Machines" (Nils Ellmenreich, August 2004)
  Parallele abstrakte Maschinen dienen als Interpreter für die Knoten in einem Verfeinerungsbaum, dessen Wurzel eine Problemspezifikation ist und dessen Blätter effiziente Zielprogramme sind. Als Entscheidungshilfe für die Wahl einer Verfeinerung dient ein Kostenmodell, mit dem der Interpreter einer Verfeinerung grob die Kosten der Zielprogramme vorhersagen kann, zu denen die Verfeinerung führen kann.
• "The Skeleton-Based Parallelization of Divide-and-Conquer Recursions" (Christoph Herrmann, Juni 2000)
  Es wird die effiziente Parallelisierung von Divide-and-Conquer durch Verwendung von Skeletten in der funktionalen Sprache HDC gezeigt.
• "Object-Oriented Specification of Distributed Systems" (Ulrike Lechner, Juni 1997)
  Zeigt neue Konzepte zur objektorientierten Spezifikation, zur Modellierung, Strukturierung und Wiederverwendung, zur Verifikation und Verfeinerung.
• "The Mechanical Parallelization of Loop Nests Containing WHILE Loops" (Martin Griebl, Okt. 1996)
  Zeigt, wie das für die Parallelisierung von verschachtelten FOR-Schleifen ideal geeignete Polytopmodell so erweitert werden kann, daß auch WHILE-Schleifen behandelt werden können; insbesondere werden die für die Code-Erzeugung entstehenden Probleme aufgezeigt und gelöst.

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 Prgoramms 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.