AG Meyer auf der Heide:

Themen für Diplom- und Studienarbeiten

geordnet nach Forschungsgebieten:

Algorithmische Geometrie und Computergraphik
Idle-Profiling und -Statistik eines Linux-Pools
Basisdienste für Rechnernetzwerke: Datenmanagement
Energiesparende Protokolle für Sensornetzwerke

Algorithmische Geometrie und Computergraphik

In unserer Arbeitsgruppe beschäftigen wir uns mit der Entwicklung von beweisbar guten Algorithmen in der Computer Grafik, sowie mit verwandten Problemen der algorithmischen Geometrie. Einige der von uns entwickelten Algorithmen wurden bereits im Paderborner Walkthrough System "PaRSiWal" implementiert und auf ihre Praxistauglichkeit getestet. PaRSiWal ist ein echtzeitfähiges, dynamisches Walkthroughsystem, bei dem es Besucher und Modellierer gibt, die eine virtuelle Szene durchwandern und im Fall der Modellierer diese auch verändern können. Wir sind insbesondere an der Verwaltung sehr großer Szenen interessiert, die auch verteilt (z.B. im Internet) liegen dürfen. Die Probleme, die wir betrachten, umfassen unter anderem:

Suchprobleme (wie finde ich die Objekte, die in der Nähe eines Besuchers stehen und daher vermutlich sichtbar sind?)

Occlusion Culling (wie kann man Objekte, die durch andere vollständig verdeckt sind finden, damit man sie nachher nicht der Grafikhardware übergeben muß?)

Approximationen (wie kann man weit entfernte Objekte oder Objektgruppen geschickt approximieren?)

Datenpartitionierung (wenn man die Objektdaten auf viele Rechner verteilen möchte, stellt sich die Frage, wie das geschickt gemacht werden kann)

Bewegliche Objekte (wie kann man die oben genannten Probleme lösen, wenn sich einige Objekte (z.B. Autos) in der Szene bewegen?)

Datenkompression (wie kann man Objekte, die z.B. als Dreiecksnetze im Rechner dargestellt werden, geschickt komprimieren, um die Netzlast gering zu halten?).

Themen für Diplom- und Studienarbeiten:

Management beweglicher Objekte für virtuelle Szenen
In virtuellen Szenen bewegen sich Besucher, die anderen Besuchern in Form eines Avatars dargestellt werden. In großen Szenen mit sehr vielen Besuchern (Spiele) müssen deshalb die Positionen der Besucher verwaltet und aktuell gehalten werden, damit jeder Besucher nur die Besucher seiner näheren Umgebung sieht und verwalten muß. Die Verwaltung kann mit Hilfe sogenannter PMO (Potentiell Moving Objects) erfolgen. Diese PMOs sollen mit einem dynamischen Quadtree implementiert werden. Es soll ein Besucher implementiert werden, der sich mit Hilfe der PMO durch eine Szene Szene bewegt. Die Besucher der Szene und die PMOs sollen in Java implementiert und durch eine 2D-Grafik visualisiert werden. Auf Wunsch kann die Visualisierung auch in Java 3D erfolgen, ist aber nicht notwendig.
Arbeitsschritte:
- Implementierung der PMO's mit Hilfe dynamischer Quadtrees
- 2D-Visualisierung der PMO's in Java
- Navigation eines Besuchers mit Hilfe der PMO's

Idle-Profiling und -Statistik eines Linux-Pools

Projekte wie seti@home zerlegen ein sehr großes Problem in unabhängige kleine Teile und lassen diese von gängigen PCs während deren Idle-Zeiten abarbeiten. Die PUB-Library unterstützt darüber hinaus Prozesskommunikation und -Migration in Linux-Pools. Wenn also ein Rechner plötzlich keine freie CPU-Zeit mehr aufweist, weil z.B. ein Student sich eingeloggt hat und zu arbeiten beginnt, kann der Scheduler den bislang dort laufenden Job auf eine andere Maschine umziehen.
Weil solch ein Umzug aber ebenfalls aufwändig ist, lohnt sich dies nur, wenn der alte Computer auf absehbare Zeit blockiert und der neue lange frei bleibt. Ob dies der Fall sein wird, kann im Voraus natürlich niemand wissen; aber basierend auf einer genauen Statistik kann der Scheduler seine Entscheidung zumindest auf eine gute Prognose basieren.
Eine solche Statikstik über die CPU- und Speicherauslastung (wie mißt man diese aussagefähig?) in einem typischen Linux-Pool soll hier erstellt werden, aufgeschlüsselt nach Wochentag und Uhrzeit. Ausserdem sind Korrelationen/Abhängigkeiten von Bedeutung, also z.B. die Frage: Wenn die Auslastung steigt, wie lange bleibt sie dann typischerweise hoch? Woran kann man kurze Lastspitzen (cron-Job, Einloggen bloss zum Email-Lesen) von echten Rechnungen unterscheiden?
Ziel soll ein Tool sein, das dem Scheduler für jeden Job konkret eine Migration entweder empfiehlt oder davon abrät.

Basisdienste für Rechnernetzwerke: Datenmanagement

