structure of cache when CPU uses words smaller than the main memory

Question

As the title says, i have the following excersice:

An associative mapping cache with four lines in each set, can store in each line two words of 16 bits each. It can store 4K words, that they have length 32bits from Main memory. The CPU is 16 bits and the address that he produces is 24 bits length. So the solution is shown below:

I can understand why set has 10 bits, or why tag is 12, but I can't figure out the word select and byte select signals. Also how can this cache store two words as the image shows (Word 0 and Word 1), when the line size is 16 bit, but the word size from Main Memory is 32 bits.

Answer 1

So the question is a bit confusing because there are two types of words: CPU words that are 16 bits, and memory words that are 32 bits. This can happen when the CPU registers have 16 bits but the memory chip is organized in such a way that the minimum accessible unit (a word) is 32-bit. The cache will always read/write multiple of memory words, in this case one word per line. Since the CPU word is 16 bits, each memory word (32 bits) actually holds two CPU words, those are the Word 0 and Word 1 on the picture.

Now, when the CPU accesses memory, the cache will find which lines corresponds to the request. This line contains 32-bit, but maybe the CPU only wanted 8 bits, so we have to extract those 8 bits from the line. In this example, bit 1 will select between Word 0 and Word 1 (which are CPU words). The resulting word still has 16 bit, so we use bit 0 to select between the low or high 8 bits of that word.

If you still find confusing, forgot about Word 0 and Word 1 and just imagine that each cache line stores 4 bytes (=32 bits). Now to select one byte in 4, you need to discriminate based on the lower 2 bits of the address. If the cache had 8 bytes per line, then you would use 3 bits. And so on. In general, the format of an address is

| Tag | Index | Offset |

where Index selects the line (there are many way of doing so) and Offset selects the byte within the Line.

Answer 2

If the memory is byte addressable, each memory address represents a byte in the memory. If the CPU is operating at 2 byte granularity (16 bits), all the addresses you'll see are 0, 2, 4, 8 and so on. If you get the hex representation of these addresses, you'll see that the last bit is always zero. This last bit represents the byte within the 16 bit data, hence can be called byte select. Now the cache lines are of 2 word lengths, accommodating 4 bytes. Therefore all the cache line addresses you'll see are 0, 4, 8, 12, and so on. Again if you check the hex representation of these, you'll notice that last two bits are always zero. We have already established that the last bit gives us the byte within a word. And the next bit gives the word within a cache line, hence called word select.