<p>I don't know about a method for analyzing an arbitrary given algorithm to come up with a cache policy in general (this sounds quite hard), but this is essentially what's been done (optimally, in an asymptotic sense) on a case-by-case basis for most known <a href="https://en.wikipedia.org/wiki/Cache-oblivious_algorithm" rel="nofollow"><strong>cache-oblivious algorithms</strong></a>, by analyzing their divide-and-conquer structure. Cache-oblivious algorithms are known for FFT, matrix multiplication, sorting, and a few others. See the <a href="https://en.wikipedia.org/wiki/Cache-oblivious_algorithm" rel="nofollow">Wikipedia page</a> and references therein.</p>

CC BY-SA 3.0
2015-06-16T13:34:32.463Z
2015-06-16T13:34:32.463Z
Joshua Grochow
<p>I recently became interested in the general problem of optimizing memory usage in a situation where there is more than one kind of memory available, and there is a trade-off between the capacity of a given memory segment and the speed of accessing it.</p>

<p>The familiar example is a program deciding when to <em>read from</em> / <em>write to</em> the processor cache, RAM and hard drive (via virtual memory).</p>

<p>I am particularly interested in the special case where the amount of data (including the program itself) that needs to be loaded significantly exceeds the capacity of the fastest storage available (i.e. the trivial solution of "just load up everything" is inapplicable).</p>

<p>I found that a <a href="https://en.wikipedia.org/wiki/Cache_algorithms" rel="nofollow">Wikipedia page</a> describing some common cache algorithms, which is almost what I want. Unfortunately, these are a bit low-level: </p>

<ul>
<li>Many, such as LRU or MRU only make sense if you have subroutines that get accessed many times. If I have a program with a large number of subroutines, some of which are never accessed in a given run, and some of them are accessed one or two times, this strategy will never work because it can't build up enough data on what is commonly used and what is not.</li>
<li>Others, such as CLOCK, seem to deal with the peculiarities of implementation, rather than actually attacking the root of the problem.</li>
<li>I know there is a strategy where one first profiles a program during a test run, then provides the profile for the operating system to optimize accordingly. However, we must still solve the problem of providing a truly representative "example usage" while building the profile.</li>
</ul>

<p>What I really want to learn about is this:When we abstract away all the technicalities of hardware and software, and speak in a purely theoretical context, is it possible to somehow analyze the structure of an algorithm, to work out an effective cache strategy for it based on high-level comprehension of what the algorithm is doing?</p>

CC BY-SA 3.0
2015-06-17T01:44:27.483Z
You might be interested in the ["access graph" model](https://scholar.google.com/scholar?cluster=8127318400884197976&hl=en&as_sdt=0,5).
Neal Young
CC BY-SA 4.0
2024-10-17T15:55:08.717Z
"Competitive analysis" has something to say about this.  To take just one example, it is known that, on any request sequence, LRU with a cache of size k never incurs more than twice as many faults as the minimum possible number with a cache of size k/2.
Neal Young
<optimization><program-analysis>
What is the state of the art in cache algorithm theory?
Superbest
# What is the state of the art in cache algorithm theory?

(Asked by: username_0 on 2014-11-25)

I recently became interested in the general problem of optimizing memory usage in a situation where there is more than one kind of memory available, and there is a trade-off between the capacity of a given memory segment and the speed of accessing it.

The familiar example is a program deciding when to *read from* / *write to* the processor cache, RAM and hard drive (via virtual memory).

I am particularly interested in the special case where the amount of data (including the program itself) that needs to be loaded significantly exceeds the capacity of the fastest storage available (i.e. the trivial solution of "just load up everything" is inapplicable).

I found that a [Wikipedia page](https://en.wikipedia.org/wiki/Cache_algorithms) describing some common cache algorithms, which is almost what I want. Unfortunately, these are a bit low-level:

* Many, such as LRU or MRU only make sense if you have subroutines that get accessed many times. If I have a program with a large number of subroutines, some of which are never accessed in a given run, and some of them are accessed one or two times, this strategy will never work because it can't build up enough data on what is commonly used and what is not.
* Others, such as CLOCK, seem to deal with the peculiarities of implementation, rather than actually attacking the root of the problem.
* I know there is a strategy where one first profiles a program during a test run, then provides the profile for the operating system to optimize accordingly. However, we must still solve the problem of providing a truly representative "example usage" while building the profile.

What I really want to learn about is this:When we abstract away all the technicalities of hardware and software, and speak in a purely theoretical context, is it possible to somehow analyze the structure of an algorithm, to work out an effective cache strategy for it based on high-level comprehension of what the algorithm is doing?

**Tags:** optimization, program-analysis
> **Comments:**
> **username_1**: You might be interested in the ["access graph" model](https://scholar.google.com/scholar?cluster=8127318400884197976&hl=en&as_sdt=0,5).  
> **username_1**: "Competitive analysis" has something to say about this.  To take just one example, it is known that, on any request sequence, LRU with a cache of size k never incurs more than twice as many faults as the minimum possible number with a cache of size k/2.  

---

## 1 answers

### Answer by username_2 on 2015-06-16. Score: 2

I don't know about a method for analyzing an arbitrary given algorithm to come up with a cache policy in general (this sounds quite hard), but this is essentially what's been done (optimally, in an asymptotic sense) on a case-by-case basis for most known [**cache-oblivious algorithms**](https://en.wikipedia.org/wiki/Cache-oblivious_algorithm), by analyzing their divide-and-conquer structure. Cache-oblivious algorithms are known for FFT, matrix multiplication, sorting, and a few others. See the [Wikipedia page](https://en.wikipedia.org/wiki/Cache-oblivious_algorithm) and references therein.


---

