Moritz Gobbert

• Even though in most cases time is a good metric to measure costs of algorithms, there are cases where theoretical worst-case time and experimental running time do not match. Since modern CPUs feature an innate memory hierarchy, the location of data is another factor to consider. When most operations of an algorithm are executed on data which is already in the CPU cache, the running time is significantly faster than algorithms where most operations have to load the data from the memory. The topic of this thesis is a new metric to measure costs of algorithms called memory distance—which can be seen as an abstraction of the just mentioned aspect. We will show that there are simple algorithms which show a discrepancy between measured running time and theoretical time but not between measured time and memory distance. Moreover we will show that in some cases it is sufficient to optimize the input of an algorithm with regard to memory distance (while treating the algorithm as a black box) to improve running times. Further we show the relation between worst-case time, memory distance and space and sketch how to define "the usual" memory distance complexity classes.
• Obwohl Zeit in den meisten Fällen eine gute Metrik darstellt um die Kosten von Algorithmen zu beschreiben, gibt es Fälle, bei denen die theoretische Worst-Case-Laufzeit und die experimentelle Laufzeit nicht übereinstimmen. Da moderne Prozessoren eine inhärente Speicherhierarchie aufweisen, ist der Ort, an dem die Daten gespeichert sind, ein weiterer Faktor, den es zu beachten gilt. Wenn die meisten Operationen eines Algorithmus auf Daten arbeiten, welche schon im Prozessor-Cache liegen, ist die Laufzeit deutlich schneller als die von Algorithmen, bei denen die meisten Operationen die Daten erst aus dem Speicher laden müssen. Der Inhalt dieser Dissertation ist eine neue Metrik – genannt Speicherdistanz („memory distance“) – welche die Kosten von Algorithmen misst und als Abstraktion des eben genannten Aspektes gesehen werden kann. Wir werden sehen, dass es einfache Algorithmen gibt, bei denen die gemessene Laufzeit von der theoretisch bestimmten Laufzeit abweicht, aber die gemessene Laufzeit mit der theoretisch bestimmten Speicherdistanz übereinstimmt. Außerdem werden wir sehen, dass es in einigen Fällen ausreicht, die Eingabe eines Algorithmus bezüglich der Speicherdistanz zu optimieren (während der Algorithmus als Black Box betrachtet wird) um die Laufzeiten zu verbessern. Weiter werden wir uns die Beziehungen zwischen Worst-Case-Laufzeit, Speicherdistanz und Worst-Case-Platz ansehen und skizzieren, wie die „typischen“ Speicherdistanz-Komplexitätsklassen definiert werden könnten.