Cache Replacement Policies
Predictability calculated by RELACS tool
Policy |
Assoc. |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
LRU |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
FIFO |
1/2 |
1/3 |
1/4 |
1/5 |
1/6 |
1/7 |
1/8 |
|
PLRU |
1 |
– |
0 |
– |
– |
– |
0 |
|
RANDOM |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
LRU (Least Recently Used)
Minimal life span (mls) – minimal no. of pairwise different memory blocks needed to evict a just-visited mem block out of cache. Replacement policy with larger mls preferred.
Upper bound of mls = L. mls of LRU = L = no. of cache lines.
Non-LRU policies are considered to be much less predictable than LRU, and it would be very difficult to develop precise and efficient analyses for them. It is recommended to only use LRU caches when timing predictability is a major concern in the system design.