Test by Bikram | Computer Organization and Architecture | Test 2 | Question: 15

Question

Consider a $2$ – way set associative cache memory with $4$ sets and total $8$ cache blocks $(0 – 7)$. Main memory has $64$ blocks $(0 - 63)$. If LRU policy is used for replacement and cache is initially empty then total number of conflict cache misses for the following sequence of memory block references is:

$0 \  5 \  9 \  13 \  7 \  0 \ 15 \  25$

• A. $2$
• B. $3$
• C. $0$
• D. $1$

Answer 1

Reference string: 0  5  9  13  7  0  15  25

0 - set 0 - Compulsory miss

5 - set 1 - Compulsory miss

9 - set 1 - Compulsory miss (set 1 now full)

13 - set 1 - Compulsory miss (5 replaced, but this is not conflict miss; if 5 is again accessed then that access causes conflict miss by its definition. Remember that conflict miss is something which can be avoided if the cache is fully associative and hence it can never happen with compulsory miss)

7 - set 3 - Compulsory miss

0 - set 0 - Hit

15 - set 3 - Compulsory miss

25 - set 1 - Compulsory miss - 9 replaced. Again this is not a conflict miss. 

So, number of conflict misses = 0. 

Ref GATE question. 

Comments

@bikram sir

capacity misses is also 0 here rt na?

---

@hem chandra

yes , capacity miss is 0 here .

All main memory blocks are mapped to all the sets e.g. set 0 , set 1 and set 3 so cache is not full .

that gives 0 Capacity miss .

---

@bikram sir can u explain with  an example of capacity miss?

my confusion is when will cache memory be full because each time  a new block comes and if respective set is full it uses replacemnt so when should we consider it as full ?

Answer 2

Sir can you describe all other misses?

Compulsary misses are 8 rt?

Comments

@hem chandra joshi

 If the cache CANNOT contain all the blocks needed during the execution of a program,means when cache must be full, Capacity Misses will occur . Means when all cache lines are filled capacity miss is happen. 

Here in this question ,

No capacity miss happen .  All main memory blocks are mapped to all the sets e.g. set 0 , set 1 and set 3 so cache is not full . 

0 Capacity miss .

-------------

For your 2nd question,

And , 0% 4 = 0  it is a hit because it is 2 way set associative cache . Number of blocks per set is 2 .

0      0%4  , 1st compulsory miss  for 1st block

-----

0      0%4  , when 0 comes to set 0 second time it is considered as a hit , as 0 is found again in second time in set 0 .

---

https://gateoverflow.in/118745/gate2017-1-51#

sir c this ...#compulsary misses.

---

hem chandra joshi  

yes , here number of compulsory misses are 7 , and one cache hit in set 0 .

Answer 3

2 - way set associative cache means number of Blocks per set is 2 . And there are total 4 sets .

memory block references is : 0  5  9  13  7  0  15  25 

conflict misses occur due to the contention of multiple blocks for the same cache set .

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

0% 4 = set 0    
5% 4 = set  1
9% 4 = set 1    
13% 4 = set 1  now 5 get replaced 
7% 4 = set 3
0% 4 = set 0     cache hit
15% 4 = set  3
25% 4 = set 1  now 9 get replaced

So total number of conflict misses are 0 , 7 compulsory misses .

Comments

hem chandra joshi  

It is set associative cache with no of blocks per set is 2 , here number of conflict miss comes as 0 .

Thanks Arjun . I understand  it .

when first 5 goes to set 1 and then 9 goes to set 1 bcoz 2 way set associative cache so 2 blocks are full now. Next 13 comes and mapped to set 1 so as it is first time 13 is mapped to cache it is compulsory miss , 5 get replaced due to LRu and no conflict miss happen.

again later 25 comes and mapped to set 1 , now this time 9 get replaced due to LRU , so it is again compulsory miss and total number of conflict misses are 0 .

---

sir my question is that 0 is already in cache so now again it is mapped will it not be consider as hit?

---

yes , it is consider as a hit in set 0 .

Answer 4

First miss of any element is a compulsory miss (in demand paging/caching).

Given: 0 5 9 13 7 0 15 25

Only 0 is repeated twice, so maximum conflict misses can be 1 (ie just for the element 0). For rest others, it'll be just the one compulsory miss.

If you make the cache, and trace out this reference string, 0 is a hit the second time. Hence, there are no conflict misses.

Option C