Caches are important to providing a high-performance memory hierarchy to process
ID: 2085132 • Letter: C
Question
Caches are important to providing a high-performance memory hierarchy to processors. Below is a list of 64-bit memory address references, given as word addresses. 0x03, 0xb4, 0x2b, 0x02, 0xbf, 0x58, 0xbe, 0x0e, 0xb5, 0x2c, 0xba, 0xfd For each of these references, identify the binary word address, the tag, and the index given a direct-mapped cache with 16 one-word blocks. Also list whether each reference is a hit or a miss, assuming the cache is initially empty. for each of these reference, identify the binary word address, the tag, the index, and the offset given a direct-mapped cache with two-word blocks and a total size of eight blocks. Also list if each reference is a hit or miss, assuming the cache is initially empty.Explanation / Answer
Given that we have 64-bit memory addressing system,
Answer:-5.2.1> since cache has 16 locations of one word each so INDEX will be of 4-bit and OFFSET will be of 0-bit since only one word is present in each line. Rest will be TAG bit. So for each given address we can write the address as-
0x03 = 0b0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0011 hence for this address INDEX = LSB 4-bit = 0011 and TAG = rest left bit = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000 in binary and cache is missed since initially this is not present in cache, cache is empty initially.
0xb4 = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_1011_0100 hence INDEX = 0100 and TAG = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_1011, cache miss.
0x2b = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0010_1011 hence INDEX = 1011 and TAG = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0010, cache miss.
0x02 = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0010 hence INDEX = 0010 and TAG = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000, cache miss.
0xbf = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_1011_1111 hence INDEX = 1111 and TAG = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_1011, cache miss.
0x58 = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0101_1000 hence INDEX = 1000 and TAG = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0101, cache miss.
0xbe = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_1011_1110 hence INDEX = 1110 and TAG = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_1011, cache miss.
0x0e = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_1110 hence INDEX = 1110 and TAG = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000, cache miss.
0xb5 = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_1011_0101 hence INDEX = 0101 and TAG = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_1011, cache miss.
0x2c = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0010_1100 hence INDEX = 1100 and TAG = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0010, cache miss.
0x2a = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0010_1010 hence INDEX = 1010 and TAG = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0010, cache miss.
0xfd = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_1111_1101 hence INDEX = 1101 and TAG = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_1111, cache miss.
So here all causes cache hit because all entry are new and initially was not present in cache. The way to define cache miss/hit is-
1. take INDEX bit and check if it is present in cache?
2. if yes, then search for TAG bit if found, then cache is hit otherwise miss.
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
Answer:-5.2.2> Now cache has 8-blocks and each block has 2-word so to select one from two word we need 1- bit for OFFSET (either 0 or 1) and for 8-blocks we need 3-bit for INDEX, rest bits are TAG bit. So we can write again as-
0x03 = 0b0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0011 hence last 1- bit is OFFSET, next three bits are for INDEX and rest are TAG bits. So OFFSET = 1, INDEX = 001 and TAG = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000 and cache is miss due to empty cache initially.
0xb4 = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_1011_0100 hece OFFSET = 0, INDEX = 010 and TAG = 0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_1011, cache miss.
In similar manner we can write for other addresses also.