13.7k views

Consider a $2-$way set associative cache with $256$ blocks and uses $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 _________ .

retagged | 13.7k views
0
@arjun sir.. no sir i dint mean that. Your keys are perfect. actually seeing all their erroneous keys made me afraid and confused a lot.
0
I don't seem to understand the question. Why is there going to be contention in the first place? The cache has 256 blocks of memory, so why is every memory access going to be be contending for the place in set0 rather than going for other empty sets of cache memory?
+6

Because of set associative cache particular set mapping done via block % set

0
Ok! Got it. Thanks ☺
+1
is compulsory can also be conflict miss?
+1
No it will still be counted as compulsory miss. compulsory miss occurs on first access always
0
@arjun Sir

If the question did not asked conflict misses and if it simply asks like "Find the no. of misses ?" .Then how the answer would change ?
0
i think 10 +8*9
+7

Source of image: "Computer Architectures: A Quantitative Approach'" book by D. A. Patterson and J. L. Hennessy $5th$ edition"

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

1$^{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 $set1 = 2$

Total number of conflict misses in $1$$^{st} iteration = 2+2=4 2$$^{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 $set1 = 4$

Total Number of conflict misses in $2$$^{nd} iteration = 4+4=8 Note that content of each set is same, before and after 2$$^{nd}$ iteration. Therefore each of the remaining iterations will also have $8$ conflict misses.

Therefore, overall conflict misses $= 4+8*9 = 76$
by Loyal (6.1k points)
edited by
0
@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.
+2
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?
+6
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.
0
@Suraj Sir and Arjun Sir, then too Thanks. I'll try to search some sources myself too. :)
0
@Suraj Sir, I've downloaded the said book. Is it worth referring for CO numerical ques?. And Thanks a tonnes again. :)
0
I read (did not solve numerical questions, so cant' comment) it and I found it very useful to clear basic concepts.
+7
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
+7

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.

+5
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
+2
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.

+1

@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

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

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

0
wired enough to know :O
0
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?
+2

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

+1

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

+3

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

0
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...
+2
$$\text {No. of line in cache memory }= \frac{\text{Total number of blocks in cache}}{\text{Associativity given}} \\= \frac{256 \ blocks}{2}=128 lines$$
+4
0
what would be the answer if asked max no. of conflict misses;
0
Can any one please clarify this

Can a set associatuva cache have a capacity miss?

If yes why....
0
No, it won't.
0

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)

+1
It has only one definition and that doesn't count the first access.
0
Thanks a lot bro
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.
by Veteran (434k points)
+3

@Arjun Sir isn't it 78?

(0,128,256,128,0,128,256,128,1,129,257,129,1,129,257,129) - For first iteration, the bolded ones are conflict misses ie 6 misses. Please confirm.

+19

(0,128,256,128,0,128,256,128,1,129,257,129,1,129,257,129)

These 2 are compulsory misses - conflict miss won't occur in a fully associative cache- but these two are fist accesses and hence not conflict misses. Many people take this as conflict as a block is thrown out affter colliding - but that is not a conflict miss- conflict miss happens when the thrown out block is again accessed.

0
Ok. Understood :(
0
@Arjun, I feel that number of blocks = 2* number of different sets. It means that all memory blocks would be mapped to 128 different sets. What do you say?
0
That happens if the block numbers are consecutive 128 numbers. (taking mod 128) as hash function rt?
+1
0
0
@arjun sir...are you absolutely sure with this answer and concept as many other institutes or websites are giving different answer.. i am confused sir.
+1

@debanjan18 Are you saying I must look at their keys and correct?

Just looked at ME keys and I'm happy that they have improved a lot. This question I never expected them to be correct, but https://gateoverflow.in/118597/gate2017-2-45  answer given by them is horrible- they assuming data and instruction caches as separate cache levels. So, why should we even care for their answer to this question assuming both are given by same person? But I must say in set 2, all their other answers are reasonable.

+3
And I take back my word about ME keys after seeing their set 1 keys...
0

Hi Sir,

I have seen your response but my doubt is still unclear.

As per question :

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

I agree 1st occurrence of 256 and 257 are compulsory misses but still they satisfy definition of conflict miss as well right ?(Since 0 and 128 are in 1st and 1 and 129 are in second so.)

I mean we can't say it like, miss does not occur due to the contention of multiple blocks for the same cache set

I mean we can't assert that it is not conflict miss right ?

It can be conflict as well as compulsory

Then why shouldn't we count them as well ?

+2
@Digvijay As per definition, if a block is removed due to another block and then when a future access happens and a miss results, then it is a conflict miss. This is what they meant by that definition - they did not put it like this to test the understanding of aspirants.
0
Sir,

contention of multiple block on same cache set with lru page replacement means.

cache set is already full.and u are going to insert another page.it will make a contention.
0
I still did not understand by contention in conflict miss,plz explain in more detail.
+20

yogesh sharma  and @_

contention of multiple block on same cache set with lru page replacement means.

Cache set is already full and you are going to insert another memory block. So here LRU replacement is used .That means new block is replaced by older one .

suppose memory blocks are 5 , 13 ,  29  and 5 .

There are 4 sets set 0, set 1 , set 2 and set 3 .

Total number of sets are 4 and blocks per set is 2 .

Set selection = ( memory block reference or block address) % (number of sets)

• 5 is mapped to set 1 ,  5%4 = 1  > it is compulsory miss ,

the cache memory scenario is at this moment  5 | __Blank__

• 13 is mapped to set 1  , 13%4 = 1  >  compulsory miss again ,

the cache memory scenario is at this moment 5 | 13

• 29 is mapped to   set 1 and 5 get replaced ,          29%4 = 1 > it is compulsory miss , the cache memory scenario is at this moment 13 | 29
• now again 5 comes and 5 is mapped to set 1 by replacing 13 , it is considered as Conflict Miss , as 5 come once previously so when next time 5 is mapped it is conflict miss .

Contention means conflict , here when 5 is mapped in same set it does not find previous block  5 , as that get replaced , so here in this example " multiple block " which is mapped again is 29 and 5 , that same cache set is set 1 .

the scenario is at this moment 29 | 5 .

So in my example, number of compulsory miss is 3 and number of conflict miss is 1 .

Hope now confusion gets clear .

0
thanks a lot sir.
0
0
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!!
+1

@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

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$
by Active (2.8k points)
edited by
0
Nice Explanation @sukannya

This is ms-paint edited solution

by Junior (679 points)
0
appreciated your efforts in making this:) thanks alot:)
+1 vote

There are 256 lines, so a memory block will numbered x will sit inside the cache in x mod 256th block. (Numbered 0 - 127)

But here, we got a 2-way set associative cache on our hands, so we have a total of 128 sets, and a memory block will sit inside x mod 128th set. (Numbered 0 - 127)

First iteration: 4 conflict misses.

Subsequent 9 iterations: 8 conflict misses each.

Total conflict misses = 76

This image shows the first iteration. When a block comes in for the first time, it's compulsory miss.

So, conflict misses = 4 (second appearances of 0, 256, 1 and 257)

For the remaining iterations, the first block of Set 0, and the first block of Set 1 would repeat identically. While 128 and 129 would be untouched. But this time, all misses are conflict misses, because it's not the first time the block is introduced in the cache.
So, conflict misses = 8 for nine iterations.

So, 4 + 9(8) = 76.

by Loyal (7.8k points)

Please refer to the solution below:

by (137 points)
edited