External Memory Algorithmus

Diese Baustelle befindet sich fälschlicherweise im Artikelnamensraum. Bitte verschiebe die Seite oder entferne den Baustein {{Baustelle}}.

Dieser Artikel ist im Entstehen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Solltest du über eine Suchmaschine darauf gestoßen sein, bedenke, dass der Text noch unvollständig sein und Fehler oder ungeprüfte Aussagen enthalten kann. Wenn du Fragen zum Thema hast, nimm Kontakt mit den Autoren auf.

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.

Das Parallel Disk Model, hier mit $D=P=1$. Cache hat eine Größe von $M$ Speicherworten, der Hauptspeicher ist unbegrenzt. Datentransfer zwischen beiden findet immer in Blöcken der Größe $B$ statt.

Analyse im Parallel Disk Model (PDM)

Das häufig verwendete Parallel Disk Model modelliert die wichtigsten Eigenschaften von magnetischen Festplatten und Systemen mit mehreren parallel angebundenen Festplatten. Wir betrachten hier nur batch-Probleme und Systeme mit einem Prozessor. Für online-Probleme und Systeme mit beliebiger Anzahl Prozessoren siehe Vitter (2006).

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

Oft können Formeln vereinfacht werden, wenn statt der oben verwendeten Größen in Anzahl von Datenelementen die jeweilige Größe in Anzahl von Blöcken verwendet werden:

$$n=N/B,\quad m=M/B$$

Für eine Effiziente Verarbeitung müssen die Eingabedaten des Problems striped auf den D Platten vorliegen (siehe Abb. TODO für ein Beispiel). Die Ausgabe des Algorithmus soll dem gleichen Format folgen.

Fundamentale Operationen

Die I/O-Komplexität vieler Algorithmen wird im wesentlichen bestimmt durch die performance einiger fundamentaler Operationen:

1. Scanning (auch streaming oder touching) – Lesen oder schreiben von $N$ sequentiellen Datenelementen
2. Sortieren von $N$ Datenelementen (vergleichsbasiert)

Schranken für die I/O-Komplexität dieser Operationen finden sich in folgender Tabelle:

Schranken für die I/O-Komplexität fundamentaler Operationen

Operation	I/O-Schranke, D = 1	I/O-Schranke, D ≥ 1
${\textit {Scan}}(N)$	$\Theta (N/B)=\Theta (n)$	$\Theta (N/DB)=\Theta (n/D)$
${\textit {Sort}}(N)$	$\Theta (N/B\log _{M/B}N/B)=\Theta (n\log _{m}n)$	$\Theta (N/DB\log _{M/B}N/B)=\Theta (n/D\log _{m}n)$

Beispiele

Merge Sort

Betrachten wir External Memory Merge Sort für $D=1$. Dieser Algorithmus arbeitet in zwei Phasen.

In der ersten Phase namens run formation werden jeweils $m$ der $n$ Eingabeblöcke in den internen Speicher eingelesen, dort sortiert und anschließend wieder zurück in den externen Speicher geschrieben. Als Ergebnis dieser Phase stehen die Eingabedaten nun als $n/m$ sortierte runs im hintereinander im externen Speicher.

In der zweiten Phase des Algorithmus werden die existierenden runs rekursiv verschmolzen bis nur noch ein vollständig sortierter run existiert. Dazu werden pro Rekursionsebene jeweils $m$runs gleichzeitig Blockweise durch den internen Speicher gestreamt, und dabei zu einem sortierten run verschmolzen. Pro Ebene werden alle Elemente je einmal gelesen und geschrieben, was $2n$I/Os entspricht. Nach $\Theta (\log _{m}n)$Merge-Phasen ist nur noch ein sortierter run übrig, das Ergebnis.

Insgesamt benötigt der Algorithmus also $\Theta (n\log _{m}n)$ I/Os, ist also optimal.

Motivation

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. Siehe dazu auch Speicherhierarchie.

Anwendung

Es existieren diverse Bibliotheken und Tools um External Memory Algorithmen zu implementieren. Ein umfassende Übersicht ist in Vitter (2006) ab Seite 141 zu finden.

Geschichte

Laut Vitter begann die Arbeit an External Memory Algorithmen bereits 1956 in Stanford mit H. B. Demuths Dissertation Electronic data sorting. Auch Donald E. Knuth beschäftigte sich in seiner 1973 veröffentlichte Monografie The Art of Computer Programming – Volume 3: Sorting and Searching ausgiebig mit dem Sortieren von Daten auf Magnetbändern und zum Teil auch auf Festplatten. Etwa zur selben Zeit präsentierte Robert W. Floyd in seiner Arbeit Permuting Information in Idealized Two-Level Storage ein Modell ähnlich PDM mit Parametern $D=1$, $P=1$, $B=M/2=\Theta (N^{c})$ mit $0<c<1$. 1988 erweiterten Aggarwal und Vitter in The input/output complexity of sorting and related problems Floyds Modell um die Möglichkeit von parallelen Block-Transfers. 1994 führten Vitter und Shriver das Parallel Disk Model ein, welches eine realitätsnähere Version von Aggarwal und Vitters Modell darstellt.

Siehe auch

• Speicherhierarchie
• Cache-Oblivious Algorithmus – für eine alternative Modellierung, bei der dem Algorithmus $M$ und $B$ nicht zur Verfügung stehen