Theses

• Selection of Completed Master Theses
• Completed Dissertations
• Completed Habilitation Theses

Selection of Completed Master Theses

• "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, Mar. 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, Sep. 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, Sept. 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, Sept. 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, Mar. 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, Sept. 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, Nov. 1995)
  Describes code generation algorithms for space-time mappings based on methods by Lamport and Feautrier. Implemented in the LooPo project.

Completed Dissertations

• "Code Optimization in the Polyhedron Model - Improving the Efficiency of Parallel Loop Nests" (Peter Faber, October 2007)
  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, Oct. 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.

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.