External Memory Algorithmus

Ein External Memory Model ermöglicht das Analysieren von Algorithmen die Datenmengen verarbeiten, welche die Kapazität des Hauptspeichers des ausführenden Rechners übersteigen. Da die Zugriffszeit auf langsame Massenspeicher wie Festplatten oder Netzwerkspeicher die Zeit für Hauptspeicher- Cache- oder Registerzugriffe sowie Operationen der ALU um mehrere Größenordnungen dominiert, ist in diesem Fall für die Zeitkomplexität eines Algorithmus die Anzahl der I/O-Operationen auf diese langsamen Massenspeicher maßgeblich.

Notwendigkeit eines speziellen Modells

Klassischerweise wird die Laufzeit von Algorithmen in Berechnungsmodellen ohne Speicherhierarchie analysiert. In diesen Modellen verursacht ein Speicherzugriff konstante Kosten, genau wie die Ausführung arithmetischer Befehle. Desweiteren sind die Kosten eines Speicherzugriffs unabhängig von der Adresse auf die zugegriffen wird, sowie von vorangegangenen Zugriffen.

Diese Annahmen sind vereinfachend und entsprechen nicht der Realität. Einerseits unterscheiden sich die Zugriffszeiten zwischen zwei Ebenen der Speicherhierarchie für gewöhnlich um Größenordnungen. Andererseits führen Caches sowie die Funktionsweise von Festplatten dazu, dass der Zugriff auf mehrere aufeinander folgende Adressen üblicherweise schneller ist, als der Zugriff auf zufällige Adressen.

An der Grenze zwischen Haupt- und Massenspeicher ist dieser Effekt besonders stark (BELEG + Werte).

Das Parallel Disk Model (PDM)

Das häufig verwendete Parallel Disk Model wurde von 1994 von Vitter und Shriver eingeführt. Es modelliert die wichtigsten Eigenschaften von magnetischen Festplatten und Systemen mit mehreren parallel angebundenen Festplatten. Wir betrachten hier die Version mit nur einem Prozessor. Für Systeme mit beliebiger Anzahl Prozessoren siehe .

Definition

Das Modell besteht aus einem internen Speicher welcher $M$Datenelemente fasst sowie einem unbegrenzten externen Speicher welcher aus $D$parallelen Festplatten besteht. Jede dieser $D$Festplatten kann während einem gemeinsamen I/O-Schritt $B$ Datenelemente in den internen Speicher schreiben oder aus ihm lesen. Die Problemgröße wird mit $N$ Datenelementen beziffert. Desweiteren soll gelten $M<N$ sowie $1\leq DB\leq M/2$.