• search hit 1 of 1
Back to Result List

Memory Distance: A Different Metric for Analyzing Algorithm Performance

Speicherdistanz: Eine Andere Metrik zum Analysieren der Performance von Algorithmen

  • 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.

Download full text files

Export metadata

Metadaten
Author:Moritz Gobbert
URN:urn:nbn:de:hbz:385-1-18817
DOI:https://doi.org/10.25353/ubtr-xxxx-6e99-667d
Advisor:Stefan Näher, Philipp Kindermann
Document Type:Doctoral Thesis
Language:English
Date of completion:2022/06/17
Publishing institution:Universität Trier
Granting institution:Universität Trier, Fachbereich 4
Date of final exam:2022/06/15
Release Date:2022/06/23
Tag:algorithm analysis; cache behavior; memory distance; time complexity
GND Keyword:Algorithmus; Analyse; Datenspeicherung; Prozessor; Pufferspeicher; Speicherdirektzugriff
Number of pages:vii, 259
First page:i
Last page:259
Institutes:Fachbereich 4 / Informatik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 000 Informatik, Informationswissenschaft, allgemeine Werke
Licence (German):License LogoCC BY: Creative-Commons-Lizenz 4.0 International

$Rev: 13581 $