Content deleted Content added
No edit summary |
LRU vs. optimal replacement |
||
Line 7:
:No, it's basically correct. The following lemma is proved in the Frigo paper from the references:
::Lemma 12. Consider an algorithm that causes Q'(n;Z,L) cache misses on a problem of size n using a (Z, L) ideal cache. Then, the same algorithm incurs Q(n;Z,L) ≤ 2Q'(z;Z/2,L) cache misses on a (Z,L) cahce that uses LRU replacement.
:Note that, technically, you need an LRU cache of twice the size of the optimal-replacement cache to simulate it within a factor of two.
| |||