cache oblivious algorithm
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
| Algorithm | Cache-Aware | Cache-Oblivious | Cache Complexity |
|---|---|---|---|
| Matrix Transpose | Tiled loops | Recursive divide | O(N²/B) |
| Matrix Multiply | Tiled (BLAS) | Recursive divide | O(N³/(B√M)) |
| Sorting | B-way merge | Funnel Sort | O((N/B)log_{M/B}(N/B)) |
| Search | B-tree | van Emde Boas layout | O(log_B N) |
| FFT | Recursive | Cache-oblivious FFT | O((N/B)log_M N) |
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.