New theses starting after winter semester 2007
|
Title
|
Student
|
Supervisor
|
Description
|
| Parallelismus bei der Berechnung der Inversen Kinematik eines Roboters |
Kofler, Moosbrugger |
Hans Moritsch |
details here |
| Developing an MMOG with automatic content generation |
Bernd Altstätter, Daniel Gasteiger |
Vlad Nae |
details here |
| Resource tracking tool using dynamic instrumentation |
David Obwaller |
Radu Prodan |
details here |
| Implementing Ray Tracing by exploiting OpenCL Vector Type |
Thomas Trenkwalder |
Biagio Cosenza |
details here |
| Reporting tool for the INSIEME compiler project |
Michael Gasser |
Hans Moritsch |
details here |
| A data file converter for the F5 Project |
Wolfgang Leimer |
Thomas Fahringer |
details here |
| Computation of huge primes in OpenCL |
Stefan Rebitsch |
Thomas Fahringer |
details here |
| Verwaltungssystem für Literaturreferenzen |
Martin Klotz |
Thomas Fahringer |
details here |
| Automatic benchmarking tool |
Simon Schuler |
Simone Pellegrini |
details here |
| Workflow Execution Simulation |
Felix Koenig |
Kassian Plankensteiner |
details here |
Details for the theses
| Title |
Parallelismus bei der Berechnung der Inversen Kinematik eines Roboters |
| Students |
Kofler, Moosbrugger
|
| Supervisor |
Hans Moritsch |
| Language |
Deutsch |
| Description |
Im Rahmen dieser Bachelorarbeit soll eine existierende Parallelisierung eines Algorithmus zur Berechnung der Inversen Kinematik eines Roboters analysiert und weiterentwickelt werden. Dabei soll auch noch nicht genutztes Parallelisierungsspotential ausgeschöpft werden. Programmiersprache: C-Sharp |
| Tasks |
- Einarbeiten in den Algorithmus zur Berechnung der Inversen Kinematik
- Einarbeiten in C-Sharp
- Einarbeiten in die existierende Parallelisierung
- Identifikation von Parallelisierungsspotential
- Erweiterung der parallelen Implementierung
- Experimentelle Evaluation, Laufzeitmessungen
|
| Theoretical skills |
Objektorientiertes Programmieren, Multi-Thread Programmierung |
| Practical skills |
C |
| Title |
Developing an MMOG with automatic content generation |
| Students |
Bernd Altstätter, Daniel Gasteiger
|
| Supervisor |
Vlad Nae |
| Language |
English |
| Description |
Massively Multiplayer Online Games (MMOGs) are a new type of large-scale distributed applications characterised by a real-time, persistent, virtual world entertaining millions of players. Today’s MMOGs can include millions of concurrent players spread across the world and interacting with each other within a single session.
The aim of this project is twofold:
1) the development of an MMOG capable of supporting more than a thousand of clients within a single distributed and persistent session;
2) implementation of a content generation algorithm to create functional game worlds and assist the players in creating their own content.
The core of the MMOG will be a distributed server application which manages all the game data, accepts new client connections and distributes them among the available machines. The content generation algorithm should be based on different existing procedural generation algorithms such as the Perlin noise or stochastic algorithms, like fractal landscaping. |
| Tasks |
|
| Theoretical skills |
Distributed systems, Networking |
| Practical skills |
Java, JMonkeyEngine |
| Additional information |
http://jmonkeyengine.com/ |
| Title |
Resource tracking tool using dynamic instrumentation |
| Students |
David Obwaller
|
| 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
|
Implementing Ray Tracing by exploiting OpenCL Vector Type |
| Student |
1Thomas Trenkwalder |
| Language |
English |
| Supervisor |
Biagio Cosenza |
| Description |
In computer graphics, ray tracing is a technique for generating an image by tracing the path of light through pixels in an image plane. Ray tracing is capable of simulating a wide variety of optical effects, such as reflection and refraction, scattering, and chromatic aberration. However, ray tracing is even known to be compute-expensive.
OpenCL is a parallel programming language that takes advantage of nowadays multi-processors hw. An interesting feature of OpenCL is the availability of a vector type that easily exploits the underlying vector unit.
The aim of this thesis is to implement a ray tracer by using OpenCL and exploiting its vector type availability.
|
| Tasks |
- Familiarize with OpenCL
- Study a basic OpenCL implementation of the ray tracing algorithm
- Implement a packet-based ray tracing by using the underlying vector type and a Structure-of-Array memory arrangement
- Use the proposed framework to implement two test rendering algorithms: Whitted ray tracing and Instant Radiosity
|
| Theoretical skills |
Basic knowledge of parallel computing |
| Practical skills |
- C/C++
- Computer graphics and/or visualization background is a plus
|
| Additional information |
|
Title
|
Reporting tool for the INSIEME compiler project |
| Student |
Michael Gasser |
| Language |
German |
| Supervisor |
Hans Moritsch |
| Description |
Im Rahmen der Entwicklung des Insieme Compilation System, das die Implementierung eines Compiler und eines optimierendes Laufzeitsystem einschliesst, ergibt sich die Notwendigkeit, die Fortschritte in diesem umfangreichen Projektes zu protokollieren und in Form von automatisch generierten Berichten zu dokumentieren. Die dazu erforderlichen Daten werden sowohl über Kommandozeile als auch über eine Webanwendungvon an das zu erstellende Reporting-Tool übermittelt und von diesem in Form von Diagrammen dargestellt. Die Daten sollen nach konfigurierbaren Kriterien gefiltert und die erzeugten Diagramme entsprechend dynamisch angepasst werden können.
|
| Tasks |
- Einarbeitung in Aufbau und Funktion des Insieme Compilers
- Auswahl geeigneter Programmbibliotheken für Diagrammerstellung
- Design
- Implementierung
- Test, Experimente
|
| Practical skills |
Java, JDBC, Swing |
Title
|
A data file converter for the F5 Project |
| Student |
Wolfgang Leimer |
| Supervisor |
Thomas Fahringer |
| Language |
English or German |
| Description |
With the increasing use of sensor technology in GEO-sciences data storage and organization becomes crucial. Different types of data from different sources such as satellite images, photogrammetric images, LIDAR laser data or shape files are the basis for researchers of different GEO-scientific domains. The file format F5 ( http://www.fiberbundle.net/ ) is based on HDF5 and already supports to store satellite and LIDAR data. This thesis first develops a concept on how to store shape files into F5 and then implements a data file converter in C++, while providing performance measurements on the HDF5 layers. Finally, a 3D visualization a combined data set consisting of satellite images, LIDAR data and shape files is created in VISH ( http://vish.origo.ethz.ch/ ), a scientific 3D visualization tool supporting the F5 data model. |
| Tasks |
- Familiarize with HDF5 and F5
- Develop an algorithm to convert shape files into F5 format
- Performance analysis of the implemetation
|
| Theoretical skills |
|
| Practical skills |
|
| Additional information |
|
Title
|
Computation of huge primes in OpenCL
|
| Student |
Stefan Rebitsch |
| Supervisor |
Thomas Fahringer |
| Language |
English or German |
| Description |
One ongoing research in number theory is, how one can gather huge prime numbers for cryptography and other usages, say 100000 and more digits. This bachelor thesis focus on an implementation for OpenCL, which is a brand new industrial standard for programming CPUs, GPUs and other accelerators.
Einer der derzeitigen Forschungsgebiete der Zahlentheorie ist es, sehr grosse Primzahlen zu ermitteln und diese Eigenschaft nachzuweisen. Grosse Primzahlen werden in der Kryptographie und in vielen anderen Bereichen verwendet. Die Bachelorarbeit fokussiert dabei nicht auf neue Algorithmen der Zahlentheorie, sondern auf eine optimierte Umsetzung der Integer-Implementation fuer OpenCL, welches ein neuer Industriestandard fuer das Programmieren von CPUs, Grafikprozessoren und anderen Beschleunigern (Cell) ist. |
| Tasks |
- Read background literature
- Usage of OpenCL environment
- Implement a huge-Integers data structure and needed operations in an optimized way
- Implement different prime number testing (naive, sieve, ...)
- Benchmark on CPUs/GPUs/... (suite provided)
|
| Theoretical skills |
- Interests in low-level data structures
- (Interests in number theorie)
|
| Practical skills |
C |
Titel
|
Verwaltungssystem für Literaturreferenzen |
| Studente |
Martin Klotz |
| Betreuer |
Thomas Fahringer |
| Beschreibung |
Es soll eine Web-Anwendung erstellt werden, das Literatureinträge erfasst und diese dann in verschiedenen Formaten ausgeben kann, wie z.B. bibtex, ascii sowie html. Literatureinträge sollen sortiert bzw auch formatiert werden können. Literatureinträge können gefiltert werden, derart dass nur eine Teilmenge der Literaturreferenzen ausgegeben werden. Die Web-Anwendung soll über eine Mechanismus zur Authentifizierung gesichert werden. |
| Aufgaben |
Folgende Komponenten sind Teil der WEB-Anwendung:
- Erfassen der Literaturreferenzen
- Erstellen eines Literaturverzeichnisses durch Filtermethoden
- Web Authentifizierungsmechanismus
- Suchen und Filtern von Literatureinträgen
- Ausgabe der Literaturreferenzen mit verschiedenen Formaten (Bibtex, html, ascii, ...)
- Laden von Literaturdatenbanken in die Web-Anwendung
|
| Theoretische Kenntnisse |
Grammatiken, Compilerbau |
| Praktische Kenntnisse |
Web-Anwendungsprogrammierung, Latex, HTML |
Title
|
Webinterface for FLD
|
| Number of students |
Martin Klotz |
| Supervisor |
Thomas Fahringer |
| Language |
English or German |
| Description |
The FLD - documentation of research done - is an university and inter-university collection of the active research done at the divers institutes. Conference papers as well as editor-ships and public works are recorded.
This bachelor thesis should create an interface for entering all necessary information into an own database, while it provides and validates(!) most information out of a given DOI-Link and IEEE/Springer/ACM/DBLP libraries. It should generate BibTeX and an overview/report.
The used back-end (frameworks/languages/own things/...) can be discussed.
Die FLD - Forschungsleistungsdokumentation - ist eine universitaere und interuniversitaere Zusammenfassung der aktiven Forschung. Hier werden nicht nur Papers von Konferenzen eingetragen, sondern auch Editorenschaften und  Oeffentlichkeitsarbeit.
Diese Bachelorarbeit soll nun ein Interface zum Eintragen aller notwendigen Informationen anbieten, wobei moeglichst vieles automatisch aus DOI-Link bzw IEEE/Springer/ACM/DBLP-Bibliothek generiert und vor allem auch ueberprueft, werden soll. Die Implementation soll sowohl BibTeX als auch eine Uebersicht ausgeben koennen.
Welches Back-End verwendet werden soll (Framework/Sprache/eigenes...) ist dem Studenten, in Absprache mit dem Betreuer, selber ueberlassen. |
| Tasks |
- Read background literature (given by supervisor)
- Evaluate information required (with supervisor)
- Build up a "simple" interface and the output.
- Evaluate information retrievable by DBLP/...
- Build a system to retrieve information
- Test the tool.
|
| Theoretical skills |
Web, Validation |
| Practical skills |
Web-developement (framework discussable), Databases |
Title
|
Automatic benchmarking tool
|
| Number of students |
1-2 |
| Supervisor |
Simone Pellegrini |
| Language |
English |
| Description |
Program autotuning is a complex task which needs to be supported by proper tools. Usually several program version need to be generated, compiled and executed on different architectures. In such a process, parameters (i.e. compilation flags, program input parameters, environment variables, etc...) are varied to determine their correlation with the program performance. The data generated during the simulation is then extracted from the output of the program, elaborated and collected for further analysis or visualization. |
| Tasks |
The goal of the thesis is to develop a highly configurable tool able to take care of the entire process described above. The benchmarking tool should be able to read all the information required (compiler flags, input parameters, etc...) from a configuration file (related to a particular benchmarking run) and then run the program considering all the combinations of the parameters specified by the user. As the evaluation of a complete benchmarking run can take several days, a resume function should be implemented. All the useful data generated by the benchmark should be collected in a database for further analysis.
- Familiarize with the program evaluation problem
- Define a simple language for benchmark description
- Design a database to store the results of a benchmarking run
- Enable visualization of the results (eg. using Matlab or Gnuplot)
As the tool should execute on several architectures (x86, SPARC, ia64) and different OS (Linux, Solaris, Windows) the use of a scripting language (like Ruby or Python) is preferred. |
| Theoretical skills |
Regular Expressions, RDBMS |
Title
|
Workflow Execution Simulation
|
| Number of students |
1-2 |
| Supervisor |
Kassian Plankensteiner |
| Description |
Simulation is a very important technique in research for distributed systems such as Grids and Clouds. Compared to real world experiments, simulated experiments have the benefit of reproducibility of results. In this bachelor thesis, the students will develop a small workflow execution environment that is able to schedule and execute simple workflow applications. They will get familiar with high performance computing on distributed systems and workflow application scheduling based on an existing efficient scheduling algorithm. All of their work will be carried out in a simulated environment based on the new GroudSim simulator. |
| Tasks |
- Understand the workflow application model by reading background literature (given by supervisor)
- Understand the HEFT list scheduling algorithm for DAG-based workflow applications (given by supervisor)
- Try example programs to understand how to use GroudSim (given by supervisor)
- Implement a system consisting of three components
- A workflow generator that generates simple DAG-based workflows as simulation input
- A scheduler component that uses the HEFT algorithm to schedule the workflow
- An execution component that sends the workflow tasks to GroudSim for simulated execution
- Test the simulation with randomly generated workflows and summarize the results.
|
| Theoretical skills |
should have an interest in distributed systems and high performance computing as well as algorithms and data structures
should be able to understand a new API (GroudSim) quickly |
| Practical skills |
Java programming |
