Fakultät für Informatik der Technischen Universität München Lehrstuhl für Effiziente Algorithmen Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Seminar: Dynamische Lastbalancierung

Im Sommersemester 1996 findet ein Hauptseminar über dynamische Lastbalancierung statt. Die Vorbesprechung mit Anmeldung dafür wird am

Mittwoch, den 21.2.1996, um 13:15 Uhr im Raum S2225

Die enorme Rechenleistung und zunehmende Verfügbarkeit paralleler und verteilter Systeme hat große Forschungsanstrengungen ausgelöst, um diese Systeme so effizient wie möglich zu nutzen. Zahlreiche Problemstellungen erzeugen in nicht vorhersagbarer Weise Systemlasten. Dies führt in der Regel zu einer sehr ungleichmäßigen Ausnutzung der vorhandenen Resourcen. In einem Parallelrechner könnten beispielsweise einige Prozessoren völlig arbeitslos sein, während andere vollkommen überlastet sind.

Lastbalancierung ist der (heuristische) Versuch die Systemlast möglichst gleichmäßig auf die zur Verfügung stehenden Resourcen zu verteilen. Auf den ersten Blick sollte dies die Gesamtleistung des Systems deutlich verbessern. Jedoch darf der Aufwand für die Sammlung von Lastinformation und die Umverteilung der Last nicht vernachlässigt werden.

In diesem Seminar werden wir einige klassische und neuere Methoden zur Lastbalancierung in verschieden System-Modellen untersuchen. Neben der Präsentation der Algorithmen wird deren Analyse einen breiten Raum einnehmen. Danach sollen neuere Beiträge aus dem Bereich des on-line Scheduling dargestellt werden, die ebenfalls eine gute Resourcenausnutzung garantieren.

Abschließend werden wir uns mit dem Problem beschäftigen, Datenpakete effizient durch Netzwerke zu leiten. Dieses Problem ist einerseits untrennbar mit der Lastverteilung in parallelen und verteilten Systemen verbunden, da die Verschiebung von Last (etwa Prozessmigration) geschickt organisiert werden muß. Andererseits stellt sich beim Routing von Daten in einem Netzwerk wiederum das Problem die Last (zu verschickende Daten) gleichmäßig auf die Resourcen (Kommunikationskanäle) aufzuteilen.

Last but not least sollen die Bewertungsmaßstäbe, die der Entscheidungsfindung der Lastverteilung zugrunde liegen, in einem genau spezifizierten mathematischen Modell untersucht werden.

Die Themenliste mit Literaturangaben als PostScript-Datei.

Es werden die folgenden Themen behandelt:

1. Lastverschiebung in Richtung unterlasteter Prozessoren
2. Lastausgleich bei wohlstrukturierten Anwendungen
3. Zufällig gewählte Matchings als Partner der Lastbalancierung
4. Intelligente Taskplazierung
5. Diffusion und Dimensions-Austausch zur Lastbalancierung
6. Gewinnung von on-line aus off-line Algorithmen
7. On-line Scheduling paralleler Jobs auf verschiedenen Architekturen
8. On-line Scheduling voneinander abhängiger Jobs
9. Globale Lastbalancierung bei Service-Einschränkungen
10. Schnelles Routing von Datenpaketen
11. Routing als Anwendung von Lastbalancierung
12. Neue Bewertungsmaßstäbe für Lastbalancierung

Weitere Auskünfte erteilen Thomas Erlebach oder Stefan Bischof.