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.