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

Bounded above means upper bound and bounded below means lower bound.

“Bounded above by k” means at most k (never more than k).

---

The correct answer is A. $\left(\frac{n}{N}\right)$
 

The Initial Misses (Compulsory Misses)

The access sequence has a total length of $N$, but it only contains $n$ unique block addresses.

When the cache first turns on, it is empty. Every time one of these $n$ unique blocks is requested for the very first time, the cache will not have it. This results in an unavoidable miss. Therefore, we are guaranteed to have exactly $n$ compulsory (or cold-start) misses.

The Re-accesses (Surviving Eviction)

After a block is brought into the cache, what happens when we need to access it again? To find out if it's still in the cache (a hit) or if it was evicted (a miss), we have to look at the rules provided:

• The Gap: There are at most $k$ other unique blocks accessed between two consecutive accesses to our target block.

• The Cache: It uses a Least-Recently-Used (LRU) policy and has an associativity of $A$, where $A \ge k$.

To mathematically guarantee a cache hit on a re-access, we must evaluate the absolute worst-case scenario: What if the access pattern is so unlucky that all $k$ intervening blocks map to the exact same cache set as our target block?

 

The Role of Associativity ($A \ge k$)

Associativity only matters when multiple blocks fight for space in the same set. In our worst-case scenario, all $k$ intervening blocks flood into our target block's set.

Here is how the associativity rule saves the day:

• Associativity ($A$) defines exactly how many "slots" exist within a single set.

• If $k$ new blocks enter the set, they push our original target block down the LRU stack toward eviction.

• However, because the problem guarantees that $A \ge k$ (the number of slots is greater than or equal to the number of invading blocks), the set is physically large enough to hold all $k$ new blocks plus our original target block.

• Our block might become the absolute "Least Recently Used" block at the bottom of the stack, but it will not be kicked out.

 

The Final Calculation

Because our block survives the absolute worst-case mapping scenario, it will certainly survive any normal scenario where the $k$ blocks are scattered across different sets.

Therefore, every single re-access to a block is guaranteed to be a cache hit. There are zero conflict misses and zero capacity misses. The only misses that occur in the entire sequence are the initial $n$ compulsory misses.

$$\text{Miss Ratio} = \frac{\text{Total Misses}}{\text{Total Accesses}} = \frac{n}{N}$$

---

Meaning Of Each and every Line with detailed explanation :

An access sequence of cache block addresses is of length $N$ and contains $n$ unique block addresses.

Meaning of this Line  ==> The CPU requests data from memory $N$ times in total. However, among those $N$ total requests, there are only $n$ distinct (different) memory blocks being asked for. 

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

Meaning of this Line ==> Whenever a specific block  is accessed and then accessed again later, the number of different other blocks requested in between those two accesses is at most $k$.

For examples : B1--> B2 --> B3 --> B1 between first B1 and second B2 accessed the block accessed are B2 & B3 ..That means unique block between two consecutive access to same block = 2 

If the access sequence is passed through a cache of associativity $A \ge k$

Meaning of this Line ==> The cache set can hold at least $A$ blocks, where $A$ is greater than or equal to $k$.

Solution by taking examples

Sequence length ($N$) = $8$

Unique blocks ($n$) = $3$ 

Maximum unique intermediate blocks ($k$) = $2$

Cache Associativity ($A$) = $3$ 

Sequence: B1,B2,B3,B1,B2 ,B3,B1,B2

1st access (B1) : Not in cache $\rightarrow$ MISS (Compulsory). Cache = B1

2nd access (B2): Not in cache $\rightarrow$ MISS (Compulsory). Cache = B1,B2

3rd access (B3): Not in cache $\rightarrow$ MISS (Compulsory). Cache = B1,B2,B3

4th access (B1)

Between 1st B1 and 2nd B1, unique blocks accessed = B2,B3.

B1 was never evicted because cache capacity $A \ge 2$. It means that B1 is present so there is "HiT"

Subsequent accesses (B2,B3,B1,B2): All were previously loaded and never evicted because $A \ge k$. So All are Hit

Note : capacity Miss =0 , conflict Miss =0 ,compulsory miss = 3 ... So total miss = 3 which is equal to n..

