Informatik – effizient & skalierbar

Spätestens seit den 70er Jahren bestimmen Computer unseren Umgang mit Daten im öffentlichen und privaten Raum. Aber erst mit dem Internet hat sich die elektronische Datenverarbeitung zur Datenflut ausgeweitet: Überall werden Daten erfasst, gespeichert, verarbeitet und ausgetauscht. Diese Datenflut schwillt immer weiter an: Jeden Tag werden Millionen von Digitalfotos geschossen. In Tausenden von Internet Foren und so genannten Blogs werden Berichte und Meinungen ausgetauscht.

Vielfach erschließt sich der volle Nutzen dieser großen Datenmengen nicht unmittelbar. Die Daten müssen erst sinnvoll aufbereitet werden. Dazu benötigt man effiziente Algorithmen, deren Leistung nicht beim Anwachsen der Datenflut einbricht. Solche Algorithmen und Verfahren heißen skalierbar.

Zu den Aufgaben, die Computer heute übernehmen, gehören die Vorverarbeitung, die Strukturierung, und Interpretation von Daten. Gegebenenfalls sollen aufgrund der Interpretation (zum Beispiel in der Robotik) geeignete Handlungen initiiert werden, was oft erst mit einem großen Aufwand realisierbar ist. Ein Beispiel: Die Gesichtserkennung, die aus einem Foto – also einer großen Menge unterschiedlich heller Bildpixel – den Namen der abgebildeten Person zuordnen soll. Menschen verwenden zur Interpretation derartiger Daten eine große Menge an so genanntem Weltwissen – beispielsweise Erfahrungswerte darüber, wie sich verschiedene Gesichter typischerweise voneinander unterscheiden. Eine sinnvolle Verarbeitung von Daten geht daher einher mit einer Integration von Weltwissen – von Modellen und Kategorien für verschiedene Objekte. Während die Datenverarbeitung in sehr eingeschränkten Anwendungen (zum Beispiel die visuelle Unterscheidung von 100 Testobjekten vor schwarzem Hintergrund) bereits Erfolge zeigt, bleibt die Verarbeitung komplexerer Daten bei einer großen Zahl von Kategorien ein ungelöstes Problem.

Zwei zentrale Anforderungen an die Verarbeitung von Daten sind daher Effizienz und Skalierbarkeit. Insbesondere ergeben sich folgende Herausforderungen:

Wie kann eine große Menge von Weltwissen (zum Beispiel über das Aussehen von Gesichtern) geeignet erfasst und repräsentiert werden?
Wie kann man große Mengen von Daten (zum Beispiel Bilder und Bildsequenzen) effizient verarbeiten und mit dem Weltwissen in Zusammenhang bringen?

Effizienz bedeutet in diesem Zusammenhang, dass die Rechenlaufzeiten mit der zu verarbeitenden Datenmenge und vorhandenen Kategorienzahl nicht übermäßig anwachsen. Skalierbarkeit bedeutet in diesem Zusammenhang, dass entsprechende Methoden auch dann noch zuverlässig funktionieren, wenn die Menge der zu verarbeitenden Daten wächst (zum Beispiel die Auflösung der Bilder), und wenn die Menge des repräsentierten Weltwissens größer wird. Die Informatik befasst sich seit langem mit der Suche nach effizienten und skalierbaren Algorithmen. Gerade in den letzten Jahren wurde für einige Probleme überraschende Ergebnisse erzielt. Mit der Fähigkeit, auch große Datenmengen sinnvoll zu verwenden, ergeben sich ungeahnte Möglichkeiten sowohl zur Leistungssteigerung bestehender Systeme als auch für gänzlich neuartige Anwendungen.

Forschungsbedarf: Algorithmen für große Datenmengen

Einige der größten Herausforderungen in der Algorithmik ist das so genannte Algorithmen-Engineerings, das theoretische Ergebnisse wie Laufzeitschranken oder Approximations¬garantien mit praktikablen Algorithmen verbindet. Neben der experimentellen Analyse von Algorithmen wirft Algorithmen-Engineering ständig neue theoretische Fragen auf, wie etwa beim Entwurf von so genannten Checkern. Diese Problemstellung kommt direkt aus der Praxis: Wie kann ein Algorithmus ein Zertifikat liefern, mit dessen Hilfe die Korrektheit der Ausgabe schnell zu überprüfen ist?

Des Weiteren geht es im Algorithmen-Engineering darum, für algorithmische Probleme realistische Modelle anzugeben. Einige davon werden im Folgenden vorgestellt.

