I need some help with this machine structures on memory/cache/bits/bytes questio
ID: 3843432 • Letter: I
Question
I need some help with this machine structures on memory/cache/bits/bytes question. Please, and thank you!
Q: Suppose we have a 1KB direct-mapped data cache with 4 byte blocks.
(a.) Show how a 32-bit memory address is divided into tag, index and offset. Show clearly how many bits are in each field.
(b.) How many total bits are there in this cache?
(c.) Consider this address trace:
0x807bfc4
0x807b1dc
0x907bfc4
0x806ce04
0x807b1e0
0x806ce0c
0x807b1e4
0x806ce0c
0x807bfc4
0x806ce14
For this cache, for each address in the above trace, show the tag, index and offset in binary. Indicate whether each reference is a hit or a miss. What is the miss rate?
Explanation / Answer
Given,
a)
1KB direct-mapped data cache with 4 byte blocks
Offset bits --> Right most bits of the address
Index bits --> Next to right most address bits
Tag bits --> Remaining left over bits (left part)
For 32 bit memory address à Tag + Index + Offset = 32 bits
There are 4 bytes in a cache block, the OFFSET field must contain 2 bits (2^2 = 4).
Cache size: 1 KB block and Block size: 32 B, So the INDEX field contains 8 bits (Since, 1KB/4B = (2^10)/(2^2) = 2^8 )
Now, remaining bits are TAG bits i.e, 22 bits (32-2-8 = 22)
|<--------22 bits------->|<---------8 bits-------->|<---------2 bits--------->|
Tag
Index
Offset
b) cache size?
Size of cache line: 2^offset bits = 2^2 = 4 bytes
Number of cache lines: 2^index bits = 2^8 = 256 lines
Total cache size: 4 256 = 1 KB = 8000 bits
c)
Address
Binary
Tag
Index
Offset
Hit/Miss
0x807bfc4
0000 1000 0000 0111 1011 1111 1100 0100
0000 1000 0000 0111 1011 11
11 1100 01
00
Miss
0x807b1dc
0000 1000
0000 0111 1011 0001 1101 1100
0000 1000
0000 0111 1011 00
01 1101 11
00
Miss
0x907bfc4
0000 1001 0000 0111 1011 1111 1100 0100
0000 1001 0000 0111 1011 11
11 1100 01
00
Miss
0x806ce04
0000 1000 0000 0110 1100 1110 0000 0100
0000 1000 0000 0110 1100 11
10 0000 01
00
Miss
0x807b1e0
0000 1000 0000 0111 1011 0001 1110 0000
0000 1000 0000 0111 1011 00
01 1110 00
00
Miss
0x806ce0c
0000 1000 0000 0110 1100 1110 0000 1100
0000 1000 0000 0110 1100 11
10 0000 11
00
Miss
0x807b1e4
0000 1000 0000 0111 1011 0001 1110 0100
0000 1000 0000 0111 1011 00
01 1110 01
00
Miss
0x806ce0c
0000 1000 0000 0110 1100 1110 0000 1100
0000 1000 0000 0110 1100 11
10 0000 11
00
Hit
0x807bfc4
0000 1000 0000 0111 1011 1111 1100 0100
0000 1000 0000 0111 1011 11
11 1100 01
00
Miss
0x806ce14
0000 1000 0000 0110 1100 1110 0001 0100
0000 1000 0000 0110 1100 11
10 0001 01
00
Miss
Miss rate = no. of misses / total no. of address = 9/10 = 0.9
Tag
Index
Offset