Cache-oblivious algorithm
A cache-oblivious algorithm does not use cache capacity or transfer-block size as tuning parameters in its computation or data layout.
Its analysis may still depend on those parameters. The ideal-cache model counts transfers between two memory levels, with a fully associative cache and optimal offline replacement. The name alone does not imply an efficient algorithm. [1]
Recursive layouts can expose locality at several scales. Bender, Demaine and Farach-Colton give dynamic search trees whose transfer bounds do not require the algorithm to know block size. Their first construction matches the classical B-tree search bound; its update guarantee is amortized, whereas the classical comparison is worst-case. [2]
Frigo et al., Lemma 12, bounds LRU misses by twice the misses of an optimal cache of half its capacity, not the same capacity. [1]
Relations
Citations
- Frigo, Leiserson, Prokop and Ramachandran. Cache-Oblivious Algorithms. FOCS 1999, pp. 285-297; sections 1 and 6, Lemma 12 and Corollary 13.
- Bender, Demaine and Farach-Colton. Cache-Oblivious B-Trees. SICOMP 35(2), 2005, pp. 341-358, sections 1-2. DOI 10.1137/S0097539701389956.
Further reading
Sources & caveats
- Primary-source terminology and theoretical guarantees; no performance measurement or implementation replication.