edited by
22,502 views
126 votes
126 votes

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?

  1. $\left(\dfrac{n}{N}\right)$
  2. $\left(\dfrac{1}{N}\right)$
  3. $\left(\dfrac{1}{A}\right)$
  4. $\left(\dfrac{k}{n}\right)$
edited by

10 Answers

Best answer
146 votes
146 votes
There are $N$ accesses to cache.
Out of these $n$ are unique block addresses.
Now, we need to find the number of misses. (min. $n$ misses are guaranteed whatever be the access sequence due to $n$ unique block addresses).

We are given that between two consecutive accesses to the same block, there can be only $k$ unique block addresses. So, for a  block to get replaced we can assume that all the next $k$ block addresses goes to the same set (given cache is set-associative) which will be the worst case scenario (they may also go to a different set but then there is lesser chance of a replacement). Now, if associativity size is $\geq k$, and if we use LRU (Least Recently Used) replacement policy, we can guarantee that these $k$ accesses won't throw out our previously accessed cache entry (for that we need at least k accesses). So, this means we are at the best-cache scenario for cache replacement -- out of $N$ accesses we miss only $n$ (which are unique and can not be helped from getting missed and there is no block replacement in cache). So, miss ratio is $n/N$.

PS: In question it is given "bounded above by $k$", which should mean $k$ unique block accesses as $k$ is an integer, but to ensure no replacement this must be '$k-1$'. Guess, a mistake in question.

Correct Answer: $A$
edited by
26 votes
26 votes

Tried to do with taking some values.... kindly correct me if I went somewhere wrong thanks

8 votes
8 votes
Their are N access request for the cache blocks out this n
blocks are unique .

In between two access of the same block their are request of
(k-1) other block block.

And if their associativity >=k and use LRU, then
there will be only one cache miss for every unique block i.e.,
n and it will be the time when the enter the cahe for the first
time.  Therefore Miss ratio =(Cache miss)/(No. of request) = n/N
6 votes
6 votes
Easy Thinking: Only Compulsory Miss Happens

It is given that between any two access for the same block there is a gap less than k elements.

Now, if the cache set can contain atleast $k$ slots then there will not be any replacement in LRU strategy.

In question cache associativity is $>= k$ means $k$ or more slots available. So no misses once it's in cache.

So only miss possibility is the compulsory miss which happens the first time element is brought to cache.

So for $N$ access $n$ compulsory misses occur ($n$ are unique).

Means miss ratio $= \frac{n}{N}$

Ans: A) $\frac{n}{N}$
Answer:

Related questions