Cache-Oblivious Algorithmus

Ein cache-oblivious Algorithmus ist ein Algorithmus, der effizient auf Architekturen mit mehrstufiger Speicherhierarchie arbeitet, ohne deren genaue Parameter zu kennen. Diese Parameter sind zum Beispiel die Anzahl der Caches, die Größe der jeweiligen Cachezeilen oder deren Zugriffszeiten. Die Performance wird im sogenannten Idealized Cache Modell analysiert, in dem das Kostenmaß die Cache-Misses sind. Ein cache-oblivious Algorithmus ist optimal, wenn er die Caches asymptotisch optimal benutzt, also eine bis auf konstante Faktoren minimale Anzahl an Cache-Misses erzeugt.

Entwurfsziel ist eine gute Performance des gleichen Codes auf verschiedenen Maschinen mit vielen Speicherebenen, ohne dass Anpassungen an die Architektur gemacht werden müssen. (Für eine optimale Performance müssen allerdings noch Anpassungen an die jeweilige Hardware vorgenommen werden, die über die Speicherhierarchie hinausgehen.)

Cache-oblivious Algorithmen sind verwandt mit External Memory Algorithmen, bei denen im Gegensatz aber nur von einer zweistufigen Speicherhierarchie ausgegangen wird und bei denen die Größe $M$ des kleineren/schnelleren sowie die Blockgröße $B$ des größeren/langsameren Speichers dem Algorithmus als Eingabeparameter zur Verfügung stehen. Ein optimaler cache-oblivious Algorithmus für zwei Speicherebenen ist auch optimal für beliebig viele Speicherebenen.

Geschichte

Die erste Idee (und der Name) zu cache-oblivious Algorithmen stammt von Charles E. Leiserson aus dem Jahr 1996, die erste Veröffentlichung dazu ist die Masterarbeit von Harald Prokop am Massachusetts Institute of Technology von 1999. Dort werden bereits cache-oblivious Algorithmen zur Matrixtransposition, für die Schnelle Fourier-Transformation und fürs Sortieren vorgestellt.

Bereits vorher wurde eine Vielzahl von Algorithmen entwickelt, die als cache-aware bezeichnet werden können. Diese arbeiten ebenfalls optimal mit dem vorhandenen Caches, müssen dafür aber deren Parameter (Größe, Zeilenlänge) kennen.

Analyse im Idealized Cache Modell

Das Idealized Cache Modell. 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.

Cache-oblivious Algorithmen werden im Idealized Cache Modell (alternativ Cache Oblivious Modell) analysiert. Es basiert auf dem RAM-Modell. Der Prozessor arbeitet mit einer konstanten Anzahl an Registern auf einem unendlichen Hauptspeicher, in dem auf jede Speicherzelle in $O(1)$ zugegriffen werden kann. Als Erweiterung wird nun eine zweite Speicherebene, der Cache, zwischen Prozessor und Hauptspeicher eingefügt. Die weiteren Unterschiede im Idealized Cache Modell sind:

• Der Hauptspeicher ist unterteilt in Blöcke der Größe $B$.
• Der Cache kann $M$ Speicherworte enthalten. Dabei wird $M=\Omega (B^{2})$ angenommen (sog. tall cache assumption).
• Eine Lese-/Schreiboperation zwischen Prozessor und Hauptspeicher kann nun durch den Cache erledigt werden. Falls dies nicht möglich ist, spricht man von einem Cache-Miss.
• Bei einem Cache-Miss: Soll auf ein Speicherwort $w$ zugegriffen werden, das in einem Block $x$ des Hauptspeichers liegt, wird der ganze Block $x$ in den Cache geladen. Sollte der Cache bereits voll sein, muss vorher ein anderer Block verdrängt, also aus dem Cache zurück in den Hauptspeicher geschrieben werden.
• Der Cache hat volle Assoziativität, das heißt, dass jeder Speicherblock an jede Position des Caches geladen werden kann.
• Die Verdrängungsstrategie ist optimal. Es wird also angenommen, dass der Cache die genaue Reihenfolge aller (auch der zukünftigen) Speicherzugriffe kennt und immer den Block aus dem Cache verdrängt, auf den erst am weitesten in der Zukunft wieder zugegriffen wird. Dies ist natürlich eine unrealistische Annahme, aber eine LRU Strategie approximiert dies bis auf einen kleinen konstanten Faktor.

Die Parameter $M$ und $B$ sind dem Algorithmus dabei nicht bekannt.

