The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+55 votes
5.1k 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 in CO & Architecture by Veteran (111k points)
edited by | 5.1k 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

3 Answers

+74 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 $\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.
answered by Veteran (367k points)
edited by
+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
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?

Please help
0
I still don't understand because n/N in any case is the least posssible miss ratio. The additional constraints in the question don't change anything.
0
What is k and a  still not get
+5 votes

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

answered by Active (4.7k points)
+11


 

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.
+2 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
answered by Loyal (8.7k points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,147 questions
49,639 answers
163,290 comments
65,807 users