Abschlussarbeiten

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

"Iterative Schedule Optimization for Parallelization in the Polyhedron Model" (Stefan Ganser, Januar 2020)
Stellt einen Ansatz zur iterativen Schedule-Optimierung zur Parallelisierung und Kachelung im Polyedermodell vor. Anvisiert werden Schleifenprogramme, die von der Optimierung von Datenlokalität und grobkörniger Schelifenparalleisierung profitieren. Der Schedule-Suchraum kann entweder per Zufall oder mit Hilfe eines genetischen Algorithmus durchforstet werden.
"Automatic Performance Optimization of Stencil Codes" (Stefan Kronawitter, Dezember 2019)
Spezialisiert Codeoptimierung auf Knotenebene für Stencilcodes. Verwendete Techniken beinhalten eine Kombination von Raum-und Zeitkachelung, arithmeitsche Vereinfachungen und Normalisierungen, beliebige nicht-invasive affin-lineare Transformationen von Datenlayouts, Redundanzelimination übergreifend auf benachbarte Schleifenschritte und sieben Filter zur Reduzierung des immensen Suchraums legaler paralleler Ausführungen schlussendlich auf eine Handvoll.
"The Challenges of Non-linear Parameters and Variables in Automatic Loop Parallelisation" (Armin Größlinger, Dezember 2009)
Erweitert das Polyedermodell zur Schleifenparallelisierung um gewisse Nicht-linearitäten auf Modellebene. Anwendungen sind z. B. Abhängigkeitsanalyse mit einem nichtlinearen Parameter, Berechnung nichtlinearer Zeitverteilungen, Kacheln mit unterschiedlichen Kachelgrößen und Codeerzeugung für beliebige polynomiale Schleifengrenzen.
"Code Optimization in the Polyhedron Model - Improving the Efficiency of Parallel Loop Nests" (Peter Faber, Juli 2008)
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, Oktober 1996)
Zeigt, wie das für die Parallelisierung von verschachtelten FOR-Schleifen ideal geeignete Polytopmodell so erweitert werden kann, dass auch WHILE-Schleifen behandelt werden können; insbesondere werden die für die Code-Erzeugung entstehenden Probleme aufgezeigt und gelöst.

"Improving the Efficiency of Code Generation Based on Cylindrical Algebraic Decomposition" (Thomas Lang, März 2018)
Diese Arbeit betrachtet die Codegenerierung für Schleifensätze mit Hilfe zylindrischer algebraischer Dekomposition and präsentiert eine Implementierung in C++, die mehrere für die Praxis relevante Verbesserungen enthält, u.a. algorithmitsche Fortschritte sowie eine Feinabstimmung der Codegenerierung für wichtige Spezialfälle.
"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 Haskell-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.

"Partial Evaluation in Template Haskell" (Klara Schlüter, Januar 2019)
Ein prototypischer partieller Auswerter wird in Template Haskell implementiert. Die partielle Auswertung erfolgt online und Bindungszeitanalyse wird automatisch während der Spezialisierung durchgeführt.
"Multigrid for the SPIRAL prototype in Scala" (Sebastian Schweikl, September 2017)
Kürzlich wurde ein Multigrid-Löser einer diskretisierte, quadratische, zweidimensionale Poisson-Gleichung mit Dirichlet Randbedingungen für eine automatische Codegenerierung mit dem Programmsynthesesystem SPIRAL spezifiziert. Die Arbeit überträgt diese Spezifikation auf die teilweise Reimplementierung SpiralS von SPIRAL in Java und stellt die erforderlichen domänenspezifischen Sprachmittel zur Verfügung. Leistungsoptimierungen werden mit einer schrittweisen Verfeinerung des Algorithmus erreicht.
"An Intel ® Xeon Phi TM Backend for the ExaStencils Code Generator" (Thomas Lang, April 2016)
Der Code-Generator von ExaStencils wird so erweitert, dass er den Intel Xeon Phi Koprozessor unterstützt. Die verschiedenen Programmiermodelle des Koprozessors werden auf ihre Eignung für Stencils-Berechnungen untersucht.
"Efficient Preoptimization Sequences for Polly" (Christoph Woller, August 2014)
Mittels heuristischer Verfahren und genetischer Algorithmen wird eine bessere Voroptimierungssequenz für das Polly-Modul zur Modellierung polyedrischer Schleifensätze in LLVM bestimmt.
"Analysis and Extension of Existing Tiling Algorithms for Stencil Computations" (Michael Freitag, Juli 2014)
Die Kachelungsalgorithmen von der Systeme Pochoir, Pluto und SDSL werden verglichen, in einem einheitlichen Framework implementiert und mittels dynamischem Scheduling wird eine Erhöhung der Performanz erreicht.