[Solved]: Direct Cache Mapping - Determine Tag Size

Problem Detail: 

In the following direct cache map, there is a list of 32-bit memory address references, given as word addresses. I gathered that the index size is 3 bit and there is no offset.

However, I used 4 bits to determine the tag--is this correct? When does the tag bits change? How many bits are typically used?

Address  Binary Address   Tag       Index   H/M  3        00000011        0000        011    Miss 180      10110100        1011        100    Miss 43       00101011        0010        011    Miss 2        00000010        0000        010    Miss 191      10111111        1011        111    Miss 88       01011000        0101        000    Miss 190      10111110        1011        110    Miss 14       00001110        0000        110    Miss 181      10110101        1011        101    Miss 44       00101100        0010        100    Miss 186      10111010        1011        010    Miss 253      11111101        1111        101    Miss 

Asked By : Nathan_Sharktek

Answered By : Aaron Hammond

The tag should be all bits not used for index/offset; thus, you should use the top 5 bits, not just the top 4. To see why, let's look at an example direct-map cache with 8 lines, where memory addresses are given as word addresses (so there are no byte offset bits) with a block size of 1 word (so there are no block offset bits either).

Let's say the cache has the following state

idx        tag          data 000        10000        insert data here (not important) 001        10010 010        11001 011        01010 100        10010 101        01000 110        01010 111        01010 

Now, I want to read the word at address 10011001. The index is then 001, and I compare the address's tag bits (the top 5; 10011) to the tag of the address of the data in the cache at index 001 (10010), and discover that they don't match. We have a cache-miss and replace the block at index 001 with the data we retrieve from memory and then update the tag of that entry.

If we had instead used only the top 4 bits for the tag, then we would do the tag comparison and think that the data in the cache was from the correct address (10011 and 10010 differ only by the bottom bit).

In general, a byte address is broken into the following pieces for the cache:

[        tag bits        ][   index bits   ][   block offset bits   ][   word offset bits   ] 

The word offset bits indicate which byte within a word we want; there are 2 (to indicate which of the 4 bytes in the word; because you're dealing with word addresses, we don't need these).

The block offset bits indicate which word within a block we want; say 4 words are read into a cache-line, then we'd need 2 bits to indicate which word within the block we want. There are log_2(cache_width) of these generally. Because your cache has only one word per line, we don't need these either.

The index bits indicate which line of the cache we should look at. There are log_2(lines) of these necessary. Your cache has 8 lines, so we'll need 3 bits for the index (which will be the bottom 3).

Finally, the other remaining bits in the address are used for the tag, to differentiate between blocks in the cache that otherwise have the same index bits. Because in our example (and your problem), the addresses are 8 bits, then the remaining 'unclaimed' top 5 bits are used.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33981