Difference between revisions of "Student Projects"

From Sccswiki
Jump to navigation Jump to search
Line 35: Line 35:
 
== Computational Fluid Dynamics (CFD) ==
 
== Computational Fluid Dynamics (CFD) ==
  
[[Image:StudentProjects_fsi.jpg]] [[Image:StudentProjects_driftRatchet.png]]
+
[[Image:StudentProjects_fsi.jpg]] [[Image:StudentProjects_driftRatchet.jpg]]
 
<br>
 
<br>
  
Line 200: Line 200:
  
 
Mittels der verschiedenen Lösungstechniken kann eine SUDOKU-Analysierer entwickelt werden zur Bestimmung des Schwierigkeitsgrades eines SUDOKU-Problems, abhängig von Art und Anwendung der verschiednen Lösungstechniken.
 
Mittels der verschiedenen Lösungstechniken kann eine SUDOKU-Analysierer entwickelt werden zur Bestimmung des Schwierigkeitsgrades eines SUDOKU-Problems, abhängig von Art und Anwendung der verschiednen Lösungstechniken.
 +
 +
[[Image:StudentProjects_sudoku.jpg]]
  
 
Vorkenntnisse: Kenntnisse in C++ oder Java, GUI
 
Vorkenntnisse: Kenntnisse in C++ oder Java, GUI

Revision as of 07:38, 22 July 2008

Studentische Arbeiten? Hier?? Wo sonst?

Diese Seite ist gedacht für alle, die sich vorstellen können, am Lehrstuhl SCCS eine studentische Arbeit

  • Praktikum Systementwicklung (PSE)
  • Systementwicklungsprojekt (SEP) / Fortgeschrittenenpraktikum / Studienarbeit
  • Bachelor- / Master- / Diplomarbeit
  • Interdisziplinäres Projekt (IDP)
  • bei manchen Projekten ggf. auch als studentische Hilfskraft
  • ...

in ihrem Studiengang

  • Informatik
  • Mathematik
  • CSE
  • ...

zu machen.

Wegen der Vielzahl der Kombinationen, die sich aus obigen Möglichkeiten ergeben und der noch viel größeren Zahl individueller Präferenzen (die sind wichtiger als der formale Rahmen - wesentlich ist, dass man ein Themenfeld findet, das einem Spaß macht!), schreiben wir im Regelfall keine konkreten Arbeiten aus, sondern erklären hier, auf welchen Feldern wir Euch Themen anbieten können.

Falls Ihr Euch für etwas davon interessiert: man besten per Mail anfragen (Fragen kostet nix und verpflichtet zu nix!).

Dabei dürften folgende Angaben hilfreich sein:

  • Studiengang
  • Semester
  • Art der Arbeit
  • ggf. Vorkenntnisse - einschlägige Vorlesungen, Seminare, Praktika etc.
  • und natürlich Eure Interessensgebiete

(Das SCCS-Kolloquium ist eine weitere gute Gelegenheit, etwas über Themen zu lernen, die bei uns bearbeitet werden; Gäste sind dort willkommen!)

Und hier kommen die Themenfelder:

Computational Fluid Dynamics (CFD)

StudentProjects fsi.jpg StudentProjects driftRatchet.jpg

The simulation of various flow phenomena and the development of software for this purpose are among the core subjects of our group. We offer topics for projects (such as PSE) and theses (BA/MA/Diploma) from various application areas such as turbulence, particle transport, effects on a microscale (Brownian motion etc.), and fluid-structure interaction.

To achieve efficient and accurate codes, we apply mathematical methods (finite element method, multigrid, numerical time integration schemes, etc.) as well as computer science techniques (parallelisation, cache- and runtime-optimisation, high performance computing, grid computing, etc.). The focus of a project or a thesis can be chosen to be either in one or both of these two fields.

Further information on possible projects: concrete project topics in Computational Fluid Dynamics (CFD)

Contact:

  • Dr. rer. nat. Miriam Mehl,
  • Ioan Lucian Muntean: parallelisation, high performance computing, grid computing, turbulence,
  • Tobias Neckel: fluid-structure interaction, particle transport, finite element method, turbulence, multigrid, high performance computing,
  • Tobias Weinzierl: particle transport, multigrid, parallelisation, cache- and runtime-optimisation, high performance computing.


Programming of Supercomputers: from Algorithms to Applications

