The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+47 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 & Architecture by Veteran (99.8k points)
edited by | 4.2k views

3 Answers

+60 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 >= 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 (355k points)
selected by
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
+2 votes

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

answered by Active (4.5k 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 

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

38,053 questions
45,543 answers
48,880 users