Externspeichermodell

Das Externspeichermodell ist ein Modell aus der theoretischen Informatik, welches die Komplexität von Algorithmen in Bezug auf die Verwendung von mehreren Speicherhierarchien beschreibt. Das Modell wurde erstmals 1987 von Alok Aggarwal und Jeffrey S. Vitter beschrieben. Im Gegensatz zum klassischen RAM-Modell, welches die Laufzeit eines Algorithmus anhand der Anzahl von Operationen auf dem Prozessor und Zugriffen auf einen beliebig großen, schnellen Hauptspeicher beschreibt, wird beim Externspeichermodell ein abstraktes Maschinenmodell, bestehend aus zwei Speicherstufen, verwendet. Es handelt sich hierbei um einen schnellen Hauptspeicher, welcher die Größe M besitzt, und um einen externen Speicher, welcher eine für die Lösung des Problems hinreichend große Größe besitzt, wobei dieser kein Modellparameter ist, sowie eine Blockgröße B. Die Länge der Eingabe wird mit N bezeichnet, welche in N/B Blöcken auf dem Externspeicher gespeichert ist. In realistischen Szenarien ist N >> M. Um ein Element oder B Elemente innerhalb eines Blocks in den Hauptspeicher zu laden, wird ein Zugriff auf den Externspeicher benötigt. Dieser Zugriff wird auch als I/O bezeichnet.

Ziel des Modells ist es, die Anzahl von Zugriffen auf den Externspeicher (I/Os) zu minimieren, welche für die Lösung eines gegebenen Problems notwendig sind.

Lesen von konsekutiv gespeicherten Daten

Eines der grundlegenden Primitive, welches im Externspeicher zur Anwendung kommt, ist das Lesen von X auf einander folgenden Daten. Um diese Daten zu lesen, müssen ${\mathcal {O}}(X/B)$ I/Os durchgeführt werden. Wird die ganze Eingabe gelesen, so wird dies als ein scan(N) bezeichnet, welcher die I/O-Komexplität von ${\mathcal {O}}(N/B)$ I/Os besitzt.

Sortieren im Externspeicher

Im Externspeicher können unter Verwendung eines modifizierten Mergesort Algorithmus N Daten mit ${\mathcal {O}}(N/B\cdot \log _{M/B}(N/B))$ I/Os sortiert werden.