The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+59 votes

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 and Architecture by Veteran (97.7k points)
edited by | 6.5k views

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

+81 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.

Correct Answer: $A$
answered by Veteran (414k points)
edited by
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?

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:
Its ok to have k = A = 3. Right?


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:


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).
+8 votes

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

answered by Active (4.2k points)


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

@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 @Rishav Kumar Singh How do you determine how many number of sets there are? Or what is the total no. of lines? Bcoz we need "no.of sets" to map the elements to their appropriate set numbers and then see if there is a hit or a miss. And N need not be equal to the no. of lines.

+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 (9.3k points)

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
49,811 questions
54,540 answers
75,596 users