GATE CSE 2017 Set 1 | Question: 51

Question

Consider a $2$-way set associative cache with $256$ blocks and uses $\text{LRU}$ replacement. Initially the cache is empty. Conflict misses are those misses which occur due to the contention of multiple blocks for the same cache set. Compulsory misses occur due to first time access to the block. The following sequence of access to memory blocks :

      $\big \{0,128,256,128,0,128,256,128,1,129,257,129,1,129,257,129 \big \}$

is repeated $10$ times. The number of conflict misses experienced by the cache is _________ .

Comments

More questions to practice –

https://gateoverflow.in/20086/page-replacement 

https://gateoverflow.in/30994/direct-mapping-and-types-of-misses 

Read - 

https://gatecse.in/cache-misses/

 

---

endurance1

i exactly did the same mistake!😥

---

@jatinmittal199510

Thanks for the references :)

Answer 1

$\{0,128,256,128,0,128,256,128,1,129,257,129,1,129,257,129\}$

1$^{\text{st}}$ Iteration:

For $\left \{ 0,128,256,128,0,128,256,128 \right \}$

\begin{array}{|l|c|l|} \hline \textbf {Block ID} \ & \textbf{Type} &  \textbf{Set 0 content } \\\hline \text{0} & \text{Compulsory Miss} & \text{0} \\\hline\text{128} & \text{Compulsory Miss} & \text{0   128} \\\hline \text{256} & \text{Compulsory Miss} & \text{128   256}\\\hline \text{128} & \text{Hit} & \text{256   128} \\\hline \text{0} & \text{Conflict miss} & \text{128   0} \\\hline \text{128} & \text{Hit} & \text{0   128} \\\hline \text{256} &  \text{Conflict miss} & \text{128   256} \\\hline \text{128} & \text{Hit} & \text{256   128} \\\hline \end{array}

Total number of conflict misses $=2$;

Similarly for  $\left \{ 1,129,257,129,1,129,257,129 \right \}$, total number of conflict misses in $\text{set1} = 2$

Total number of conflict misses in $1^{\text{st}}$ iteration $= 2+2=4$

$2^{\text{nd}}$ iteration:

for $\left \{ 0,128,256,128,0,128,256,128 \right \}$

\begin{array}{|l|c|l|} \hline \textbf {Block ID} \ & \textbf{Type} &  \textbf{Set 0 content } \\\hline \text{0} & \text{Conflict Miss} & \text{128   0} \\\hline\text{128} & \text{Hit} & \text{0   128} \\\hline \text{256} & \text{Conflict miss} & \text{128   256}\\\hline \text{128} & \text{Hit} & \text{256   128} \\\hline \text{0} & \text{Conflict miss} & \text{128   0} \\\hline \text{128} & \text{Hit} & \text{0   128} \\\hline \text{256} & \text{Conflict miss} & \text{128   256} \\\hline \text{128} & \text{Hit} & \text{256   128} \\\hline \end{array}

Total number of conflict misses $= 4$.

Similarly for  $\{1,129,257,129,1,129,257,129\}$, total number of conflict misses in $\text{set1} = 4$

Total Number of conflict misses in $2^{\text{nd}}$ iteration $= 4+4=8$

Note that content of each set is same, before and after $2^{\text{nd}}$ iteration. Therefore each of the remaining iterations will also have $8$ conflict misses.

Therefore, overall conflict misses $= 4+8\ast 9 = 76$

Comments

@Suraj Sir, Please can you share a link which provides description of Conflict Miss, Compulsory Miss. Possibly if it contains the numerical solved, it'll be an added advantage stating the above concept Sir. Thanks in advance. Right now naive to these concepts.

---

These misses are explained in details in  "Computer Architectures: A Quantitative Approach'" book by D. A. Patterson and J. L. Hennessy, @Arjun do you know some online link which explains these concepts in details?

---

I'll get them if possible. The fact is that the same question used to be asked a lot in ME mock tests but unfortunately they used to give wrong solution as in the key :) I would like to know if any got this correct because this was discussed here at least 2 times.

