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.

Das Parallel Disk Model, hier mit $D=P=1$.

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

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 (BELEG + Werte).

Siehe auch

• Speicherhierarchie
• Cache-Oblivious Algorithmus