hence , Miss Ratio = Total Miss / Total Access = 3/ 8 = n / N

Answer 1

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$

Comments

@disha Please see answer here

---

@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

---

it is bounded above by k- so k-1 unique accesses.

---

But if this happens what i assumed then all references will be misses from fst to last and hit ratio will become 1

---

not really. Then in question it must be "at least" and not "bounded by".

---

@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 !

Please clarify !

---

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.

---

What's the meaning of associacity A>= k excersing lru in the ques??

And what is " bouneded above by k" meaning?

---

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.

---

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

---

it means <=. They could have used simpler English..

---

  thanks though

---

This question is unfairly interesting.

---

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

---

requests for k blocks will also be a miss because they are unique right?

---

https://courses.cs.washington.edu/courses/cse378/09wi/lectures/lec16.pdf

https://courses.cs.washington.edu/courses/cse378/09wi/lectures/lec15.pdf

---

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.

---

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

---

@gateaspirant

in your example shouldn't k value  be 2 ?

---

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?

---

@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

---

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

---

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

---

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.

---

What is k and a  still not get

---

Yes, thanks arjun Sir. I was getting confused on the same thing. A should be >=(n-1).

---

@Arjun

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

---

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

Given in question

---

@Ram Swaroop

It can be fully associative mapping as well. 

---

“...but to ensure no replacement this must be 'k−1'. Guess, a mistake in question.”

I could not understand this part. Can any one please explain?

---

I'm getting miss ratio (a-1/a) for the worst case scenario, is that correct?

For example, let's say there are 8 sets each contains 4 blocks which is A and k = 3.

For this access sequence 0,8,16,24,0,32,40,48,0,8,16,24…

It's going to be only one hit for each A(I.e. 4) access.

---

@Krishnendu Ghosh

Consider a $2-way$ set associative cache with $4$ sets.

If $k = A = 2$, then I can have this access sequence: $100, 200, 300, 100$.

This will cause the replacement of the block containing address $100$ when I try to access address $300$ because they all map to the same set i.e. the first set.

If $k < A$, then I cannot have that access sequence. In the worst case I can have: $100, 200, 100$ for $k =1$. So, even if they map to the same set I always have space for all of them to coexist.

---

@JeygMR

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

Your access sequence doesn’t satisfy this.

---

Does the scenario depend on the type of replacement policy used?

---

In this question, as we are having enough cache memory space to store all n unique sequences and we don’t need to replace any block to accommodate a new one, hence there’s no significance of LRU or any other replacement algorithm here.

---

A set is bounded above by K, which means every element in the set is <= K.

So, I guess in the question it should be k-1 rather than k, to get the potential answer as n/N.

---

Total number of block addresses to be accessed is N and it contains all block addresses  i.e. unique+duplicates.
There are n unique block addresses so reamining N-n are no. of duplicate block addresses.

Each duplicate block address will result 1 hit , an there are (N-n) duplicate blocks so (N-n) hits are there ,so hit rate= hits/total accesses
hit rate= (N-n)/N= 1- n/N
hence miss rate= 1-(hit rate) = 1-(1-n/N) = n/N
Hence OPTION A is correct

---

Had the same doubt......question should correct

***Either associativity › k

***Or bounded by k-1

Answer 2

Easy Thinking: Only Compulsory Miss Happens

It is given that between any two access for the same block there is a gap less than k elements.

Now, if the cache set can contain atleast $k$ slots then there will not be any replacement in LRU strategy.

In question cache associativity is $>= k$ means $k$ or more slots available. So no misses once it's in cache.

So only miss possibility is the compulsory miss which happens the first time element is brought to cache.

So for $N$ access $n$ compulsory misses occur ($n$ are unique).

Means miss ratio $= \frac{n}{N}$

Ans: A) $\frac{n}{N}$

Comments

best one

---

Great Approach

Answer 3

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

Comments

@Pawan Kumar

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

---

Great approach

---

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

---

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

Answer 4

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

Answer 5

"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

---

beautiful explanation, thanks.

---

Thanks Man for this answer! At first i Thought i havent studied this topic yet (seems very complex at first )

Answer 6

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