---

@Suraj Sir and Arjun Sir, then too Thanks. I'll try to search some sources myself too. :)

---

@Suraj Sir, I've downloaded the said book. Is it worth referring for CO numerical ques?. And Thanks a tonnes again. :)

---

I read (did not solve numerical questions, so cant' comment) it and I found it very useful to clear basic concepts.

---

But a miss can be both,

compulsary and conflict.

here 256 is both compulsary and conflict miss  also according to definition written in question.

so total conflict miss is 78

---

No, it isn't. Read the definition carefully

which occur due to the contention of multiple blocks

As per this first access to any block can never be a conflict miss.

---

Not getting properly,

there is a contention for block no 256 with block no 0.

justify ur comment sir.

i am going to file against this question

---

Yup, you are right, if we analyze both statements separately. Accessing 256th block in 1st iteration also satisfies the given definition of conflict miss, though it is more clear that it'll experience compulsory miss, but you can argue :)

1) Conflict misses are those misses which occur due to the contention of multiple blocks for the same cache set.

2)Compulsory misses occur due to first time access to the block.

---

@suraj so what is it then? first time access of 256th block is compulsory miss as well as conflict miss? because it is contesting for same cache set

Is this a bad question?

---

I won't say it is a bad question. People consider this type of miss as compulsory miss.

---

"Conflict misses are misses that would not occur if the cache were fully associative with LRU replacement."

Check whether the first reference to 256 was not missed if cache was fully associative with LRU replacement. Is it?? It is not.. Cause in any case 256 was never present in the cache before and so if cache was fully associative with LRU replacement then also first reference to 256 would have been a miss only, i.e compulsory miss. So first reference to 256 and first reference to 257 those are compulsory miss only. Not conflict miss.

For reference: https://stackoverflow.com/questions/33314115/whats-the-difference-between-conflict-miss-and-capacity-miss

---

wired enough to know :O

---

repeated 10 times means total 11 times? First time is not repeatition.Second iteration is first repitions.So total times it should be 11?Arjun sir,please clarify

there was some OS question on page fault which says access sequence repeated three times,but there we take total 4 iterations.I am not able to find it now.SO why here not 11 total iterations?

---

@rahul sharma. The question says:

The following sequence of access to memory blocks: ... is repeated 10 times.

So, this sequence is in total done 10 times.

---

See https://gateoverflow.in/1992/gate2014-2-33 @Rishabh. What is the difference that in current question it is 10 times and in this link it is 4 times

---

Now a program accesses the pages numbered 1, 2, ..., 100 in that order, and repeats the access sequence THRICE.

Here it says that program accesses these pages, AND repeats the sequence thrice. So, one + 3 MORE

But in this question it says: The following sequence is repeated 10 times. So, it is accessed TOTAL 10 times.

Try reading both questions again more carefully(and slowly).

---

M NOT getting this question

how to calculate no. of lines in cache memory?

as for LRU we need to know the no. of lines.. m getting confused plz somebody help

HELP...

---

$$\text {No. of line in cache memory }= \frac{\text{Total number of blocks in cache}}{\text{Associativity given}} \\= \frac{256 \ blocks}{2}=128 lines$$

---

Cache line is same as cache block.

https://cseweb.ucsd.edu/classes/su07/cse141/cache-handout.pdf

---

what would be the answer if asked max no. of conflict misses;

---

Can any one please clarify this

Can a set associatuva cache have a capacity miss?

If yes why....

---

No, it won't.

---

What is the general definition of conflict miss?

I want to ask that  should  we have to consider first access of block 256 as conflict miss?(in case if nothing is defined about conflict miss in the question)

---

It has only one definition and that doesn't count the first access.

---

Thanks a lot bro

---

@ Devshree Dubey

Helped me to understand conflict miss ,especially

https://gatecse.in/cache-misses/

---

I found this conflict miss definition helpful = Conflict misses are those misses which occur when an access tries to fill a filled block even if other blocks are empty.(Note- First misses are not counted as conflict misses)

---

Easy one. But that's wrong definition and will get you negative marks. Where did you see it?