For various systems, ranging from multicore machines to supercomputers (comprising tens of thousands of processors), parallelization and hardware awareness are THE WAY to achieve outstanding performance. Load balancing, minimization of the interprocess communication, or software tuning are just some of the issues playing a decisive role in the development of efficient application software for high performance computers.

Students will typically adapt existing algorithms of practical interest to the requirements of concrete systems, such as shared-memory computers or clusters. The applications in focus are mainly from the field of computational science and engineering (yet not restricted to it!), such as flows and fluid - structure interaction, molecular dynamics or traffic simulation.

Prerequisites:

  • Interest in the development of parallel programs for simulations, intended to be run on supercomputers
  • Interest in numerical algorithms of practical value in computational applications
  • MPI or thread programming basic skills

Some keywords: HPC, load balancing, optimization, MPI, OpenMP

Contact persons:


Effiziente (hardware-nahe, parallele, ...) Implementierung von Matrixoperationen

Operationen auf Matrizen, wie z.B. die Matrixmultiplikation oder das Lösen von Gleichungssystemen in Matrix-Vektor-Notation, sind grundlegende Operationen, die in vielen Anwendungen gebraucht werden. Die entsprechenden Algorithmen sind zwar zunächst nicht arg kompliziert, sie auf moderner Hardware - seien es Multi-Core-Prozessoren oder hochparallele Supercomputer - so zu implementieren, dass die verfügbare Performance voll ausgenutzt wird, ist jedoch eine diffizile Angelegenheit.

Wir untersuchen dazu vor allem Ansätze, die die Matrizen rekursiv in Teilblöcke zerlegen und diese, z.B. mit Hilfe raumfüllender Kurven, geschickt im Speicher bzw. auf den unterschiedlichen Prozessoren anordnen.

Vorkenntnisse: Besuch der Vorlesung "Algorithmen des Wissenschaftlichen Rechnens" ist günstig, aber auch nicht unbedingt Voraussetzung. Eine gewisse Freude daran, vorhandene Rechner bis zum letzten Takzyklus auszureizen, ist ebenfalls ein guter Start.

Ansprechpartner: Michael Bader Weitere Information:

  • Cache-effiziente Verfahren zur Matrixmultiplikation auf Basis der Peanokurve
  • TifaMMy isn't the fastest Matrix Multiplication, yet!


Simulation von Tsunamis - Wellenausbreitung auf adaptiven Gittern

Die Ausbreitung von Ozeanwellen nach Erdbeben oder vergleichbar großen Erschütterungen (sog. Tsunamis) kann man auf einem zweidimensionalen Diskretisierungsgitter simulieren. Eine Herausforderung stellt dabei dar, dass das Gitter entlang der Wellenfronten stark adaptiv verfeinert werden muss.

Zum einen sind speichereffiziente Datenstrukturen für das Gitter erforderlich; auf diesen muss die Ausbreitung der Wellen modelliert werden und Kriterien zur Verfeierung und Vergröberung des Gitters werden benötigt.

Schließlich ist das resultierende Modell effizient zu implementieren - ggf. auf einem Parallelrechner, wenn die Gitterauflösung und damit die Genauigkeit fein genug sein soll.

Vorkenntnisse:

  • Besuch der Vorlesungen "Algorithmen des Wissenschaftlichen Rechnens" oder "Modellbildung und Simulation ist günstig, aber auch nicht unbedingt Voraussetzung.
  • Interesse an der Simulation physikalischer Vorgänge.

Ansprechpartner: Michael Bader

Weitere Information: Simulation der Ausbreitung von Tsunamis


Grid Computing Applications

Within the field of Grid Computing, multiple disciplines interplay, such as distributed systems, networking, security, software engineering, scientific computing etc. The projects span over a wide range of informatics assignments, comprising the development of grid services, of middleware components for Grid, the implementation of various security mechanisms or of different applications for Grid. The students have the chance to work on challenging topics, that offer an applied perspective to the theoretical concepts learned throughout their study.

Prerequisites:

  • Interest in the design and development of distributed simulation programs, intended to be run on supercomputers
  • Basic programming skills

Some keywords: C/C++, Java, Python, Globus Toolkit 4, LRZ, GridSFEA, HPC

Contact person: Ioan Lucian Muntean

Further information: Topics in Grid Computing Applications


Dünngitterverfahren zur effizienten Bearbeitung hochdimensionaler Daten

