Cache-Oblivious Algorithms are algorithms designed to use the memory hierarchy efficiently without knowing the cache size or line size as parameters — automatically achieving near-optimal cache performance across ALL levels of the memory hierarchy (L1, L2, L3, TLB, disk) simultaneously, without any tuning constants, making them portable across different hardware.

The Problem with Cache-Aware Algorithms

• Cache-aware: Algorithm uses cache parameters (B = block size, M = cache size) to tile/partition data.
• Example: Blocked matrix multiply with tile size chosen for L1 cache.
• Problem: Optimal tile for L1 ≠ optimal for L2 ≠ optimal for L3.
• Problem: Must re-tune for every new machine.

• Cache-oblivious: Algorithm has NO cache parameters — recursively divides the problem until subproblems fit in cache, regardless of cache size.

Key Idea: Tall Cache Assumption

• Assume an ideal cache of size M with block size B where $M = \Omega(B^2)$.
• If the algorithm is optimal under this model → it's optimal for ALL cache levels.
• Proof: Each level of the memory hierarchy acts as a cache for the next level.

Classic Cache-Oblivious Algorithms

Cache-Oblivious Matrix Multiply

1. Recursively divide A, B, C matrices into quadrants. 2. 8 recursive calls of size N/2: C₁₁ = A₁₁B₁₁ + A₁₂B₂₁, etc. 3. When submatrix fits in cache → all operations are cache hits. 4. This happens automatically at the right recursion level for ANY cache size.

van Emde Boas Layout (Cache-Oblivious Search)

• Store a binary search tree in memory using recursive "cut at half-height" layout.
• Top half stored contiguously, then each bottom subtree stored contiguously.
• Result: Any root-to-leaf path touches O(log_B N) cache lines — same as B-tree.
• No need to know B — layout is inherently cache-friendly.

Practical Impact

• Cache-oblivious algorithms often match hand-tuned cache-aware versions within 10-20%.
• Advantage: Zero tuning, portable, automatically optimal for TLB and disk too.
• Disadvantage: Higher constant factors, more complex implementation.

Cache-oblivious algorithms are an elegant theoretical framework with real practical value — they demonstrate that algorithms can be designed to exploit memory hierarchy efficiency without machine-specific parameters, providing portable performance across the increasingly diverse landscape of modern computing hardware.