The Gateway to Computer Science Excellence
+3 votes
330 views
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
in CO and Architecture by Boss (10.9k points) | 330 views
0
I think the last 4 bits will be offset and the next 1 bit will be set no (as it is given byte addressable
0

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

+1
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
0

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

2 Answers

+3 votes

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)

by Boss (10.9k points)
0
ya...VS u r correct....

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

0-15 B1

16-31-B2....
0
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....
0 votes

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

by Loyal (8.2k points)
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
50,737 questions
57,395 answers
198,595 comments
105,446 users