The Gateway to Computer Science Excellence
+65 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)$
in CO and Architecture by Veteran (105k points)
edited by | 7.3k 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

+95 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$
by Veteran (425k points)
edited by
@disha Please see answer here
@arjun if first  block is mapped to 0th set suppose and next k unique blocks also mapped to 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".


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

sad  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?
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).


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. 

+11 votes

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

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.
+4 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
by Loyal (9.7k 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
50,645 questions
56,563 answers
101,656 users