cache oblivious algorithm

**Cache-Oblivious Algorithms** are **algorithms designed to achieve near-optimal cache performance across all levels of the memory hierarchy without requiring knowledge of cache sizes, line sizes, or the number of cache levels — achieving this universality through recursive divide-and-conquer structures that naturally adapt to any cache configuration**. **Theoretical Foundation:** - **Ideal Cache Model**: analysis assumes a two-level memory hierarchy with cache size M and line size B; an algorithm is cache-oblivious if it achieves optimal cache complexity Q(N;M,B) without M or B as parameters — the performance automatically extends to all levels (L1, L2, L3, DRAM, disk) - **Tall Cache Assumption**: analysis requires M = Ω(B²) — cache is big enough to hold at least B cache lines; satisfied by all practical caches (L1: 32KB with 64B lines → B²=4KB ≪ M) - **Optimal Bounds**: cache-oblivious matrix multiply achieves Q = O(N³/(B√M)), matching cache-aware lower bound; cache-oblivious sorting achieves Q = O((N/B) log_{M/B}(N/B)), matching external-memory sorting bound - **Universality**: since the algorithm doesn't use M or B parameters, the same binary achieves near-optimal performance on machines with different cache sizes — no tuning, no recompilation, no architecture-specific parameters **Core Algorithmic Patterns:** - **Recursive Matrix Multiply**: divide each matrix into 4 quadrants recursively until base case fits in cache; multiply quadrants using 8 recursive multiplications and additions; cache complexity emerges from the recursion naturally matching cache line size at the appropriate depth - **Cache-Oblivious Stencil**: space-time tiling using trapezoidal decomposition — divide 1D stencil computation into space-time trapezoids that recurse until fitting in cache; generalizes to 2D/3D stencils with hyperplane cuts - **Funnel Sort**: K-way merge using a funnelsort tree; K-funnel recursively merges K^(1/2) sorted sequences using K^(1/2) sub-funnels; achieves optimal O((N/B) log_{M/B}(N/B)) I/O complexity - **Van Emde Boas Layout**: stores a binary tree in memory using recursive decomposition — top half of tree stored contiguously, then bottom subtrees stored recursively; achieves O(log_B N) cache misses per search **Practical Considerations:** - **Constant Factors**: cache-oblivious algorithms often have 2-5× larger constant factors than cache-aware counterparts due to recursive overhead and suboptimal base cases — matters for small-to-medium problem sizes - **Base Case Optimization**: switching from recursion to iterative, cache-aware kernels at small sizes (fitting in L1) hybridizes the approach — cache-oblivious for outer levels, tuned kernels for inner - **Prefetch Interaction**: hardware prefetchers optimized for sequential/strided patterns may perform poorly with recursive access patterns — software prefetch hints can help bridge the gap - **TLB Effects**: recursive decomposition can increase TLB pressure if working sets span many virtual pages — huge pages (2MB/1GB) mitigate TLB miss penalties Cache-oblivious algorithms represent **a profound theoretical contribution showing that explicit cache management is unnecessary for achieving optimal memory hierarchy utilization — though in practice they are most valuable for portable library code and multi-level cache hierarchies where manual tuning of architecture-specific parameters is infeasible**.