Available Theses

Title Student(s) Supervisor Description
Automatische Analyse für Parallele Programme 1 Thomas Fahringer details
Betriebssystem Services und Visualisierung 1 Thomas Fahringer details
Parallel Numerical Receipts in OpenMP and OpenCL 1 Juan J. Durillo details
Resource tracking tool using dynamic instrumentation 1 Radu Prodan details
Triangular decomposition algoritms for large sparse matrices on GPU using OpenCL 1 Radu Prodan, Klaus Kofler details
Debugging tool using dynamic instrumentation 1 Radu Prodan details
On-the-fly code coverage tool 1 Radu Prodan details

Title Automatische Analyse für Parallele Programme
Number of students 1
Language German
Supervisors Thomas Fahringer
Description Das Ziel dieser Arbeit ist ein Werkzeug für die automatische Abhängigkeitsanalyse ausgehend von einer Eingabemaske für geschachtelte Schleifen. Die Abhängigkeitsanalyse soll für eine geschachtelte Schleife feststelle um welche Datenabhängigkeit es sich handelt (true, anti, output, input). Zusätzlich soll der Direction Vector und und die Distanz der Abhängigkeit angegeben werden. Daneben soll noch eine Prediction für die Anzahl der Cache Misses für das Schleifennest erstellt werden. Die Aufgabe kann mit einer beliebigen Programmiersprache entwickelt werden. Die zu untersuchenden Programme sollen C Programme sein.
Tasks
  • Studieren der Datenabhängigkeitsanalyse zur Feststellung ob eine Schleife parallel oder seriell ausgeführt werden kann bzw. muss.
  • Studieren eines vorgegebenen analytischen Algorithmus zur Abschätzung der Anzahl der Cache Misses für geschachtelte Schleifen.
  • Visualisierung der Ergebnisse.
  • Eingabeformat der zu analysierenden Codeteile soll entworfen werden.
Theoretical skills Datenabhängigkeitsanalyse (z.B. polyhedral library, omega test, etc.).
Vorkenntnisse zur Parallelisierung von Programmen
Practical skills scripting Sprache, C oder C++
Additional information

Title Betriebssystem Services und Visualisierung
Number of students 1
Language German
Supervisors Thomas Fahringer
Description Das Ziel dieser Arbeit ist die Entwicklung von einigen Standard-Services aus Betriebssysteme (z.B. Prozessscheduling, Deadlocks, Seitenersetzungsverfahren).
Es sollen beliebige Eingabedaten vom Benutzer eingegeben werden können, um die Services zu testen. Eine Visualisierung soll verschiedene Verfahren (z.B. Prozessscheduling) miteinander vergleichen.
Die Aufgabe kann auch als Web-Anwendung realisiert werden.
Tasks
  • Studieren von mehreren Betriebssystemalgorithmen, die in der Vorlesung vorgestellt worden sind.
  • Implementieren einer sinnvollen Schnittstelle für die Eingabedaten.
  • Visualisierung der Ergebnisse.
  • Eventuell als Web-Anwendung zu realisieren.
Theoretical skills Inhalt der Vorlesung Betriebssysteme
Practical skills  C, C++ oder Java
Additional information

Title Parallel Numerical Receipts in OpenMP and OpenCL
Number of students 1
Language English
Supervisors Juan J. Durillo
Description Hardware performance is usually benchmarked by executing programs stressing different computing units. Nowadays, in the multi- and many- core era, computational resources are composed of more and more cores/processing units, opening a new era for programmers, who must adapt their sequential codes for exploiting the performance offered by these new parallel architectures. In this sense, today’s programmers should not restrict themselves to CPU, but they also must target other architectures like GPU or co-processors (like Intel Phi). The purpose of this thesis is to implement a repository composed of several numerical recipes using OpenMP and OpenCL. This repository will be further used for benchmarking different parallel architectures. Additionally, comparisons between OpenMP and OpenCL implementations shuuld be provided.
Tasks
  • Study numerical receipts codes
  • Analyse dependences
  • Provide OpenMP and OpenCL implementations of the numerical receipts
  • Validate the parallel implementations
  • Benchmarking and comparing several architectures
Theoretical skills
Practical skills
Additional information Bibliography: Willian H. Press, Saul A. Teukolsky, William T. Vetterling and Brian P. Flannery. Numerical Recipes in C. Second Edition.

