Cache-oblivious Algorithm - Idealized Cache Model

Idealized Cache Model

Cache-oblivious algorithms are typically analyzed using an idealized model of the cache, sometimes called the cache-oblivious model. This model is much easier to analyze than a real cache's characteristics (which have complicated associativity, replacement policies, etcetera), but in many cases is provably within a constant factor of a more realistic cache's performance.

In particular, the cache-oblivious model is an abstract machine (i.e. a theoretical model of computation). It is similar to the RAM machine model which replaces the Turing machine's infinite tape with an infinite array. Each location within the array can be accessed in time, similar to the Random access memory on a real computer. Unlike the RAM machine model, it also introduces a cache: a second level of storage between the RAM and the CPU. The other differences between the two models are listed below. In the cache-oblivious model:

• Memory is broken into lines of words each
• A load or a store between main memory and a CPU register may now be serviced from the cache.
• If a load or a store cannot be serviced from the cache, it is called a cache miss.
• A cache miss results in one line being loaded from main memory into the cache. Namely, if the CPU tries to access word and is the line containing, then is loaded into the cache. If the cache was previously full, then a line will be evicted as well (see replacement policy below).
• The cache holds words, where . This is also known as the tall cache assumption.
• The cache is fully associative: each line can be loaded into any location in the cache.
• The replacement policy is optimal. In other words, the cache is assumed to be given the entire sequence of memory accesses during algorithm execution. If it needs to evict a line at time, it will look into its sequence of future requests and evict the line that is accessed furthest in the future. This can be emulated in practice with the Least Recently Used policy, which is shown to be within a small constant factor of the offline optimal replacement strategy (Frigo et al., 1999, Sleator and Tarjan, 1985).

To measure the complexity of an algorithm that executes within the cache-oblivious model, we can measure the familiar (running time) work complexity . However, we can also measure the cache complexity, the number of cache misses that the algorithm will experience.

The goal for creating a good cache-oblivious algorithm is to match the work complexity of some optimal RAM model algorithm while minimizing . Furthermore, unlike the external-memory model, which shares many of the listed features, we would like our algorithm to be independent of cache parameters ( and ). The benefit of such an algorithm is that what is efficient on a cache-oblivious machine is likely to be efficient across many real machines without fine tuning for particular real machine parameters. Frigo et al. showed that for many problems, an optimal cache-oblivious algorithm will also be optimal for a machine with more than two memory hierarchy levels.