Um mit den stetig wachsenden Datenbergen umgehen zu können, müssen Algorithmen mit linearer oder fast-linearer Laufzeit für grundlegende Probleme gefunden werden. Häufig ist dieses Ziel mit exakter Berechnung unvereinbar. Seit einiger Zeit versucht man daher, für Optimierungsprobleme so genannte Linearzeit-Approximationsschemata zu finden. Die Laufzeit eines solchen Schemas ist linear in der Größe der Eingabe, hängt aber noch von der gewünschten Genauigkeit der Ausgabe ab.
Eine radikalere Herangehensweise an große Datenmengen stellen so genannte Streaming-Algorithmen dar, bei denen die Eingabe nur ein einziges Mal gelesen wird und dass im Vergleich zur Größe der Eingabe nur sehr wenig Speicher zur Verfügung steht.
Noch extremer sind so genannte sublineare Algorithmen, die ein gegebenes Objekt daraufhin testen, ob es eine bestimmte Eigenschaft erfüllt oder ob es ein anderes Objekt gibt, das dem gegebenen ähnelt und die gewünschte Eigenschaft besitzt. Bei anderen sublinearen Algorithmen ist die Berechnung exakt; nur die Laufzeit ist eine Zufallsvariable.
Ein weiterer Zweig der Algorithmik befasst sich mit Datenmengen, die so groß sind, das sie nicht mehr in den Hauptspeicher des betroffenen Rechners passen. Da der Zugriff auf externe Speicher wie die Festplatte aber um viele Größenordnungen langsamer ist, wird ein anderes Maß für Effizienz als das übliche RAM-Einheitskostenmodell benötigt. Der Einfachheit halber wird dabei nur die Anzahl der (teuren) Zugriffe auf die Festplatte gezählt, nicht die Anzahl der Operationen im Hauptspeicher.

Forschungsbedarf: Skalierbare verteilte Systeme

Computer haben sich über die letzten 60 Jahre hinweg sehr verändert. Aus den raumfüllenden Großgeräten sind winzige allgegenwärtige Hilfsgeräte geworden, die vom Handy über das Auto bis hin zu ganzen Fabrikanlagen unsere Lebens- und Arbeitswelt prägen. Mit der gewaltigen Zunahme der schieren Zahl von Rechnern und Kleinstrechnern ergibt sich aber auch die Notwendigkeit, derartige hochkomplexe Systeme aus Tausenden oder Millionen von Computern zu entwerfen und zu betreiben. Längst ist nicht mehr die einzelne Rechenmaschine die Herausforderung, sondern die Frage, ob ein System auch dann noch wie erwartet fehlerfrei seine Leistung erbringt, wenn sich seine Gesamtgröße alle ein bis zwei Jahre verdoppelt.

Bislang verlief diese Entwicklung einigermaßen stabil. Engpässe in der Leistungsfähigkeit des Internets oder der Mobilfunknetze wurden durch entsprechende Investitionen überwunden. So konnte über die letzten Jahre hinweg eine sichere und kontinuierliche Entwicklung gewährleistet werden. Viele Fragen sind hier aber nach wie vor offen. So werden alle großen Systeme heute geplant und administriert. Die Mobilfunknetze wurden von einigen wenigen großen Anbietern aufgebaut. Auch das Internet wird von nur wenigen großen Providern Unternehmen und Privatleuten zugänglich gemacht. Die Euphorie um Peer-to-peer-Technologien der letzten Jahre zeigt aber, welche Kraft hinter völlig neuartigen Ansätzen stehen kann. So ist beispielsweise Skype innerhalb von nur zwei Jahren zu einem global agierenden Großunternehmen gewachsen. Ähnliche Techniken könnten vom Mobilfunk bis hin zu Web-Diensten im Internet die gesamte Informations- und Kommunikationstechnologie umwälzen. Planung und Administration würden dabei durch Selbstorganisation ergänzt oder sogar ersetzt. So könnten immense Kosteneinsparungen realisiert werden. In manchen Bereichen, beispielsweise bei den Lebenswissenschaften, kann die wachsende Datenflut vermutlich nur noch mit derartigen Techniken gebändigt werden.

Selbstorganisation ist als grundlegendes Prinzip schon seit einigen Jahren Forschungs¬gegenstand, vor allem in den Naturwissenschaften. Mittels Selbstorganisation bilden große Systeme eine inhärente Ordnung: Einzelne Wassermoleküle bilden eine Schneeflocke, Tausende von Fischen agieren als ein Schwarm, Termiten errichten riesige Bauwerke, die nicht nur allen statischen Anforderungen genügen, sondern überdies auch nach klimatechnischen Gesichtspunkten geplant erscheinen.

Dieses Prinzip gilt es nun für die Informatik nutzbar zu machen. Dies erfordert eine Umstellung vieler Analyse- und Entwicklungstechniken. So gibt es bislang im Bereich der Leistungsbewertung keine allgemein akzeptierten Simulations- und Analysewerkzeuge für sehr große verteilte Systeme. Spezifikations- und Beschreibungstechniken müssen auf selbstorganisierende Systeme erweitert werden; die klassischen prozedural-funktionalen Modelle müssen um selbstorganisierende Elemente ergänzt werden. Testwerkzeuge und Testlabors müssen auf die Untersuchung sehr großer Systeme erweitert werden.