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 des kleineren/schnelleren sowie die Blockgröße 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.