Cache Direct Map (Index, tag, hit/miss)

Question

Alright, I thought I understood this concept but now I am confused. I looked up similar problems and their solutions to practice, and that's what threw me off. The question is a homework problem which says:

Below is a list of 32-bit memory address references, given as word addresses.

3, 180, 43, 2, 191, 88, 190, 14, 181, 44, 186, 253

a) For each of these references, identify the binary address, the tag, and the index given a direct-mapped cache with 16 one-word blocks. Also list if each reference is a hit or a miss, assuming the cache is initially empty.

b) For each of these references, identify the binary address, the tag, and the index given a direct-mapped cache with two-word blocks and a total size of 8 blocks. Also list if each reference is a hit or a miss, assuming the cache is initially empty.

(How do I know how many bits the tag and index are supposed to have? Also, it is a miss unless both the tag and the index match, right? Or is it just if the index matches? I'm obviously extremely confused but I really do want to understand!)

My answer for a) :

Memory        Binary          tag          index         hit/miss
3             00000011       0000          0011          miss
180           10110100       0010          0000          miss
43            00101011       0010          0011          miss
2             00000010       0000          0010          miss
191           10111111       1011          1111          miss
88            01011000       0101          1000          miss
190           10111110       1011          1110          miss
14            00001110       0000          1110          miss
181           10101101       1010          1101          miss
44            00101100       0010          1100          miss
186           10111010       1011          1010          miss
253           11111101       1111          1101          miss

b)I'm not sure how to figure this out, but when I looked it up, people were saying the index should be left shifted one bit so that's what I got (I'd like to understand why)

3             00000011       0000          001          miss
180           10110100       0010          000          miss
43            00101011       0010          001          miss
2             00000010       0000          001          hit
191           10111111       1011          111          miss
88            01011000       0101          100          miss
190           10111110       1011          111          hit
14            00001110       0000          111          miss
181           10101101       1010          110          miss
44            00101100       0010          110          miss
186           10111010       1011          101          miss
253           11111101       1111          110          miss

As always, thank you so much for your help.

Answer 1

For a direct mapped cache the general rule is: first figure out the bits of the offset (the right-most bits of the address), then figure out the bits of the index (the next-to right-most address bits), and then the tag is everything left over (on the left side).

One way to think of a direct mapped cache is as a table with rows and columns. The index tells you what row to look at, then you compare the tag for that row, and if it matches, the offset tells you which column to use. (Note that the order you use the parts: index/tag/offset, is different than the order in which you figure out which bits are which: offset/index/tag.)

So in part (a) The block size is 1 word, so you need 0 offset bits (because $2^0=1$). You have 16 blocks, so you need 4 index bits to give 16 different indices (because $2^4=16$). That leaves you with the remaining 28 bits for the tag. You seem to have gotten this mostly right (except for the rows for "180" and "43" where you seem to have missed a few bits, and the row for "181" where you interchanged some bits when converting to binary, I think). You are correct that everything is a miss.

For part (b) The block size is 2 words, so you need 1 offset bit (because $2^1 = 2$). You have 8 blocks, so you need 3 index bits to give 8 different row indices (because $2^3=8$). That leaves you with the remaining 28 bits for the tag. Again you got it mostly right except for the rows for "180" and "43" and "181". (Which then will change some of the hits and misses.)

Answer 2

The accepted answer clear most of the doubt, and I wanna make a note here (for comp org student).

• The addresses are not byte addressable (as mentioned in the question, they are word addresses). The equation (with +2 offset) mentioned in the textbook should not be used directly in this question.
• remind that offset does not need to be matched for a HIT to be happened since cache will be filled by block (or 2 words in part b) each time a MISS happened. check this out