Mehrdimensionale Datensätze erzeugen gewaltige Datenmengen - schon bei zwei oder drei Dimensionen, wie etwa bei räumlich aufgelösten Simulationen, aber erst recht, wenn etwa bei Problemen des Data Minings oder der Finanzmathematik einige dutzend oder auch hundert Dimensionen auftreten.

Dünngitterverfahren, deren Aufwand wesentlich moderater mit Zahl der Dimensionen steigt als bei klassischen Diskretisierungen, bieten hier ein großes Einsparpotential und treiben so die Grenze der handhabbaren Probleme signifikant voran.

Dünngitterverfahren werden in den verschiedensten Anwendungsgebieten, die mit mehreren Dimensionen arbeiten, benötigt: Nicht nur in Ingenieur- und physikalischen Anwendungen muss optimiert, approximiert und integriert werden, auch in KI-Anwendungen wie der Klassifikation müssen beispielsweise zugrunde liegende Zusammenhänge rekonstruiert und angenähert werden. In finanzmathematischen Aufgabenstellungen muss integriert werden, bei Simulationsaufgaben müssen Kennfelder effizient abgelegt werden, ... - die Einsatzmöglichkeiten sind vielfältig.

StudentProjects sparseGrids.jpg

Aufgaben für studentische Arbeiten ergeben sich einerseits durch den Einsatz dieser Techniken in neuen Anwendungsfeldern - andererseits ist die Methodik dieser relativ neuen Technik noch alles andere als abschließend geklärt: Neben Fragen der richtigen Auswahl von Gitterpunkten und Ansatzfunktionen gibt es auch beliebig viel zu tun, um die teilweise verzwickt-rekursiven Algorithmen, die sich aus diesen Datenstrukturen ergeben, besser in den Griff zu bekommen.

Vorkenntnisse: Eine gewisse Freude an numerischen Fragestellungen sollte man hier mitbringen; optimal, aber nicht notwendig, wären Kenntnisse aus der Vorlesung Algorithmen des Wissenschaftlichen Rechnens.

Kontakt: Dirk Pflüger, Stefan Zimmer


Präkonditionierung linearer Gleichungssysteme

Zu einem linearen Gleichungssystem Ax=b mit n x n - Matrix A sucht man einen Präkonditionierer M mit der Eigenschaft, dass sich das äquivalente Gleichungssystem

MAx=Mb

besser iterativ lösen lässt, insbesondere soll die neue Matrix MA eine kleinere Kondition haben.

Schwerpunkt sind Präkonditionerer, die z.B. aus einer Normminimierung entstehen, z.B.

min || AM - I ||

für eine vorgegebene Dünnheitsstruktur von A und M. Dazu sind viele kleine Least-Squares-Probleme Cache-effizient zu lösen. Weiterhin können Präkonditionierer betrachtet werden, die - ähnlich wie ILU oder MILU (unvollständige LU-Zerlegungen) - aus einer unvollständigen Lösung von Dreiecksgleichungssystemen entstehen.

Zu bearbeiten sind hier die Definition und die mathematischen Eigenschaften von M, eine effiziente (parallele) Implementierung, und Anwendungen im Bereich Regularisierung und Glättung z.B. in der Bildverarbeitung oder bei der Lösung von PDE's.

File:StudentProjects orsirr.gif

Vorkenntnisse: Numerisches Programmieren oder Numerik, Lineare Algebra, ev. MPI

Kontakt: Univ.-Prof. Dr. Thomas Huckle


Numerische Probleme im Rahmen des Quantencomputing

Zur Implementierung effizienter Quantenalgorithmen müssen Quantenzustandsübergänge kontrolliert werden. Dazu benötigt wird die numerische Berechnung von Matrizen exp(i*H), wobei H eine dünnbesetzte, strukturierte Matrix (Hamiltonian) ist. Die Berechnung der Exponentialfunktion einer Matrix ist ein notorisch schlecht konditioniertes Problem. Hier sollen verschiedene Berechnungsmöglichkeiten hergeleitet, implementiert und verglichen werden.

