Question

Assume the cache can hold 64 kB. Data are transferred between main memory and the cache in blocks of 4 bytes each. This means that the

cache is organized as 16K=2^14 lines of 4 bytes each. The main memory consists of 16 MB, with each byte directly addressable by a 24-bit

address (2^24 =16M). Thus, for mapping purposes, we can consider main memory to consist of 4M blocks of 4 bytes each.

Please show illustrations too for all work.

Part 1) For the hexadecimal main memory addresses F6125Chex, when it is loaded to cache memory using direct mapping, where will it be

stored? Show the following information: Tag, Line number and word offset (show in binary, no conversion to hex is needed)

Part 2) If the next instruction is the content stored at 160004 hex in main memory and in cache memory, line number 0001 hex

has a tag 00 hex. Will we have a cache hit event or cache miss, why? (hint: check the line number and tag of 160004, if matches with the cache line and tag,

then cache hit; if catch line does not match, then cannot determine. Otherwise, cache miss)

Part 3) For the hexadecimal main memory addresses FFF666, show the following information: Tag, set and word values for a four-way set- associative cache

(show in binary, no conversion to hex is needed)

Answer 1

First some notes :

• As already mentioned, each cache block consists of 4 (= 2^2) words. Thus, lowest 2 bits of physical address determine the word-offset.
• Also, as already explained in the question, there are a total of 2^14 cache blocks (for direct-mapped cache, for first two questions). Thus, next 14 bits of physical address determine the cache line-number/block-number.
• The remaining bits of the physical address, constitute the tag.

Part 1)

0xF6125C :

• Address in binary = 1111 0110 0001 0010 0101 1100
• Lowest 2 bits = word offset = 00 = 0x00 = decimal 0
• Next 14 (bolded) bits = cache line (block) number = 00 0100 1001 0111 = 0x0497 = decimal 1175
• Remaining bits = tag = 1111 0110 = 0xF6 = decimal 246

Part 2)

0x160004

• Address in binary = 0001 0110 0000 0000 0000 0100
• Lowest 2 bits = word offset = 00 = 0x00 = decimal 0
• Next 14 (bolded) bits = cache line (block) number = 00 0000 0000 0001 = 0x0001 = decimal 1
• Remaining bits = tag = 0001 0110 = 0x16 = decimal 22

So, 0x160004 corresponds to cache-line 0x0001 with tag 0x16.

Currently, cache-line 0x0001 has tag 0x00 stored, so this is a collision case, and hence we have a cache-miss.

C)

In this case,

• Lowest 2 bits determine the word-offset, as usual.
• Also, now the number of sets become equal to (Total blocks / associativity factor) = 2^14 / 4 = 2^12. Thus, now, the next 12 bits will determine the set-number.
• Remaining bits form the tag.

(As a side-note, here in 4-way set-associative cache, each set can store a maximum of 4 tags).

So, for 0xFFF666,

• Address in binary = 1111 1111 1111 0110 0110 0110
• Lowest 2 bits = word offset = 10 = 0x02 = decimal 2
• Next 12 (bolded) bits = set number = 1101 1001 1001 = 0xD99 = decimal 3481
• Remaining bits = tag = 11 1111 1111 = 0x3FF = decimal 1023