Cache-oblivious algorithm

In computing, the cache-oblivious model is an abstract machine similar to many modern machines, featuring random access and a two-level cache. Unlike the external-memory model, which shares these features, it has no knowledge of the size of the cache and cannot perform explicit cache fetches. The benefit of the model is that an algorithm which is efficient on a cache-oblivious machine is likely to be efficient across many real machines without fine tuning for particular machine parameters.

The cache-oblivious model was conceived by Harald Prokop for his masters thesis at the Massachusetts Institute of Technology in 1999.

External links

• Harald Prokop. Cache-Oblivious Algorithms. Masters thesis, MIT. 1999.

• M. Frigo, C.E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS 99), p.285-297. 1999. Extended abstract at IEEE, at Citeseer.

• Erik Demaine. Review of the Cache-Oblivious Model. Notes for MIT Computer Science 6.897: Advanced Data Structures.