Title Resource tracking tool using dynamic instrumentation
Students 1
Supervisor Radu Prodan
Language German, English
Description The normal cycle of developing a program is to edit the source code, compile it, and then execute the resulting binary. However, sometimes this cycle can be too restrictive. We may wish to change the program while it is executing, and not have to recompile, relink, or even reexecute it to change the binary. The dynamic instrumentation technology permits the modifications of applications on-the-fly during their execution, and the Dyninst library provides a machine independent API to permit the creation of tools and applications using dynamic instrumentation.

The goal of this thesis is to develop a resource tracking tool based on dynamic instrumentation. Resources can be memory (i.e. monitoring memory allocation and deallocation), open files, System V interprocess communication (shared memory, message queues, semaphores), processes, pipes, POSIX threads, etc. The purpose of the tool is to test a program for correct behaviour.
Tasks
  • Study C standard library and POSIX, System V and BSD system calls
  • Develop data structures to efficiently track resource usage
  • Provide instruments to track resource usage using dynamic instrumentation
  • Track correct/incorrect memory usage (i.e. writes to non-allocated memory, off-by-one errors, buffer overruns)
Theoretical skills Compiler construction, Operating systems
Practical skills C/C++, POSIX, UNIX
Additional information Dyninst

Title
 Triangular decomposition algoritms for large sparse matrices on GPU using OpenCL
Student Michael Stather
Language Deutsch
Supervisor Radu Prodan, Klaus Kofler
Beschreibung Ziel dieser Bachelorarbeit ist es Algorithmen zur Triangulierung sehr grosser Sparse-Matrizen ( zB LU, LDLt, …) auf ihre Eignung für die Implementierung auf GPUs zu untersuchen. Einige dieser Algorithmen sollen in OpenCL implementiert werden. Die Verwendbarkeit und Performace dieser Implementierung soll durch Vergleiche mit bestehnden Libraries ( zB Magama) ermittelt werden.
Tasks
  • Einarbeiten in OpenCL
  • Einarbeiten in Grundlagen Lineare Algebra und Numerik zum Verständnis der Algorithmen
  • Implementierung verschiedener Algorithmen in OpenCL
  • Performace-Analyse
Practical skills
  • C++
  • OpenCL
  • Grundlagen Matrizen/Numerik

Title
 Debugging tool using dynamic instrumentation
Number of students 1
Supervisor Radu Prodan
Language German, English
Description The normal cycle of developing a program is to edit the source code, compile it, and then execute the resulting binary. However, sometimes this cycle can be too restrictive. We may wish to change the program while it is executing, and not have to recompile, relink, or even reexecute it to change the binary. The dynamic instrumentation technology permits the modifications of applications on-the-fly during their execution, and the Dyninst library provides a machine independent API to permit the creation of tools and applications using dynamic instrumentation.

The goal of this thesis is to develop a simple command-line debugging tool online (gdb-like) based on the dynamic instrumentation technology.
Tasks
  • Study of the gdb command line interface and identification of the sub-functionality to be implemented
  • Create, attach, and detach a process
  • Start, resume, stop, kill a process
  • Breakpoint management
  • Call stack manipulation using the Stackwalker library
  • Symbol table manipulation using the Samtab library
Theoretical skills Compiler construction, Operating systems
Practical skills C, POSIX, UNIX
Additional information Dyninst

Title
 On-the-fly code coverage tool
Number of students 1
Supervisor Radu Prodan
Language German, English
Description The normal cycle of developing a program is to edit the source code, compile it, and then execute the resulting binary. However, sometimes this cycle can be too restrictive. We may wish to change the program while it is executing, and not have to recompile, relink, or even reexecute it to change the binary. The dynamic instrumentation technology permits the modifications of applications on-the-fly during their execution, and the Dyninst library provides a machine independent API to permit the creation of tools and applications using dynamic instrumentation.

The goal of this thesis is to develop an efficient online code coverage tool using the dynamic instrumentation technology that determines whether each line of code is hit or not by the program counter during the program execution. The final goal of this tool is to identify potential dead code in the application.
Tasks
  • Design an efficient code coverage algorithm that incrementally adds and removes instrumentation code with minimum intrusion
  • Overhead and scalability analysis of the algorithm
  • Portability analysis on at least two platforms with different operating systems
Theoretical skills Compiler construction, Operating systems
Practical skills C, POSIX, UNIX
Additional information Dyninst