4.6k 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)$
edited | 4.6k views
0

number of unique block addresses between two consecutive accesses to the same block address is bounded above by k.

what is this means:

number of  unique bocks addresses between two consecutive accesses to the same block address< k  or

number of  unique bocks addresses between two consecutive accesses to the same block address< k

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.
edited by
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

----------------------- Since A=3, cache is full (Is it so?)
1: hit
----------------------- Since A=3, cache is full (Is it so?)
1: hit
----------------------- 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
0
Sir can we say n/N miss is best case scenario as blocks are not replaced? How we will find worst case scenario when blocks are replace?

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

+7

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

0
Great approach
+1
@pawan you can take

n {1,2,3,4}

N {1,2,3,4,1,2,3,4}

K=3, A=4 then, there will be only one set it will be same as fully associative.

Then proceed you will get 4/8 miss ratio means n/N.
+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