Faculty of Computer Science and Mathematics
Completed Habilitation Theses
- "Automatic Parallelization of Loop Programs for Distributed Memory Architectures" (Martin Griebl, December 2004)
Presents all necessary phases of automatic, model-based parallelization. The central aspects are, first, a refinement of the model by index set splitting and, second, a tiling of the parallelized program in order to adapt the communication overhead to the target architechture's parameters (e.g., number of processors, ratio between communication and computation cost).
- "Abstraction and Performance in the Design of Parallel Programs" (Sergei Gorlatch, July 1997)
Presents a systematic approach based on abstracting low-level details of parallelism. Describes methods of transforming abstract specifications into efficient algorithms and experiments with target programs on parallel machines.
- "The Challenges of Non-linear Parameters and Variables in Automatic Loop Parallelisation" (Armin Größlinger, December 2009)
Extends the polyhedron model for loop parallelization to cover certain non-linearities at the level of the model. Applications are, e.g., analyzing dependences in the presence of one non-linear parameter, computing non-linear schedules, applying tiling with non-fixed tile sizes and generating code for arbitrary polynomial loop bounds.
- "Code Optimization in the Polyhedron Model - Improving the Efficiency of Parallel Loop Nests" (Peter Faber, July 2008)
Introduces common subexpression elimination to automatic loop paralleization with the polyhedron model. Expressions with a common value are identified. One computation of the value is being placed in time and space, and further uses of this value are facilitated via references.
- "PolyAPM: Comparative Parallel Programming with Parallel Abstract Machines" (Nils Ellmenreich, August 2004)
Uses parallel abstract machines as interpreters for intermediate programs in a program refinement tree, whose root os a problem specification and whose leaves are efficient target programs. As a decision aid for the selection of refinements, a cost model can be applied to an intermediate refinement to predict the performance of target programs it may lead to.
- "The Skeleton-Based Parallelization of Divide-and-Conquer Recursions" (Christoph Herrmann, June 2000)
Demonstrates the efficient parallelization of skeleton-based divide-and-conquer programs in the functional language HDC.
- "Object-Oriented Specification of Distributed Systems" (Ulrike Lechner, June 1997)
Describes new concepts for object-oriented specification of distributed systems, for modeling, structuring and reusing as well as for verification and refinement of these specifications.
- "The Mechanical Parallelization of Loop Nests Containing while Loops" (Martin Griebl, October 1996)
Describes how the polytope model, useful for the automatic parallelization of nested FOR loops, can be adapted to WHILE loops; esp. the problems ocurring in code generation are described and solved.
Selection of Completed Master Theses
- "Improving the Efficiency of Code Generation Based on Cylindrical Algebraic Decomposition" (Thomas Lang, März 2018)
This thesis focuses on the code generation for loop nests based on cylindrical algebraic decomposition and presents an implementation in C++ which incorporates several improvements for cases relevant in practice, including both algorithmic enhancements and tuning of the code generation for important special cases.
- "A Performance Prediction Function based on the Exploration of a Schedule Search Space in the Polyhedron Model" (Dominik Danner, Februar 2017)
This master's thesis presents an extension of Polyite, a tool for iterative schedule optimization in the Polyhedron Model, with a prediction of schedules' performance. The prediction function is composed of several features that address various aspects of the schedules. The quality of the predictions has been evaluated.
- "Polyhedral Optimization for GPU Offloading in the ExaStencils Code Generator"(Christoph Woller, Oktober 2016)
The code generator for graphics processors in project ExaStencils is extended by a polyhedral code generation which supports shared memory and read-only cache in addition to spatial blocking as optimization techniques. For selected examples, exploration is used to find the best schedule. The capability of the code generator is demonstrated using a real-world stencil problem.
- "Combining the DKU Pattern with Polyhedral Optimization and Tiling" (Stefan Kronawitter, April 2013)
The Divider, Kernel and Undivider program parts needed for the Divider-Kernel-Undivider pattern for data parallelism are generated automatically from a given specification or sequential implementation using methods of polyhedral parallelization.
- "Performance Exploration of Selected Manually and Automatically Parallelized Codes on GPUs" (Franz Xaver Bayerl, March 2012)
This thesis studies the performance of selected parallel versions of matrix multiplication on graphics processors.
- "Enabling Polyhedral Optimizations in LLVM" (Tobias Grosser, April 2011)
This thesis presents Polly, an infrastructure making optimizations using the polyhedron model available to LLVM.
- "Alternative Features in Colored Featherweight Java" (Malte Rosenthal, July 2009)
This thesis proposes an extension of a product line type system that supports alternative features.
- "Feature-Oriented Composition of XML Artifacts" (Jens Dörre, March 2009)
Looks into applying to XML languages the compositional approach to feature-oriented software design. Therein the language-independent, grammar-based tool FeatureHouse is extended to a prototype for languages based on XML Schema. However, these semi-structured languages form a class of languages wider than the class of modern programming languages; hence there are additional challenges for feature composition.
- "Extending a Task Farming Framework with Dependences to P2P Communications" (Philipp Claßen, February 2009)
In this thesis, the master-worker HOC is replaced by a new P2P-HOC that extends the taskfarming scheme by peer-to-peer communication between workers, thus increasing the scalability and performance of the target application.
- "On Algorithmic and Heuristic Approaches to Integral Problems in the Polyhedron Model with Non-linear Parameters" (Stefan Schuster, June 2007)
This thesis examines possibilities to describe the integral solutions to certain problems occurring in the polyhedron model with non-linear parameters exactly. In particular, the solvability of systems of linear Diophantine equations as they appear in Banerjee's data dependence analysis is studied.
- "SPARK for Concurrent Programming" (Michael Haller, March 2006)
SPARK is an environment for the automatic verification of Ada programs which, however, caters only to a subset of Ada. Concurrency is one of the features which are not permitted. The thesis proposes a SPARK variant, called PassauSPARK, which can be used to verify monitors in process/monitor programs. A case study is the prototypical operating system of a routing node in a processor network.
- "Automatic Code Generation for Distributed Memory Architectures in the Polytope Model" (Michael Claßen, September 2005)
This thesis presents a fully automated method for generating efficient target code within the framework of the LooPo project. The generated communication code enables the execution on clusters that are based on a distributed memory architecture. In order to achieve a good message vectorization, the tiling technique is used to increase the granularity of parallelism in the program. The implementation uses a combination of C/C++ and MPI as target language.
- "Tuning MetaOCaml Programs for High Performance" (Tobias Langhammer, September 2005)
This thesis consists of a comprehensive analysis how to achieve, in the presence of abstract programming paradigms, performance results with MetaOCaml, which are usually subject to languages close to the hardware, like C or Fortran. Background information and further publications of Tobias Langhammer are available on the metaprogramming project page.
- "Extending the Polyhedron Model to Inequality Systems with Non-linear Parameters using Quantifier Elimination" (Armin Größlinger, September 2003)
The polyhedron model usually allows parameters to appear only linearly in inequalities, i.e., products of parameters or of parameters and variables are not allowed. This thesis examines the possibility of extending the polyhedron model to allow non-linear parameters which are, e.g., necessary for tiling with parametric tile sizes. The main mathematical tool to achieve this generalization is quantifier elimination in the real numbers.
- "Parallelization of Loop Nests with General Bounds in the Polyhedron Model" (Max Geigl, March 1997)
One part examines the implications of different loop types for target code generation and integrates the results in a class hierarchy. Another part extends the polyhedron model to imperfect loop nests containing general for loops, while loops and (plain) if statements.
- "Practical Methods for Scheduling and Allocation in the Polytope Model" (Wolfgang Meisl, September 1996)
Describes time mapping (scheduling) methods by Darte/Vivien and space mapping (allocation) methods by Darte/Dion/Robert, as well as extensions, and comments on their implementation in LooPo.
- "Automatic Code Generation in the Polytope Model" (Sabine Wetzel, November 1995)
Describes code generation algorithms for space-time mappings based on methods by Lamport and Feautrier. Implemented in the LooPo project.
Selection of Completed Bachelor Theses
- "Multigrid for the SPIRAL prototype in Scala" (Sebastian Schweikl, September 2017)
Recently, a multigrid solver for a discretized square two-dimensional Poisson equation with Dirichlet boundary conditions was specified for an automatic code generation by the program synthesis system SPIRAL. The thesis ports this work to the partial reimplementation SpiralS of SPIRAL in Scala and provides the domain-specific language structures for its code generation. Performance optimizations are achieved by a gradual refinement of the algorithm’s structure.
- "An Intel®Xeon Phi™Backend for the ExaStencils Code Generator" (Thomas Lang, April 2016)
The thesis reports on an extension of the ExaStencils code generator for the Intel Xeon Phi co-processor, including an evaluation of the suitability of various programming models for stencil computations.
- "Efficient Preoptimization Sequences for Polly" (Christoph Woller, August 2014)
The thesis identifies an improved pre-optimization sequence for the modeling of polyhedral loops nests in LLVM plug-in Polly. The techniques used are heuristics and genetic algorithms.
- "Analysis and Extension of Existing Tiling Algorithms for Stencil Computations"(Michael Freitag, July 2014)
Tiling strategies for the systems Pochoir, PLuTo and SDSL have been implemented in a common framework and compared. Dynamic scheduling yields an improvement in performance.