Question

Assume a 16-word cache works on the following repeating sequence of lw addresses in hexadecimal.
40
44

48
4C
70
74
78
7C
80
84
88
8C
90
94
98
9C
0
4
8
C
10
14
18
1C
20
Based on this particular sequence of memory accesses, answer the following questions.

5.A.) (5 POINTS) What will be the cache placement of this sequence for a direct mapped with S = 16, b = 1 word cache organization? Please show your work.

5.B.) (5 POINTS) What will be the cache placement of this sequence for a 2-way set associative cache with S = 8, b = 1 word cache organization? Please show your work.

5.C.) (5 POINTS) What will be the cache placement of this sequence for a direct mapped cache with S = 8, b = 2 words cache organization? Please show your work.

Answer 1

These are the addresses

40

44

48

4C

70

74

78

7C

80

84

88

8C

90

94

98

9C

0

4

8

C

10

14

18

1C

20

A) given that we have S=16 means 16 blocks in cache with one word size

so now divide the address

as block size of cache is equal to word size so block offset will be 0

now we have 16 blocks which require 4 bits for Block Index

as we have 8 bit address so the remaining 4 bits will be our tag

tag

4 bits

Block index

4 bits

now this will be done in this manner

i'm only showing the blocks of cache which got filled

initially our cache is empty

as in this we are having exact 4 bit for index so in hexadecimal the least significant digit will be our index and most significant will be our tag

initially the cache looks like

Block Index   tag
0  
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
as we can see in our question all the addresses are referenced with the index 0, 4, 8 , C

so in future i'm only mentioning these indexes and other will remain empty

1.) 40

address is 0100 0000

last 4 bit i.e. 0000 is our index which means index is 0 and tag is 4

now this is cache miss

similarly for 44, 48 , 4C

we will have miss as cache is initially empty

Block index   tag
0   4
4   4
8   4
C   4
Now next addresses are 70 , 74 , 78 , 7C

so they will go for index 0, 4, 8 ,C respectively but these indexes are already filled so compare the tag values as in these addresses tag value is 7 and already occupied blocks have tag value 4 so they all going to be cache miss and got replaces with their matching index

Block index   tag
0   7
4   7
8   7
C   7
Now next addresses are 80 , 84 , 88 , 8C

so they will go for index 0, 4, 8 ,C respectively but these indexes are already filled so compare the tag values as in these addresses tag value is 8 and already occupied blocks have tag value 7 so they all going to be cache miss and got replaces with their matching index

Block index   tag
0   8
4   8
8   8
C   8
Now next addresses are 90 , 94 , 98 , 9C

so they will go for index 0, 4, 8 ,C respectively but these indexes are already filled so compare the tag values as in these addresses tag value is 9 and already occupied blocks have tag value 8 so they all going to be cache miss and got replaces with their matching index

Block index   tag
0   9
4   9
8   9
C   9
Now next addresses are 0 , 4 , 8 , C

so they will go for index 0, 4, 8 ,C respectively but these indexes are already filled so compare the tag values as in these addresses tag value is 0 and already occupied blocks have tag value 9 so they all going to be cache miss and got replaces with their matching index

Block index   tag
0   0
4   0
8   0
C   0
Now next addresses are 10 , 14 , 18 , 1C

so they will go for index 0, 4, 8 ,C respectively but these indexes are already filled so compare the tag values as in these addresses tag value is 1 and already occupied blocks have tag value 0 so they all going to be cache miss and got replaces with their matching index

Block index   tag
0   1
4   1
8   1
C   1
last address is 20 which will go for index 0 and replace current block

so final cache will be

Block index   tag
0   2
4   1
8   1
C   1
2.) 2 way set associative cache with S=8 and block size=1

no. of sets = 8/2 = 4

so as block size is 1 so we require 0 bit for block offset

no. of sets are 4 so we require 2 bits for set index

and the remaining bits will go with the tag

tag

6 bits

set index

2 bits

so initially cache will be

Set index   tag in way1   tag in way2
0      
1      
2      
3      
now in our question last digit are

0, 4,8 , C which are in binary are : 0000 , 0100 , 1000 , 1100

last two bits are always 00 so this shows that we are going to access only one set

i.e. set 0

so for the first addresses

40 our set will look like

Set index   tag in way1   tag in way2
0   0100 00  
1      
2      
3      
the next two addresses are 44

set index is same but the tag value is different from current one so put in way

Set index   tag in way1   tag in way2
0   0100 00   0100 01
1      
2      
3      
now the next address is 48

which has set index 0

tag 0100 10

tag does not match with any so replace with way1

Set index   tag in way1   tag in way2
0   0100 10   0100 01
1      
2      
3      
for address 4C

tag is 0100 11

and set index is 0

replace with way2

Set index   tag in way1   tag in way2
0   0100 10   0100 11
1      
2      
3      
for the next addresses we will face same allocation just the tag values change in the first 4 bits

so the last two addresses will be 1C and 20

Set index   tag in way1   tag in way2
0   0010 00   0001 11
1      
2      
3      
5 C) Given that blocks are 8 and block size is 2 words

now evrey memory reference will bring 2 words

we have block size 2 word so Block offset will be 1 bit

8 blocks so 3 bits for the index which will range from 0 to 7

and the remaining 4 bits will be our tag

tag

4 bits

Block index

3 bits

Block offset

1 bit

now initially our cache will look like

Block index   Tag
0  
1  
2  
3  
4  
5  
6  
7  
now in our question we have the addresses ending with only 0 , 4, 8 , C

which have last bits as : 0000 , 0100 , 1000 , 1100

now look closely that after leaving the last bit which is always 0 which is our block offset

remaining 3 bits are 000 , 010 , 100 , 110

which is 0 ,2 , 4, 6

so in this these will be our indexes and other remains empty

now this question is exactly same as 5A

only difference is that 0 ,4 , 8 ,C

is replaced with 0 , 2, 4, 6 respectively

and the tags and the other procedure will be exactly same

so final table will be

Block index   Tag
0   2
1  
2   14
3  
4   18
5  
6   1C
7