GATE CSE 2014 Set 1 | Question: 44

Question

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. $\left(\dfrac{n}{N}\right)$
• B. $\left(\dfrac{1}{N}\right)$
• C. $\left(\dfrac{1}{A}\right)$
• D. $\left(\dfrac{k}{n}\right)$

Comments

What if associativity is less than k?? Will that make any change to the final answer?

---

In this question our solution will not affected from  whatever page replacement algo is used , Correct me if i am wrong 

---

@Ray Tomlinson No , 
Let’s take MRU and the sequence is 1 2 3 5 6 3 , k=3 and assume all maps to one set
so now here it will be all misses as when 5 comes according to MRU previous 3 will gets replaced and for next 3 also there will be a miss 

Answer 1

As the access sequence has length N, it means there are a total of N cache accesses.
Out of which n are unique accesses. It means there must be atleast n cache misses(also known as compulsory misses)
Now in order to have more than n misses, ie. In order to have capacity misses, the block we just accessed, must be thrown out of the cache set before its next access.
In order to something happening like that in LRU policy, there must be >= k new cache accesses and they all must be mapped to that particular cache set( k is the associativity)
Now considering the worst case scenario of having set associativity equal to k, and the assumption that all the new cache accesses mapping to the same set in between the two consecutive cache accesses to the same block. As it is given that the number of unique block adresses between two consecutive accesses to the same block addresse is bounded by k(means it is less than k), thus that cache block will never be thrown out of the cache.
And we will not encounter any capacity misses.
So the miss ratio is equal to n/N

Answer 2

"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≥k exercising least-recently-used replacement policy"

This statement may seem confusing at first site, but that is where GATE tests you. This statement here simply states that there are no capacitive misses in the cache, only capacitive misses.

 

For associative caches, if the number of unique blocks accessed between two access of some block i is greater than the size of cache (associativity of the cache) , then there will be capacitive miss.

Here it has been clearly stated that the blocks accessed between two consecutive accessed is bounded above by k, where k<= A(associativity of the cache), so the number of unique blocks accessed between two consecutive access of some block i is never greater than size of cache, hence there will not be any capacitive miss.

Now since only compulsory misses are possible, compulsory miss occur every time when there is an access to unique block which is not already present in cache.

Here we have n unique blocks accessed out of total N requests sequence.

So miss ratio would be n/N

 

Comments

In the answer  ...there are no capacitive misses in the cache ,only capacitive misses….?

It should be compulsory misses in 2nd capacitive misses.

---

yes, that’s a typing mistake

Answer 3

 

Correct Answer: A

 

Answer 4

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

https://hazelcast.com/glossary/cache-miss/

---