Beziehung zum External Memory Modell und zur Realität

Im External Memory Modell werden dem Algorithmus die Parameter ${\displaystyle M}$ und ${\displaystyle B}$ als Teil der Eingabe übergeben und es macht keine Vorgaben über die Verdrängungsstrategie des Caches. Dadurch kann der Algorithmus die vorhandene Hardware noch um einen konstanten Faktor effizienter nutzen. Die Analyse im External Memory Modell ist sehr ähnlich, hier werden nur die Zugriffe auf den externen Speicher gezählt werden. Der Vorteil eines effizienten Algorithmus im Idealized Cache Modell ist, dass der gleiche Algorithmus auch auf Maschinen mit anderen ${\displaystyle M}$ und ${\displaystyle B}$ effizient ist. Genauso ergibt sich eine Effizienz über mehrere Speicherebenen, bei denen sich die Parameter ${\displaystyle M}$ und ${\displaystyle B}$ zwischen verschiedenen Ebenen zum Teil um Größenordnungen unterscheiden.

Das Modell eines idealen Caches ist deutlich einfacher als ein realer Cache. Gerade schnelle Caches (z. B. L1-Caches) haben für bessere Performance in der Regel keine vollständige Assoziativität. Außerdem existiert eine optimale Verdrängungsstrategie nur in der Theorie und muss in der Praxis approximiert werden. Die sich dadurch ergebenen Laufzeitunterschiede lassen sich in vielen Fällen jedoch beweisbar durch kleine konstante Faktoren einschränken.

Matrixtransposition

Als erstes Beispiel soll hier ein cache-oblivious Algorithmus zur Transposition einer rechteckigen Matrix vorgestellt werden, der auf Harald Prokop zurückgeht. Dabei steht die Eingabe in einer ${\displaystyle m\times n}$-Matrix ${\displaystyle A}$ und die Ausgabe soll in eine ${\displaystyle n\times m}$-Matrix ${\displaystyle B}$ geschrieben werden. Eine naive Lösung durchläuft ${\displaystyle A}$ zeilenweise und ${\displaystyle B}$ spaltenweise und kopiert in jedem Schritt einen Wert von ${\displaystyle A}$ nach ${\displaystyle B}$. Sind die Matrizen hinreichend groß, führt jeder Zugriff der spaltenweise durchlaufenen Matrix ${\displaystyle B}$ zu einem Cache-Miss. Damit ergibt sich eine Gesamtarbeit von ${\displaystyle O(mn)}$ und Cache-Komplexität von ${\displaystyle O(mn)}$. Der cache-oblivious Algorithmus nutzt aus, dass das Transponieren der gesamten Matrix in das Transponieren von zwei Teilmatrizen aufgeteilt werden kann. Dazu wird die Matrix entlang der größeren Dimension in zwei (annähernd) gleich große Teilmatrizen geteilt, bis die einzelnen Teile der Größe ${\displaystyle n'\times m'}$ doppelt in den Cache passen (als Eingabe- und Ausgabeteilmatrix). Dann kann die Teilmatrix nach dem naiven Verfahren mit Arbeit ${\displaystyle O(n'm')}$ und Cache-Komplexität ${\displaystyle O(n'm'/B)}$ transponiert werden. Insgesamt ergibt sich eine optimale Arbeit von ${\displaystyle O(mn)}$ und Cache-Komplexität ${\displaystyle O(1+mn/B)}$. Theoretisch könnten die Teilmatrizen bis zu einer Größe von ${\displaystyle 1\times 1}$ weiter zerteilt werden, in der Praxis sollte allerdings ein größerer Basisfall gewählt werden, da selbst kleinste Caches mehr als zwei Speicherworte groß sind und der Zusatzaufwand zum Zerteilen die Cacheeffekte in dieser Größenordnung dominiert.

Sortieren

