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.
2 Answers 2
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.)
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