# GATE2014-1-44

9.5k 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
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.

Correct Answer: $A$

edited
0
0
@arjun if first  block is mapped to 0th set suppose and next k unique blocks also mapped to same..it will be k+1 and if associativity is k then we will have to replace and it will lead to all misses coz at k+1th block access we will replace first block ..please tell me where am doing wrong
1
it is bounded above by k- so k-1 unique accesses.
0
But if this happens what i assumed then all references will be misses from fst to last and hit ratio will become 1
2
not really. Then in question it must be "at least" and not "bounded by".
4

@arjun,

PS: In question it is given "bounded above by k", which means up to k-1 unique block accesses as k is an integer.

Here why you are saying k-1 max ? Why not equal to k ? If it is equal to k, then all our accesses become miss & none of the options ins correct ! (Though I would have selected first option in exam as it seems closest !)

In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set (K, ≤) is an element of K which is greater than or equal to every element of S.

Looking at defination of upper bound, it seems that we are allowed to be equal to upper bound !

2
yes. You are correct. it must have been k-1 or associativity > k. Still, there won't be all misses- because that can happen only if all unique block accesses goes to the same set.
0
What's the meaning of associacity A>= k excersing lru in the ques??

And what is " bouneded above by k" meaning?
4
Associativity k means we have space for "k" blocks in a location. Consider like a bag and you can keep 'k' books in it. (When k = 1, we have direct mapped.) So, only when k+1 unique books comes to a bag, it will be full and we need a replacement.
1
Ohhhh its like k way set associative... When k is 1 then direct mapped.

For this ques. Cache will have more thn k way associative(like k+1 or 2 etc.)

And what is the meaning of "bouneded above by k"??
0
it means <=. They could have used simpler English..
0

thanks though

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?
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?

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
0
Yes, thanks arjun Sir. I was getting confused on the same thing. A should be >=(n-1).
0

@Arjun

How can we say that the Mapping is set-associative mapping?

0

if the access sequence is passed through a cache of associativity A≥k exercising least-recently-used replacement policy?

Given in question

0

@Ram Swaroop

It can be fully associative mapping as well.

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

27

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

@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.
0

@Pawan Kumar 2

Although Your answer is right but I think that you should set with atleast K lines as it is mentioned in question that associativity A>=K.

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
1 vote
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

"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

## Related questions

1
7.6k views
Consider two processors $P_1$ and $P_2$ executing the same instruction set. Assume that under identical conditions, for the same input, a program running on $P_2$ takes $\text{25%}$ less time but incurs $\text{20%}$ more CPI (clock cycles per instruction) as compared to the program ... $P_1$. If the clock frequency of $P_1$ is $\text{1GHZ}$, then the clock frequency of $P_2$ (in GHz) is ______.
Consider a $6$-stage instruction pipeline, where all stages are perfectly balanced. Assume that there is no cycle-time overhead of pipelining. When an application is executing on this $6$-stage pipeline, the speedup achieved with respect to non-pipelined execution if $25$% of the instructions incur $2$ pipeline stall cycles is ____________
A machine has a $32-bit$ architecture, with $1-word$ long instructions. It has $64$ registers, each of which is $32$ bits long. It needs to support $45$ instructions, which have an immediate operand in addition to two register operands. Assuming that the immediate operand is an unsigned integer, the maximum value of the immediate operand is ____________
The memory access time is $1$ $nanosecond$ for a read operation with a hit in cache, $5$ $nanoseconds$ for a read operation with a miss in cache, $2$ $nanoseconds$ for a write operation with a hit in cache and $10$ $nanoseconds$ for a write operation ... operations. The cache hit-ratio is $0.9$. The average memory access time (in nanoseconds) in executing the sequence of instructions is ______.