Geometrische Algorithmen mit beschränktem Arbeitsspeicher

• Antragsteller: Professor Dr. Wolfgang Mulzer
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2013 bis 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 242753045

Beim Algorithmenentwurf und Hardwaredesign lassen sich zwei gegenläufige Tendenzen beobachten: Zum einen werden die verfügbaren Ressourcen immer umfangreicher. Dies führt zu großer Software, die weder Ressourcenverbrauch noch Effizienz weiter berücksichtigt. Zum anderen gibt es immer mehr spezialisierte kleine Geräte, welche nur über beschränkten Speicher und Akkukapazität verfügen. In dieser Umgebung ist Software, welche den Speicherbedarf ignoriert, nicht geeignet. Selbst wenn ein Gerät über einen einigermaßen großen Speicher verfügt, ist es oft vorteilhaft, so wenig wie möglich in den Arbeitsspeicher zu schreiben.Sensornetze sind ein gutes Beispiel: Flashspeicher wird immer billiger, so dass eine große Anzahl von kostengünstigen Sensoren mit großen Flashdrives ausgestattet werden kann. Die Sensoren erzeugen riesige Datenmengen, die auf diesen Flashdrives gespeichert und verarbeitet werden. Dabei ist Schreiben eine teure Operation, die lange dauert und ggf. die Lebensdauer des Speichers verringert. Deswegen sollte die Anzahl der Schreiboperationen möglichst gering ausfallen. Des Weiteren kann bei mobilen Datenträgern der Schreibzugriff aus Sicherhaitsaspekten oder aus technischen Gründen eingeschränkt sein. Daher möchten wir die Daten möglichst im Speicher auf höherer Ebene verarbeiten (z.B. in CPU-Registern) und Schreibzugriffe auf das Flashdrive vermeiden. Diese Situation veranlasst uns, Algorithmen zu betrachten, welche nur wenig Arbeitsspeicher benötigen. Die Eingabe lässt sich nur lesen, aber nicht schreiben. Im bisherigen Verlauf des Projekts haben wir geometrische Algorithmen für dieses Setting entworfen und analysiert. Unser Modell ähnelt der üblichen Registermaschine insofern, als es wahlfreien Zugriff auf den Speicher erlaubt und in jeder Speicherzelle ein Datenwort vorhält. Im Gegensatz zur Registermaschine unterscheiden wir aber zwei Arten von Speicherzellen: (i) Zellen, in denen die Eingabe gespeichert ist und die sich nur lesen lassen, und (ii) Zellen des Arbeitsspeichers, die wir lesen und schreiben können. Die Ausgabe kann auf zwei verschiedene Arten behandelt werden. Entweder (a) stellt der Algorithmus eine Schnittstelle bereit, durch die sich die Komponenten der Ausgabe traversieren lassen oder (b) der Algorithmus schreibt die Ausgabe sequentiell auf ein spezielles Ausgabeband. Wir bewerten unsere Algorithmen gemäß der Anzahl an Arbeitsspeicherzellen, die sie benötigen. Insbesondere interessieren uns Algorithmen, bei denen diese Anzahl konstant ist. Im bisherigen Verlauf des Projekts haben wir mehrere interessante Probleme identifiziert, für welche solche Algorithmen möglich sind. Wir haben time-space trade-offs entwickelt, und unsere Methoden in praktischen Implementierungen getestet. In der Fortsetzung beabsichtigen wir die noch offenen und neu entstandenen Fragen weiter zu verfolgen. Insbesondere soll es um sinnvolle untere Schranken in unserem Modell gehen.

• DFG-Verfahren: Sachbeihilfen