Zum Analysieren der Komplexität eines Algorithmus im Idealized Cache Modell werden nur die Cache-Misses gezählt. Dies wird durch die sehr großen Unterschiede in der Zugriffszeit zwischen den verschiedenen Speicherebenen gerechtfertigt. Dabei werden die Unterschiede mit steigender Speicherkapazität immer extremer: Beispielsweise kann auf ein Register in einem Taktzyklus zugegriffen werden, ein Zugriff auf einen Wert in einem Cache benötigt bereits wenige Nanosekunden und ein Arbeitsspeicherzugriff dauert ca. 60–70 Nanosekunden. Noch extremer sind die Unterschiede bei Massenspeichermedien und Wechseldatenträgern, wo die Zugriffszeiten im Bereich von Millisekunden (bei Festplatten) bis Minuten (CDs, Magnetbänder) liegen können.

Beziehung zum External Memory Modell und zur Realität

Im External Memory Modell werden dem Algorithmus die Parameter $M$ und $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 $M$ und $B$ effizient ist. Genauso ergibt sich eine Effizienz über mehrere Speicherebenen, bei denen sich die Parameter $M$ und $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.

Beispiele

Die obere Matrix wird zeilenweise durchlaufen, die untere spaltenweise.

Viele cache-oblivious Algorithmen arbeiten nach dem Teile und Herrsche Prinzip, bei dem das Problem so weit in kleinere Instanzen aufgeteilt wird, dass die einzelnen Teilprobleme in den Cache passen. Diese können dann effizient gelöst und in einem cache-effizienten Verfahren wieder zu einer Lösung der ursprünglichen Instanz zusammengesetzt werden. Auch bei den beiden folgenden Algorithmen wird dieses Prinzip angewendet.

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 $m\times n$-Matrix $A$ und die Ausgabe soll in eine $n\times m$-Matrix $B$ geschrieben werden. Eine naive Lösung durchläuft $A$ zeilenweise und $B$ spaltenweise und kopiert in jedem Schritt einen Wert von $A$ nach $B$. Sind die Matrizen hinreichend groß, führt jeder Zugriff der spaltenweise durchlaufenen Matrix $B$ zu einem Cache-Miss. Damit ergibt sich eine Gesamtarbeit von $O(mn)$ und Cache-Komplexität von $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 $n'\times m'$ doppelt in den Cache passen (als Eingabe- und Ausgabeteilmatrix). Dann kann die Teilmatrix nach dem naiven Verfahren mit Arbeit $O(n'm')$ und Cache-Komplexität $O(n'm'/B)$ transponiert werden. Insgesamt ergibt sich eine optimale Arbeit von $O(mn)$ und Cache-Komplexität $O(1+mn/B)$. Theoretisch könnten die Teilmatrizen bis zu einer Größe von $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.

Transponieren einer Matrix mit Teile und Herrsche. a) Transposition von Matrix A als Ganzes. b) Transposition von den Teilmatrizen $A_{1}$ und $A_{2}$.

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 $n$ Einträgen rekursiv in zwei Schritten:

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

Die gesamte Komplexität liegt also in dem Merger, der auch Funnel genannt wird. Ein $k$-Merger erhält $k$ sortierte Folgen als Eingabe und gibt bei jedem Aufruf die nächsten $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 $k$-Merger ist rekursiv aus mehreren ${\sqrt {k}}$-Mergern zusammengesetzt (die Abbildung rechts zeigt einen 9-Merger): Es gibt insgesamt ${\sqrt {k}}$ Eingabemerger $I_{1},I_{2},\ldots ,I_{\sqrt {k}}$, auf die die $k$ Eingaben gleichmäßig verteilt werden. Jeder Eingabemerger schreibt seine Ausgabe in einen eigenen Puffer der Größe $2k^{3/2}$. Dazu gibt es einen Ausgabemerger $O$, dessen Eingänge mit den Puffern von $I_{1},I_{2},\ldots ,I_{\sqrt {k}}$ verbunden sind und dessen Ausgabe auch die Ausgabe des $k$-Mergers ist. Jeder der verbauten ${\sqrt {k}}$-Merger hat ${\sqrt {k}}$ Eingaben und produziert eine Ausgabe von $k^{3/2}$ Elementen.

Bei einem Aufruf des $k$-Mergers müssen nun $k^{3}$ Elemente ausgegeben werden. Dazu wird der Ausgabemerger $O$ insgesamt $k^{2/3}$-mal aufgerufen, der dabei in jedem Aufruf $k^{3/2}$ weitere Elemente ausgibt. Vor jedem Aufruf wird dabei sichergestellt, dass jeder Puffer in der Eingabe von $O$ mindestens $k^{3/2}$ Elemente enthält. Sollte dies bei Puffer $j$ nicht der Fall sein, wird zuerst Eingabemerger $I_{j}$ aufgerufen, der $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.

Siehe auch

• Speicherhierarchie
• External Memory Algorithmus

Ein 9-Merger, bestehend aus vier 3-Mergern (Eingabemerger $I_{1},I_{2},I_{3}$und Ausgabemerger $O$).