External Memory Algorithmus

Das Modell besteht aus einem internen Speicher welcher ${\displaystyle M}$ Datenelemente fasst, sowie einem unbegrenzten externen Speicher welcher aus ${\displaystyle D}$ Festplatten besteht. Der wesentliche Performance-Indikator ist die I/O-Komplexität: die Anzahl von Zugriffen auf den externen Speicher zur Lösung eines Problems mit ${\displaystyle N}$ Datenelementen. Bei jedem Zugriff auf den externen Speicher kann von jeder der ${\displaystyle D}$ Festplatten ein Block von ${\displaystyle B}$ Datenelementen in den internen Speicher geladen werden. Analog kann vom internen in den externen Speicher geschrieben werden. Des Weiteren soll gelten ${\displaystyle M<N}$ sowie ${\displaystyle 1\leq DB\leq M/2}$.[1]

Zwei Dateien A und B der Größe ${\displaystyle 4B}$ welche im striping Verfahren auf die Festplatten D1 bis D3 verteilt sind.

Bei ${\displaystyle D>1}$ Festplatten müssen für eine effiziente Verarbeitung die Eingabedaten des Problems im striped Format auf den ${\displaystyle D}$ Platten verteilt vorliegen (siehe die nebenstehende Abbildung für ein Beispiel). Die Ausgabe des Algorithmus soll dem gleichen Format folgen. Hierdurch können ${\displaystyle N}$ Datenelemente mit der optimalen Anzahl von ${\displaystyle \Theta (N/DB)}$ I/Os in den externen Speicher geschrieben oder von ihm gelesen werden.[1]

Oft können die Formeln der resultierenden Anzahl von I/Os vereinfacht werden, wenn statt der oben verwendeten Größen in Anzahl von Datenelementen die jeweilige Größe in Anzahl von Blöcken verwendet werden. Hieraus ergeben sich die abgeleiteten Größen ${\displaystyle n=N/B}$ sowie ${\displaystyle m=M/B}$.[1]

Die I/O-Komplexität vieler Algorithmen wird im Wesentlichen bestimmt durch die Performance einiger fundamentaler Operationen[1]:

1. Scanning (auch streaming oder touching) – Lesen oder schreiben von ${\displaystyle N}$ sequentiellen Datenelementen
2. Sortieren von ${\displaystyle 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[1]

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

Als ein einfaches Beispiel für einen I/O-optimalen External Memory Sortieralgorithmus soll External Memory Merge Sort mit ${\displaystyle D=1}$ dienen. Dieser Algorithmus arbeitet in zwei Phasen.[1]

Die erste Phase namens run formation erhält als Eingabe eine unsortierte Folge von Elementen im externen Speicher und erzeugt als Ausgabe ebendort eine Permutation dieser Folge, partitioniert in ${\displaystyle N/M}$ sortierte Teilfolgen der Länge ${\displaystyle M}$ (die sogenannten runs). Jede dieser Teilfolgen wird erzeugt, indem ${\displaystyle m}$ der ${\displaystyle n}$ Eingabeblöcke in den internen Speicher eingelesen, dort sortiert und anschließend wieder zurück in den externen Speicher geschrieben werden.[1]

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 ${\displaystyle 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 ${\displaystyle 2n}$ I/Os entspricht. Nach ${\displaystyle \Theta (\log _{m}n)}$ Merge-Phasen ist nur noch ein sortierter run übrig, das Ergebnis.[1]

Insgesamt benötigt der Algorithmus also ${\displaystyle \Theta (n\log _{m}n)}$ I/Os und ist somit optimal.[1]