An access sequence of cache block addresses is of length \(N\) and contains n…
2014
An access sequence of cache block addresses is of length \(N\) and contains n unique block addresses. The number of unique block addresses between two consecutive accesses to the same block address is bounded above by \(k\). What is the miss ratio if the access sequence is passed through a cache of associativity \(A\geq k\) exercising least-recently-used replacement policy?
- A.
\(n/N\) - B.
\(1/N\) - C.
\(1/A\) - D.
\(k/n\)
Attempted by 74 students.
Show answer & explanation
Correct answer: A
Key idea: each distinct block causes one compulsory miss, and with A ≥ k and LRU those blocks are not evicted before their next use.
There are n distinct block addresses. Each distinct block must miss on its first access, so there are at least n misses.
Between two accesses to the same block there are at most k unique other blocks. Because the cache associativity A is at least k and the replacement policy is least-recently-used, a block will not be evicted before its next use.
Therefore all subsequent accesses to a given block are hits, and the total number of misses equals n. The miss ratio is n/N.