#Conflict Misses

Question

A byte addressable computer has a small data cache capable of holding 16 32-bit words. Each cache block consist of four 32 bits words. For the following sequence of main memory addresses (in hexadecimal). The conflict miss if 2-way set associative LRU cache is used is ________.
100, 108, 114, 1C7, 128, 1B5, 100, 108, 1C7

Comments

I think the last 4 bits will be offset and the next 1 bit will be set no (as it is given byte addressable

---

CM=16 words

BS=4 words

#lines = 16/4=4 

# sets =4/2=2.

each address is byte addressable ... but mapping is done on block so we have to identify the the bytes lie in which block.

Block no=8 b

Block offset=4b

100=  0001 0000 0000   (16th block)

108=  0001 0000 1000     (16th block)

114=  0001 0001 0100     (17th block)

likewise if we do we get a sequence in terms of block : 16 17 28 18 27 16 28.

on mapping these 

no of conflict miss=2

---

Yes lines = 16/4 = 4

and set number = 2

Block offset = 2 bits (Because each block has 4 words)

set number bit = 1 (Because we have 2 sets)

hence last 3 bits are imp.

100 = ...000

108 = ...000

114 = ...100

1C7 = ...111

128 = ...000

1B5 = ...001

100 = ...000

108 = ...000

1C7 = ...111

Now if we try to allocate lines in Cache then

there will be 2 conflict misses and 6 compulsory miss

---

@  Ashwin Kulkarni  i did a mistake ... corrected now :)

Answer 1

Since, Memory is Byte Addressable.

1 word = 32 bit = 4 B

Block Size= 4 words=16B

CM size=16 words=16*4=64B

#CM lines = 64B/16B = 4

#CM sets = 4/2 = 2

Physical Addr (12 bit): ( Tag+SO = Block Number)

Tag	SO	WO
7 bit	1 bit	4 bit

CM : 

Set 0	16,18,28	28 ,16
Set 1	17	27

100 (Block 16) :   0001 000|0 |0000 ----> Compulsory Miss

108 (Block 16) :   0001 000|0 |1000 ----> Hit

114 (Block 17) :   0001 000|1 |0100 ----> Compulsory Miss

1C7 (Block 28) :   0001 110|0 |0111 ----> Compulsory Miss

128 (Block 18) :   0001 001|0 |1000 ----> Compulsory Miss   (LRU : Replace Block 16)

1B5 (Block 27) :   0001 101|1 |0101 ----> Compulsory Miss

100 (Block 16) :   0001 000|0 |0000 ----> Conflict Miss   (LRU : Replace Block 28)

108 (Block 16) :   0001 000|0 |1000 ----> Hit

1C7 (Block 28) :   0001 110|0 |0111 ----> Conflict Miss   (LRU : Replace Block 18)

Hence , #Conflict Misses = 2 (ANS)

Comments

ya...VS u r correct....

i misssed the point that ....a block will hold 16 byte...means ...

0-15 B1

16-31-B2....

---

i think that their is no conflict miss in this as  both of these 100 and 1C7 are capacity miss, since all the locations are already full....

Answer 2

here ..

cache cpacity=16 word or 64byte

block size= 4 word or 16byte

number of cahe lines would be:- 16/4=4

number of set would be....4/2=2

now by given address it is clear that address contain 12bits....means size of MM is 2¹²...byte

tag set offset

7     1     4...

therefor..we will see only 5th bit....

100 = ...0.0000(set 0 contain :- 100)

108 = ...0.1000(set0 contain : 100,108)

114 = ...1.0100(set1 contin:- 114)

1C7 = ....0.0111(set0:-1c7,108)remove 100

128 = ...0.1000(set 0:-1C7,128)remove 108

1B5 = ...1.0101(set1:-114,1B5)

100 = ...0.0000(set0-128,100)Conflict miss

108 = ....0.1000(set0-108,100)Conflict miss

1C7 = ...0.0111(set0-1C7,100)Conflcit miss