In diesem Bereich beschäftigen wir uns mit der Entwicklung von Datenmanagementstrategien in Rechnernetzwerken. Diese Strategien ermöglichen die effiziente, interaktive Nutzung von Datenobjekten, auf die von allen Rechnern im Netzwerk lesend und schreibend zugegriffen werden kann. Beispiele für diese Datenobjekte sind globale Variablen in einem parallelen Programm, Dateien in einem verteilten Dateisystem oder Seiten im World Wide Web.

Traditionelles Datenmanagement setzt üblicherweise auf eines der beiden Konzepte Hashing oder Caching. Caching steht dabei für die Ausnutzung von temporaler und topologischer Lokalität. Durch das Anlegen von Datenkopien auf dem anfragenden Rechner oder auf einem Netzwerk-Knoten in der Nähe dieses Rechners, können nachfolgende Zugriffe auf dieselben Daten lokal beantwortet werden. Während Caching darauf abzielt, die Kommunikationslast durch Ausnutzung von Lokalität zu verringern, versucht Hashing die Kommunikationslast gleichmä�ig über die Netzwerk-Ressourcen zu verteilen, um Engpässe und somit Datenstaus zu verhindern. Dies geschieht durch eine randomisierte Verteilung der Daten im Netzwerk, die jedoch üblicherweise die Lokalitäten zerstört und somit das Caching aushebelt.

Wir haben eine Datenmanagementstrategie entwickelt und analysiert, die sogenannte "Access-Tree Strategie", die diese scheinbar gegensätzlichen Konzepte miteinander verknüpft. Dazu reduzieren wir das komplexe Kommunikationsnetzwerk auf eine einfachere Struktur, den sogenannten "Access-Tree". Diese logische Struktur repräsentiert das Kommunikationspotential des gesamten Netzwerkes, abstrahiert jedoch von einzelnen Verbindungen. Insbesondere sind die Kommunikationswege in dieser Struktur eindeutig bestimmt, so daß die folgenden Problemstellungen effizient durch einen verteilten Caching-Algorithmus gelöst werden können:

Wo sollen Kopien eines Datenobjektes abgelegt werden?
Welcher Rechner greift beim Lesen oder Schreiben auf welche Kopie zu?
Wie können die einzelnen Kopien eines Datenobjektes lokalisiert werden?

Die logischen Access-Trees werden nun wiederum mittels Hashings auf das eigentliche Netzwerk abgebildet. Dabei werden randomisierte aber lokalitätserhaltende Hash-Funktionen verwendet. Durch dieses Konzept wird es möglich, die Effekte von Hashing und Caching simultan zu nutzen, d.h., einerseits die Kommunikationslast extrem zu verringern, und anderseits die verbleibende Last gleichmäßig zu verteilen, um Datenstaus zu vermeiden.

Varianten der Access-Tree Strategie sind in der DIVA (Distributed Variables) Bibliothek implementiert worden. Diese Bibliothek stellt Funktionen für den effizienten Zugriff auf globale Variablen in einem parallelen Programm bereit.

Themen für Diplom- und Studienarbeiten

Adaption der Access-Tree Strategie für Workstationcluster unter Linux. Prototypische Implementierung und experimentelle Evaluation der entwickelten Strategien.
Entwicklung und Analyse von Datenmanagementstrategien für SCI-Workstationcluster, unter besonderer Berücksichtigung der Hardwarecharakteristika von SCI, wie z.B. der Shared-Memory Unterstützung. Prototypische Implementierung und experimentelle Evaluation der entwickelten Strategien.

Energiesparende Protokolle für Sensornetzwerke

Sensornetzwerke bestehen aus einer gro�en Anzahl von Knoten, die mit (Umwelt-) Sensoren best�ckt sind. Diese messen Daten und melden Sie einer zentralen Basisstation weiter. Diese Sensorknoten beziehen ihre Stromversorgung aus Batterien und m�ssen damit sehr gut haushalten. Hierzu m�ssen sie einen Gro�teil der Zeit im Schlafmodus verbringen, indem sie weder rechnen noch Daten versenden oder empfangen k�nnen. Daneben m�ssen sie ihre Sendest�rke auf ein Mindestma� reduzieren. Damit ist eine direkte Verbindung mit der Basisstation in der Regel nicht m�glich und jede Nachricht muss �ber verschiedene anderen Sensorknoten als Zwischenstationen verschickt werden, welche jedoch die meiste Zeit schlafen...

In Zusammarbeit mit der Arbeitsgruppe Sensorik von Prof. Hilleringmann (Elektrotechnik) wird in dieser Diplomarbeit ein einfaches, verteiltes, probabilistisches Kommunikationsprotokoll in der Simulationsumgebung SAHNE auf seine Einsetzbarkeit �berpr�ft und optimiert. Die Ergebnisse dieser Untersuchungen werden dabei im Rahmen einer kooperierenden Diplomarbeit in der Elektrotechnik direkt in die Entwicklung eines reellen Sensornetzwerks eingesetzt.

Mehr Details erh�ltlich bei Christian Schindelhauer.