Weiterhin werden von den Matrizen Aj=expm(i*Hj) alle Produkte A1 * ... * Am , m=1,2,...,n, benötigt. Diese Matrixprodukte müssen effizient und parallel berechnet werden. Dazu läuft z.Z. ein Projekt mit Implementierungen auf einem Infiniband-Cluster und auf dem HLRB II. Der Übergang zu Größeren Problemen erfordert hier auch einen Wechsel in der Parallelisierungsstrategie, da bei größeren Matrizen auch das Matrixprodukt selbst zu parallelisieren ist.

Vorkenntnisse: Numerisches Programmieren oder Numerik, Lineare Algebra, Analysis, ev. MPI

Kontakt: Univ.-Prof. Dr. Thomas Huckle


Untersuchung von Multigridverfahren

Multigridverfahren zur Lösung eines linearen Gleichungssystems verwenden zwei Techniken zur iterativen Lösung: Ein Iterationsverfahren (Glaettung) reduziert den hochfrequenten Fehler; dadurch kann das Problem auf ein gröberes lineares Gleichungssystem A2 reduziert werden, das mit weniger Aufwand gelöst werden kann. Das gegebene physikalische Problem wird dabei durch die Projektion von einem feinen Gitter (feinen Diskretisierung) auf ein grobes Gitter abgebildet:

A2 := PT A P

Zur Analyse solcher Verfahren kann die gegebene Matrix durch eine Funktion (Symbol) dargestellt werden. So wird z.B. die Matrix tridiag(-1,2,-1) dargestellt durch die Funktion

f(x) = -1*exp(ix) + 2 – 1*exp(-ix) = 2 – 2 cos(x) .

Durch diese Technik kann die gesamte Analyse eines Multigridverfahrens auf die Untersuchung kleiner Matrixfunktionen reduziert werden. Ziel dieser Untersuchungen ist es, eine Kombination von Glättungs- und Projektionsoperatoren zu bestimmen, die orthogonal zueinander sind, d.h. ein Glättungsschritt und eine Grobgitterlösung liefern bereits die gesuchte Lösung. Man spricht hierbei davon, dass in diesem Fall das Multigridverfahren, sogar ein direkter Löser ist.

Weiterhin können algebraische Multigridverfahren untersucht werden, die dadurch entstehen, dass einige benachbarte Punkte der gegebenen Diskretisierung zu einem neuen Grobpunkt verschmolzen werden. Man spricht hier von Aggregation Multigrid. Auch bei diesem Ansatz sollen durch Übergang zu der Funktionsdarstellung optimale Multigridverfahren bestimmt werden,.

Auch mittels matrix-abhängiger Projektionen lassen sich Black-Box-Mulrigridverfahren definieren. Hierbei wird durch Betrachtung der Matrix, bzw. der PDE, automatisch eine passende effiziente Projektionsmatrix generiert.

StudentProjects multigrid.jpg

Vorkenntnisse: Numerisches Programmieren oder Numerik, Lineare Algebra

Kontakt: Univ.-Prof. Dr. Thomas Huckle


Untersuchung und Implementierung von Programmen zur Lösung von SUDOKU

Es sollen möglichst alle Lösungstechniken für SUDOKUs implementiert werden. Darauf aufbauend soll ein graphisches Interface zum Lösen von SUDOKUs erstellt werden, versehen mit Hilfsfunktionen, die die vorher implementierten Lösungstechniken benutzen.

Außerdem soll ein SUDOKU-Generator entwickelt werden, der - aufbauend auf einem Löser - auch auf eindeutige Lösbarkeit hin untersucht. Hierbei sind ein

  • Bottom-up-Ansatz (beginne mit leerem SUDOKU und fülle so lange auf, bis eindeutige Lösbarkeit erreicht ist) oder ein
  • Top-down-Ansatz (beginne mit vollbesetztem SUDOKU und lösche der Reihe nach Einträge, z.B. durch Rückwärtsanwendung der Lösungstechniken) denkbar.

Mittels der verschiedenen Lösungstechniken kann eine SUDOKU-Analysierer entwickelt werden zur Bestimmung des Schwierigkeitsgrades eines SUDOKU-Problems, abhängig von Art und Anwendung der verschiednen Lösungstechniken.

StudentProjects sudoku.jpg

Vorkenntnisse: Kenntnisse in C++ oder Java, GUI

Kontakt: Univ.-Prof. Dr. Thomas Huckle


Molecular Dynamics Simulation