---

Link, Could you elaborate what is wrong in the definition and correct it

---

Compulsory Misses : The miss caused by the first time access of a block.

Conflict Misses : A miss caused due to insufficient set size . Cannot happen in a fully associative cache

Capacity Misses : A miss caused due to insufficient cache size. (All misses after compulsory misses , in fully associative caches.)

A good way to differentiate between conflict and capacity miss : what would’ve happen if the cache was fully associative and you’ll get the answer .

---

Now , there could be another doubt :

What miss it would be ,if the cache is full and a fresh block is accessed , whether it would be a capacity miss or compulsory miss. This will be a compulsory miss, as no matter the size of cache this miss is guaranteed to happen.

https://youtu.be/4_9VXZ2Hg9E?t=222 

---

Thanks shashank from another shashank

---

So after reading all answers and comments I conclude as follows:

1. Compulsory miss: If you are accessing block for first time it is compulsory miss, means you have to have this miss as it is new.
2. Conflict Miss: Means technically cache had capacity to store it but because of the way it is organized (like in set associative k-way, you are forced to map a block in particular set which is full though other sets might be empty) you will have this miss, means if you were allowed to use it as direct mapping you don’t have conflict miss.
3. Capacity Miss: means it is not a new block (otherwise compulsory miss) and for it no restriction was there on organization of cache (you could use cache full capacity like in direct mapped ) and still you have miss then capacity miss.
4. So we can also say that Compulsory Miss, Capacity Miss and Conflict Miss is Mutually Exclusive to each other(a miss could be only one of them at a time)

---

Note:

In the first iteration, 256 has been counted as a compulsory miss, earlier I thought that I could be a conflict miss but actually, it is not and the same thing is for 257.

 

---

Why Set 0 has maximum 2 memory blocks??

---

@Swarnava Bose because we have 2-way set associative cache .

In general for a k-way set associative cache we have k blocks in one set. 

---

“Note that content of each set is same, before and after 2nd iteration. Therefore each of the remaining iterations will also have 8 conflict misses.”
how did u reach to this conclusion

Answer 2

In first iteration there are 4 conflict misses and 6 compulsory misses.

In second iteration, there are 4+4 = 8 conflict misses and this is the same for iterations 3..10. So, totally $8 \times 9 + 4 = 76$ conflict misses.

Comments

How is it 4 conflict miss at the first time?

when  256 try to access the cache then already we have (0 and 128) in set 0? And it will be replacing 0 hence its a conflict miss right!!

---

@Star2020

Try to see the reason why miss has occured..It will clear a lot of doubts

0,128,256,128,0,128,256,128,1,129,257,129,1,129,257,129

0,128 are compulsory misses.now they are in set 0.

Now comes 256 which gets mapped to set 0.This is also a miss.

But it is also treated as compulsory miss instead of conflict miss. why??

Because even if the blocks 0,128 are not there in set 0, access to 256 is going to be a miss.

So the main reason of miss of 256 is not the competition between the blocks 0,128,256 for the place in set 0.It is due to the first time access to block and it is unavoidable.

So it is treated as compulsory miss

---

@Bikram sir when 5 comes again why will it not be treated as Capacity miss??

Answer 3

This is ms-paint edited solution

Comments

appreciated your efforts in making this:) thanks alot:)

Answer 4

There are a total of $160$ accesses to the cache blocks and these accesses will include compulsory misses, conflict misses and hits. Now, since there are 6 distinct blocks, so there will be 6 compulsory misses and if we look at the first iteration we have 6hits and after that iteration we are left with $256,128$ in set 0 and $257,129$ in set1, so from the next iteration onwards we'll have 6+2=8hits(+2 as 128 and 129 will be hits). So for 9 iterations, $9*8=72$ hits.

Total no of hits and compulsory misses= $6$(compulsory misses)+$6$(hits for 1st iteration)+$8*9$hits(8hits/iteration for 9 iterations)= $6+6+72=84$

$\therefore$ No of conflict misses $=160-84=76$

Comments

Nice Explanation @sukannya