Als weiteres Beispiel soll ein optimaler cache-oblivious Algorithmus zum Sortieren vorgestellt werden. Harald Prokop hat in seiner Masterarbeit zwei solche vorgestellt: Distribution Sort (basierend auf Quicksort) und Funnelsort. Letzterer basiert auf Mergesort und soll hier beschrieben werden:

Funnelsort sortiert ein Array mit ${\displaystyle n}$ Einträgen rekursiv in zwei Schritten:

1. Zerteile das Array in ${\displaystyle n^{1/3}}$ Teilarrays, von denen jedes Größe ${\displaystyle n^{2/3}}$ hat. Sortiere die Teilarrays rekursiv.
2. Verschmelze (engl. merge) die sortierten Teilarrays mit einem ${\displaystyle n^{1/3}}$-Merger.

Die gesamte Komplexität liegt also in dem Merger, der auch Funnel genannt wird. Ein ${\displaystyle k}$-Merger erhält ${\displaystyle k}$ sortierte Folgen als Eingabe und gibt bei jedem Aufruf die nächsten ${\displaystyle k^{3}}$ Elemente der sortierten Folge aus, die aus der Verschmelzung der Eingabefolgen entsteht. Im Unterschied zu Mergesort wird bei Funnelsort auch das Mergen rekursiv gemacht. Diese rekursive Zerlegung der Merge-Operation führt dazu, dass die einzelnen Teilprobleme irgendwann in den Cache passen.

Ein ${\displaystyle k}$-Merger ist rekursiv aus mehreren ${\displaystyle {\sqrt {k}}}$-Mergern zusammengesetzt (die Abbildung rechts zeigt einen 9-Merger): Es gibt insgesamt ${\displaystyle {\sqrt {k}}}$ Eingabemerger ${\displaystyle I_{1},I_{2},\ldots ,I_{\sqrt {k}}}$, auf die die ${\displaystyle k}$ Eingaben gleichmäßig verteilt werden. Jeder Eingabemerger schreibt seine Ausgabe in einen eigenen Puffer der Größe ${\displaystyle 2k^{3/2}}$. Dazu gibt es einen Ausgabemerger ${\displaystyle O}$, dessen Eingänge mit den Puffern von ${\displaystyle I_{1},I_{2},\ldots ,I_{\sqrt {k}}}$ verbunden sind und dessen Ausgabe auch die Ausgabe des ${\displaystyle k}$-Mergers ist. Jeder der verbauten ${\displaystyle {\sqrt {k}}}$-Merger hat ${\displaystyle {\sqrt {k}}}$ Eingaben und produziert eine Ausgabe von ${\displaystyle k^{3/2}}$ Elementen.

Bei einem Aufruf des ${\displaystyle k}$-Mergers müssen nun ${\displaystyle k^{3}}$ Elemente ausgegeben werden. Dazu wird der Ausgabemerger ${\displaystyle O}$ insgesamt ${\displaystyle k^{2/3}}$-mal aufgerufen, der dabei in jedem Aufruf ${\displaystyle k^{3/2}}$ weitere Elemente ausgibt. Vor jedem Aufruf wird dabei sichergestellt, dass jeder Puffer in der Eingabe von ${\displaystyle O}$ mindestens ${\displaystyle k^{3/2}}$ Elemente enthält. Sollte dies bei Puffer ${\displaystyle j}$ nicht der Fall sein, wird zuerst Eingabemerger ${\displaystyle I_{j}}$ aufgerufen, der ${\displaystyle k^{3/2}}$ neue Elemente in den Puffer schreibt. Die Größe des Puffers wurde dabei gerade so gewählt, dass immer ausreichend Platz vorhanden ist.

Brodal und Fagerberg beschreiben darüber hinaus eine Variante Lazy Funnelsort, in der ein Puffer erst dann neu befüllt wird, wenn er vollständig leer ist. Dies kann in der Praxis etwas schneller sein. Die Autoren beweisen dazu, dass es in der Theorie zur gleichen Anzahl Cache Misses kommt.