+47 votes
4.2k views

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)$
asked
edited | 4.2k views

## 3 Answers

+60 votes
Best answer

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 >= 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.

answered by Veteran (355k points)
selected by
0
This question is unfairly interesting.
0
@Arjun sir, If we take references as 12345162 (k=5) it doesn't even follow first case strictly. Do we need to tolerate little sloppiness ?
0
requests for k blocks will also be a miss because they are unique right?
+3
+1
Can somebody explain the solution with a example? Like taking values of n, k, N and A and then explaining it. I'm unable to understand it and so annoyed right now.
+1
@Arjun sir, not getting how associativity plays role here. So tried example. Please check whats wrong.
N = 10
n = 4
k = A = 3
Accesses: 1,2,3,1,4,2,1,3,4,1

1: miss (load)
2: miss (load)
3: miss (load)
----------------------- Since A=3, cache is full (Is it so?)
1: hit
4: miss (by LRU, unload 2, load 4)
2: miss (by LRU, unload 3, load 2)
----------------------- Since A=3, cache is full (Is it so?)
1: hit
3: miss (by LRU, unload 4, load 3)
4: miss (by LRU, unload 2, load 4)
----------------------- Since A=3, cache is full (Is it so?)
1: hit

So for assumed parameter values, we are getting 7 misses.
Definitely, $\frac{n}{N}=\frac{4}{10}\neq 7$
What wrong I am doing?
0
@gateaspirant

in your example shouldn't k value  be 2 ?
0

Its given value, right? We may be given any value for k and we have to solve for it.
I guess according to Arjun sir's comment: https://gateoverflow.in/1922/gate2014-1-44?show=35005#c35005
Its ok to have k = A = 3. Right?

0
@gateaspirant

u have assumed its all mapping to the same block

1 goes to blck 1

2 goes to block 2

its doesnt fill the assocoativiity

hope am clear
0
can someone explain the answer with the following example:

N=6,n=3,k=2

Access Sequence: 1,2,3,1,2,3

Help will be appreciated
+2 votes

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

answered by Active (4.5k points)
+4

Please watch this video. Question is explained with an example.
0

@Pawan Kumar

In the question, it is given that cache is of associativity A≥k. But you've taken A=3 and k=5

+1 vote
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
answered by Loyal (8.3k points)
Answer:

+20 votes
4 answers
1
+21 votes
5 answers
2
+22 votes
3 answers
3