Systementwicklungsprojekt / Diplomarbeit
Entwurf eines Frameworks für Scheduling-Algorithmen
Bei Scheduling-Problemen beschäftigt man sich mit der Frage, wie Jobs in
einem System von parallelen Maschinen optimal abgearbeitet werden
können. Hierbei kann man beispielsweise sowohl an die Zuteilung von Prozessen
zu Prozessoren denken, als auch an die Einplanung von Werkstücken auf
Maschinen.
Da Scheduling-Probleme offensichtlich in vielen Bereichen innerhalb und auch
außerhalb der Informatik auftauchen, findet dieses Gebiet schon seit langem
in der Forschung Beachtung. Auch wenn im Laufe der Jahre zahlreiche Ergebnisse
erzielt werden konnten, so bleiben immer noch etliche offene Fragen, die unter
anderem auch am Lehrstuhl für Effiziente Algorithmen im Rahmen eines
Sonderforschungsbereiches untersucht wurden.
Als Hilfsmittel zum Entwurf von Scheduling-Verfahren und zur Präsentation
beispielsweise im Rahmen der Lehre wurde ein Framework zur
Implementierung, Simulation und Visualisierung von Scheduling-Algorithmen
realisiert. Innerhalb dieses Projektes besteht für Sie Gelegenheit zur
Durchführung eines Systementwicklungsprojektes oder auch einer Diplomarbeit.
Das Projekt kann grob in folgende Teilgebiete unterteilt werden:
- Simulationskern
- Visualisierung und graphischer Editor (hierbei ist
beispielsweise auch die Realisierung des automatischen Layouts von Graphen
interessant)
- Automatische Generierung von Probleminstanzen
- Realisierung von Hilfsfunktionen und Datenstrukturen, die
in Scheduling-Algorithmen benötigt werden (z. B. Berechnung des
kritischen Pfades, Umwandlung unterschiedlicher Darstellungen für
Präzedenzrelationen)
- Exemplarische Implementationen von Scheduling-Algorithmen
Eine Arbeit (DA/SEP) am Scheduling-Framework kann z.B. folgende
Themen beinhalten:
- Corba-Anbindung der Scheduling-Algorithmen
- Erweiterung des Frameworks um stochastische Scheduling-Modelle
und -Algorithmen (Generierung, Visualisierung, statistische Analyse)
- Implementierung ausgewählter Scheduling-Algorithmen. Im Rahmen einer
Diplomarbeit könnten auch eigene Verfahren und Heuristiken
entwickelt und untersucht werden.
Der Inhalt und Umfang Ihres Arbeitspaketes kann mit uns abgesprochen werden
und richtet sich nach Ihren Interessen und Vorkenntnissen, sowie nach
der Anzahl der Bearbeiter. Abgestimmte Arbeiten von mehreren Interessenten
sind nicht nur möglich, sondern auch erwünscht.
Als Implementierungssprache wurde aus Effizienzgründen und wegen der
komfortablen Bibliothek LEDA (Library for Efficient
Datatypes and Algorithms) C++ gewählt. Auf einen sauberen, auf
Wiederverwendbarkeit ausgerichteten Entwurf wird großen Wert gelegt. Zum
Design wird die objektorientierte, graphische Modellierungssprache UML verwendet. Hierbei
kommt das CASE-Tool Together/C++ zum
Einsatz, das die Modellierung und die Erstellung von Dokumentation
unterstützt. Together/C++ hat auch in der Industrie große Verbreitung und
entspricht dem aktuellen Stand der Softwaretechnik.
|
Voraussetzungen:
|
Die folgenden Kenntnisse sind für das Projekt von Nutzen, aber
selbstverständlich müssen Sie nicht auf allen diesen Gebieten
ausführliche Erfahrungen mitbringen, sofern Sie motiviert und bereit
sind, sich fehlende Kenntnisse anzueignen.
Was den Umgang mit den eigentlichen Scheduling-Algorithmen betrifft,
so können Sie sich je nach Interessenslage viel oder wenig damit
beschäftigen. Dies hängt ganz von der Gestaltung Ihres Arbeitspakets
ab.
|
Kenntnisse in C++, LEDA
|
|
|
Objektorientierter Entwurf mit UML
|
|
|
Grundlegendes Wissen über effiziente Implementierung von Algorithmen
(Vorlesung Effiziente Algorithmen, Algorithmenpraktikum)
|
|
|
Aufgabensteller:
|
Prof. Dr. Ernst W. Mayr
|
|
Betreuung:
|
Hanjo Täubig,
Thomas Schickinger
|
Thomas Schickinger,
Hanjo Täubig
Last modified: Thu May 16 16:49:25 CEST 2002
