s are algorithm
s that have asymptotically optimal cache complexity
. Unlike cache
s contain no tuning parameters for the cache
size and line length and, indeed, are oblivious to nature of the cache
, but exploit locality of reference
to achieve cache-optimal
ity nonetheless. (Memory accesses which occur within a short time of each other tend to refer to memory addresses which are close to each other.) In other words, cache
-oblivious algorithms have no specific knowledge about the cache of the machine they are running on but have optimal cache performance nonetheless.
The simplest cache-oblivious algorithm is divide and conquer matrix multiplication. (Straightforward matrix multiplication has poor cache complexity, but divide and conquer does not.) The MIT LCS discovered cache-oblivious algorithms in 1994, when they realized that divide and conquer matrix multiplication is cache-optimal and requires no cache-specific tuning parameters. The term "cache-oblivious" was not adopted by the LCS until 1997.
A good introductory treatment of cache-oblivious algorithms is the Master's Thesis of Harold Prokop (also of MIT LCS).