Molecular Dynamics Simulation deals with the simulation of materials (or mixtures of materials) on a molecular level. Even for a small simulation domains the number of particles in that domain (millions of particles) and therefore the computational effort is immense. What makes it even worse is that the molecules are often not evenly distributed in the simulation domain. Therefore, efficient algorithms and parallelisation strategies are necessary to deal with this computational challenge. The focus of student work in this field is mainly on data structures and parallelisation but can also be in any other field related to molecular dynamics.

Examples for challenges in this field are:

  • Load-balanced parallelization using space-filling curves and KD-trees
  • Adaptive data structures for finding neighbour particles
  • Improved time stepping schemes

Prerequisites:

  • Basic programming skills (in the best case C++)

Contact:

Verkehrssimulation

Verkehr spielt heutzutage eine immer größere und wichtigere Rolle. So ist Mobilität ein integraler Bestandteil unseres täglichen Lebens geworden. Zudem müssen Tag für Tag große Mengen an Waren um den ganzen Globus transportiert werden. Damit geht ein wachsendes Verkehrsaufkommen einher. Die Folgen kann jeder in Form von Staus, Umwelt- und Lärmbelastungen erleben.

Verkehrssimulationen sind ein geeignetes Mittel kostengünstig Engpässe und Probleme zu identifizieren und Lösungsstrategien zu entwickeln. Simulationen können dabei auf mikroskopischer Ebene, bei der die einzelnen Verkehrsteilnehmer und deren individuelles Verhalten betrachtet werden, oder auf makroskopischer Ebene durchgeführt werden. Hierbei werden lediglich Flüsse und Durchschnittswerte untersucht.

Studentische Arbeiten können sich dabei u.a. aus den folgenden Gebieten ableiten:

  • Mikroskopische Simulationen mittels zellulärer Automaten
  • Makroskopische Simulationen
  • Parallelisierungsstrategien für verschiedene Simulationsmodelle
  • Graphpartitionierungen und Hierarchisierungen für Verkehrsnetze

Vorkenntnisse:Kenntnisse in C++; ggf. Kenntnisse in MPI

Kontakt: Michael Moltenbrey


CFD-Simulation auf GPUs

Die Rechenleistung moderner Grafikhardware wird mittlerweile häufiger zur Durchführung von (sehr rechenintensiven) Strömungssimulationen verwendet. In einer Diplom- oder Masterarbeit, die in Zusammenhang mit der Firma EADS durchgeführt wird, soll die Eignung dieser Implementierungen für realistische Anwendungen aus dem Bereich Aerodynamik und Klimatisierung untersucht werden.

Vorkenntnisse: Kenntnisse in C++; wünschenswert auch Vorkenntnisse im Bereich numerischer Strömungssimulation (z.B. aus dem Praktikum wissenschaftliches Rechnen) und/oder Graphikprozessoren

Kontakt: Benjamin Becker (EADS), Stefan Zimmer


Hierarchical Netlists - Implementation of the Abstract, Parasitic Network Enabling View

At Qimonda AG, the department of Advanced Technology Software (PD CS ATS) develops different verification tools to support Chip Design Process. The designs worked on are strongly hierarchical which implies potentially very effective algorithms, but as well, high complexity of the data structures worked on.

In this context the problem of creating modular transactions (tools) on the hierarchical, object oriented data structures arises. This is challenging because different transactions include sometimes very similar operations on the hierarchical data and they only differ in some final steps. Thorough and fast verification and simulation of the chip schematic is needed in order to achieve "first time right" designs which are able to reach the market with the maximum yield in minimum time frame.

Verification can improve (speed up) simulation, as well. Therefore, special tools to model, optimize and analyse interconnect parasitics (important for timing analysis/simulation) are being developed by the department. The interconnection parasitics are abstracted as so called parasitic networks.

A diploma/master thesis will comprise of designing and implementing the view on the hierarchical data (electronic circuit described in the design), which detects and abstracts parasitic networks in the source circuit. Implementation language is C++.

The work includes managing of advanced object-oriented concepts.

Requirements, target group (study program): Informatics (Information systems, Business Informatics), CSE, Mathematics

Special requirements, special skills expected/preferred:

  • Interest in advanced object oriented architectures
  • Good C++ skills. Object oriented concepts, STL library
  • Solving difficult algorithmic problems
  • Recursion and hierarchy
  • Interest in Chip Design/Electronic Design Automation (EDA)

Kontakt: Marko Milosevic (Qimonda), Stefan Zimmer