LOG
IN: 19 (19999) Heft 2
Aktuelles Lexikon
Online-Algorithmen
Was ist es wert, die Zukunft zu kennen?
Einführung
Die klassische Entwicklung und Analyse von Algorithmen geht davon aus,
daß die zur Lösung eines Problems benötigten Daten zu Beginn der Berechnungen
vollständig vorliegen. In vielen Anwendungen ist diese Annahme jedoch unrealistisch.
Algorithmische Probleme, die in der Praxis auftreten, sind oftmals online, d.h. relevante
Daten treffen erst nach und nach im Laufe der Zeit ein. Ein Online-Algorithmus muß
Ausgaben berechnen, ohne zukünftige Eingaben zu kennen. Online-Probleme treten in vielen
Bereichen der Informatik auf, beispielsweise in der Ressourcenverwaltung auf
Betriebssystemebene, in verteilten Systemen, in der Robotik oder im Bereich
Datenstrukturen. Drei konkrete Probleme seien hier erwähnt, auf die wir in diesem Artikel
noch genauer eingehen werden.
Paging: Gegeben ist ein zweistufiges Speichersystem bestehend aus einem kleinen
Speicher mit schnellem Zugriff und einem großen Speicher mit langsamem Zugriff. Welche
Speicherseiten sollen in dem kleinen schnellen Speicher gehalten werden, wenn nicht
bekannt ist, auf welche Seiten in der Zukunft zugegriffen wird?
Prozessorscheduling: Eine Folge von Jobs ist auf einer Menge von Prozessoren zu
bearbeiten. Auf welchem Prozessor soll ein neu eintreffender Job eingeplant werden, wenn
nicht bekannt ist, wie zukünftige Jobs aussehen?
Roboterexploration:Ein Roboter soll eine vollständige Karte einer unbekannten
Umgebung mit möglichst geringer Wegstrecke erstellen. Wie soll der Roboter sich bewegen,
wenn er die Umgebung erst beim Durchqueren kennenlernt?
Bei der Bewertung der Qualität eines Online-Algorithmus hat sich eine
mathematische Analysetechnik entwickelt, die man kompetitive Analyse nennt. In einer
kompetitiven Analyse wird ein Online-Algorithmus mit einem optimalen Offline-Algorithmus
verglichen. Ein optimaler Offline-Algorithmus kennt alle Eingabedaten im voraus und kann
eine optimale Lösung berechnen. Ein Online-Algorithmus A heißt c-kompetitiv, wenn für
alle möglichen Eingaben die von A berechnete Lösung nicht schlechter als das c-fache
einer optimalen offline berechneten Lösung ist.
Online-Algorithmen bilden seit gut zehn Jahren ein sehr aktives Forschungsgebiet innerhalb
der theoretischen Informatik. Wir bearbeiten seit Anfang der neunziger Jahre zahlreiche
Fragestellungen in diesem Bereich und stellen hier einige Ergebnisse vor.
Paging
Wir formulieren das Problem zunächst etwas präziser. In dem
zweistufigen Speichersystem haben alle Speicherseiten dieselbe Größe. Das System muß
eine Folge von Anfragen bedienen, wobei jede Anfrage eine Seite im Speichersystem
spezifiziert. Eine Anfrage kann unmittelbar bedient werden, wenn die angefragte Seite im
schnellen Speicher ist. Ist die angefragte Seite nicht im schnellen Speicher, so tritt ein
Seitenfehler auf. Die fehlende Seite muß dann vom langsamen Speicher in den schnellen
Speicher geladen werden, damit die Anfrage bedient werden kann. Gleichzeitig muß eine
Seite aus dem schnellen Speicher entfernt werden, um Platz für die neue Seite zu
schaffen. Ein Pagingalgorithmus entscheidet, welche Seite bei einem Fehler zu entfernen
ist. Diese Entscheidung muß dabei online, d.h. ohne die Kenntnis von zukünftigen
Anfragen getroffen werden. Ziel ist es, die Anzahl von Seitenfehlern, die beim Bedienen
der Anfragesequenz insgesamt erzeugt werden, zu minimieren.
Ein sehr bekannter und in der Praxis ausgezeichnet arbeitender
Online-Pagingalgorithmus ist Least-Recently-Used (LRU). Bei einem Fehler entfernt der
Algorithmus diejenige Seite aus dem schnellen Speicher, die am längsten nicht angefragt
worden ist. Sleator und Tarjan (1985) haben gezeigt, daß LRU k-kompetitiv ist, wobei k
die Anzahl der Seiten ist, die gleichzeitig im schnellen Speicher gehalten werden können.
Auf jeder Anfragesequenz ist die von LRU erzeugte Anzahl von Seitenfehlern also höchstens
k-mal so hoch wie die von einem optimalen Off- line-Algorithmus erzeugte Anzahl von
Fehlern. Dieses Ergebnis war sehr bedeutend, weil Pagingalgorithmen zuvor nur auf von
Wahrscheinlichkeitsverteilungen erzeugten Anfragesequenzen analysiert worden waren.
In einer unserer ersten Arbeiten haben wir die grundlegende Frage des
Lookaheads in Online-Pagingalgorithmen untersucht: Welchen Vorteil hat ein
Online-Algorithmus, wenn er nicht nur die aktuelle Anfrage, sondern auch einige
zukünftige Anfragen kennt? Wir konnten zeigen, daß man klassische
Online-Pagingalgorithmen wie LRU so modifizieren kann, daß sie Look- ahead ausnutzen und
den kompetitiven Faktor von k schlagen. Eine einfache Modifikation von LRU arbeitet bei
einem Seitenfehler wie folgt: Unter den Seiten, die nicht im Lookahead sind, entferne die
Seite, die am längsten nicht angefragt worden ist. Dieser Algorithmus erzielt einen
kompetitiven Faktor von k-l, wenn sich stets l paarweise verschiedene Seiten im
Lookahead-Puffer befinden. Zusätzlich haben wir den Einfluß von Lookahead nicht nur für
Paging, sondern auch für eine Reihe anderer wichtiger Online-Probleme untersucht.
Unsere aktuellen Forschungsarbeiten beschäftigen sich mit
verallgemeinerten Pagingproblemen, die in großen Netzwerken wie dem Internet auftreten.
Dort haben Speicherseiten oder Dokumente (Text- dateien, Bilder, Web-Seiten)
unterschiedliche Größen und erzeugen unterschiedliche Kosten beim Laden. Ziel ist die
Entwicklung beweisbar guter Online- und Offline-Strategien.
Prozessorscheduling
Wir betrachten eines der grundlegendsten Probleme in der
Schedulingtheorie. Gegeben sind p identische, parallel arbeitende Prozessoren. Eine Folge
von Jobs trifft ein. Jeder Job hat eine Bearbeitungszeit, die bei Ankunft bekannt ist.
Kommt ein neuer Job an, so muß er unmittelbar auf einer der Prozessoren ohne die Kenntnis
von zukünftigen Jobs eingeplant werden. Zu minimieren ist der Makespan, d.h. das
Bearbeitungsende des letzten Jobs, der fertiggestellt wird. Der folgende elegante
Schedulingalgorithmus, der List genannt wird, erzielt einen kompetitiven
Faktor von 2-1/p: Plane einen neuen Job auf dem Prozessor ein, der aktuell die geringste
Last hat. Die Last eines Prozessors ist dabei definiert als die Summe der
Bearbeitungszeiten der bereits auf dem Prozessor eingeplanten Jobs. Eine wichtige Frage
war, ob ein kompetitiver Faktor erzielt werden kann, der asymptotisch besser als 2 ist.
Vor zwei Jahren haben wir einen Algorithmus vorgestellt, der die zur
Zeit beste Leistung erzielt. Idee des Algorithmus ist es, Belegungspläne zu vermeiden, in
denen alle Prozessoren die gleiche Last haben. Haben alle Prozessoren die gleiche Last, so
kann leicht ein kompetitiver Faktor von 2-1/p entstehen. Der neue Algorithmus hält zu
jedem Zeitpunkt eine Menge M von p/2 Prozessoren mit einer geringen Last und eine Menge
Mé von p/2 Prozessoren mit einer hohen Last. Ziel ist es, einen Belegungsplan
aufrechtzuerhalten, in dem die gesamte Last auf Prozessoren in M nicht höher ist als 2/3
der gesamten Last auf Prozessoren in Mé (Bild 1, vorige Seite, zeigt ein ideales
Lastprofil).
Jeder neue Job wird entweder auf dem Prozessor mit der geringsten Last
in M oder auf dem Prozessor mit der geringsten Last in Mé eingeplant. Die Entscheidung,
welcher der beiden Prozessoren gewählt wird, hängt von dem aktuellen Lastverhältnis in
M und Mé ab. Der Algorithmus erzielt einen kompetitiven Faktor von etwa 1,9. Dies ist
nicht wesentlich besser als 2. Jedoch können wir beweisen, daß kein Online-Algorithmus
besser als 1,85-kompetitiv sein kann. Experimentelle Tests zeigen, daß der vorgestellte
Algorithmus auch in der Praxis im allgemeinen besser als List ist.
Roboterexploration
In diesem Bereich sind sehr viele geometrische und
graphentheoretische Varianten untersucht worden. In einer grundlegenden geometrischen
Variante wird die Umgebung, in der der Roboter operiert, durch einen Raum mit polygonalen
Hindernissen modelliert (s. Bild 2, linker Teil). Der Roboter hat einen Sichtbereich von
360 Grad und kann beliebig weit in die Ferne schauen, solange kein Hindernis die Sicht
blockiert. Ziel ist es, einen möglichst kurzen Pfad durch die Szene zu laufen, von dem
aus jeder Punkt des Raumes sichtbar ist.
Deng, Kameda und Papadimitriou (1998) haben einen n-kompetitiven
Algorithmus vorgestellt, der Räume mit n rechtwinkligen Hindernissen exploriert. Sie
vermuteten, daß ein Algorithmus mit einem konstanten kompetitiven Faktor existiert.
Zusammen mit einem Diplomanden haben wir diese Vermutung widerlegt. Kein
Explorationsalgorithmus kann in Räumen mit n Hindernissen einen kompetitiven Faktor
erzielen, der besser als (Wurzel aus n) ist. Diese untere Schranke gilt sogar, wenn die
Hindernisse Rechtecke sind.
In der Praxis ist die Annahme, daß der Roboter beliebig weit in die
Ferne sehen kann, nicht gerechtfertigt. Typischerweise hat ein Roboter nur einen
Sichtradius von 3-6m. Diese Einschränkung kann man dadurch modellieren, daß man ein
Gitter über die Szene legt (s. Bild 2, rechter Teil). Ein Gitterknoten zusammen mit den
adjazenten Kanten beschreibt dann den Sichtbereich des Roboters an einem Punkt der Szene.
Die Umgebung ist vollständig exploriert, wenn jeder Knoten und jede Kante des Graphen
mindestens einmal besucht bzw. überstrichen wurde. Ziel ist es, die insgesamt benötigte
Anzahl von Kantenüberstreichungen zu minimieren. Selbstverständlich erzielt eine
Graphdurchmusterungstechnik wie Tiefensuche einen konstanten kompetitiven Faktor. Wir
haben Algorithmen für Gitter mit beliebigen rechtwinkligen Hindernissen entwickelt, die
einen konstanten kompetitiven Faktor erzielen und dabei die Piecemeal-Eigenschaft
erfüllen. Diese Eigenschaft besagt, daß der Roboter in regelmäßigen Abständen, z.B.
zum Auftanken, zu einem ausgezeichneten Startknoten zurückkehren muß.
Bei der graphentheoretischen Abstraktion der Szene kann man noch einen Schritt weiter
gehen. Möchte man geometrische Eigenheiten der Umgebung vernachlässigen und sich ganz
auf die kombinatorische Komplexität des Explorationsproblems konzentrieren, so kann man
die Szene durch einen beliebigen gerichteten Graphen modellieren. Ziel ist es wieder, den
Graphen mit so wenig Kantenüberstreichungen wie möglich zu explorieren. Zusammen mit
einer Kollegin haben wir exponentielle Verbesserungen gegenüber bisher bekannten
Lösungen vorgestellt.
Schlußbemerkungen
Die hier vorgestellten Probleme bilden nur eine kleine Auswahl
von Online-Problemen, die in der Forschung untersucht werden. In den vergangenen Jahren
sind zum Beispiel verschiedene finanzielle Spiele betrachtet worden. Dort geht es unter
anderem darum, ein Portfolio zusammenzustellen, ohne zu wissen, wie sich beispielsweise
Aktienkurse entwickeln. Die vorgestellten Lösungen sind aber bisher nicht unmittelbar in
der Praxis einsetzbar. Darüber hinaus werden in der Forschung sogenannte Server- und
metrische Tasksysteme untersucht, die eine große Klasse von Online-Problemen modellieren
können.
Dr. Susanne Albers
Max-Planck-Institut für Informatik
Im Stadtwald
66123 Saarbrücken
E-Mail: albers@mpi-sb.mpg.de
Literatur
Sleator, D.D.; Tarjan, R.E.: Amortized efficiency of list update and paging rules. In:
Comm. of the ACM, 28 (1985), S. 202-208.
Deng, X.; Kameda, T.; Papadimitriou, Ch.H.: How to Learn an Unknown Environment I
The Rectilinear Case. In: Journal of the ACM, 45 (1998), S. 215-245.
|