Have a few questions about caches and cache hits/misses

Question

This is a homework problem, but the homework was already due and we were already given the answers, I just have no idea how they actually came up with these answers.

It relates to caches, and I'm just getting a lot of concepts mixed up.

Here is the question:

For a direct-mapped cache design with a 32-bit address, the following bits of the address are used to access the cache.

From my understanding, the index bits determine which block in the cache a particular location in memory is mapped to. The lowest log(base2) bits off the address determine the cache block, and here there are 5 index bits, so I know that there will be a total of 2^5 blocks in the cache, or 32.

What is the cache block size (in words)?

According to the answers given to us, the cache block size is 8. According to some notes given to us by our TA, the block size is 2^(# of offset bits), which in this case would be 5. However, that gives me as an answer 32, so I do not know where the 8 is coming from. Furthermore, nowhere in this book is the term "offset bits" defined, so can somebody tell me exactly what this means?

**What I'm thinking here is that since the same memory address is never referenced twice, there should be NO hits, since the cache will never already have the data it is looking for within the cache. However, according to the answers, the hit ratio should be .25, so once again I guess I'm not understanding what is going. Finally, for the last question it says the answer is as follows:

<000001, 0001, mem[1024]>

<000001, 0011, mem[16]>

<001011, 0000, mem[176]>

<001000, 0010, mem[2176]>

<001110, 0000, mem[224]>

<001010, 0000, mem[160]>

Which contains some memory addresses (176, 2176) that weren't even in the original question, so by this point I completely lost about everything. Can somebody help clear some of these things up for me?**

Answer 1

In the example the cache block size is 32 bytes, i.e., byte-addressing is being used; with four-byte words, this is 8 words.

Since an entire block is loaded into cache on a miss and the block size is 32 bytes, to get the index one first divides the address by 32 to find the block number in memory. The block number modulo 32 (5-bit index) is the index. The block number divided by 32 is the tag. The trace would look like this:

   0  miss  <00000, 0000, mem[0..31]>
   4  hit   <00000, 0000, mem[0..31]>
  16  hit   <00000, 0000, mem[0..31]>
 132  miss  <00100, 0000, mem[128..159]>
 232  miss  <00111, 0000, mem[224..255]>
 160  miss  <00101, 0000, mem[160..191]>
1024  miss  <00000, 0001, mem[1024..1055]>
  30  miss  <00000, 0000, mem[0..31]>
 140  hit   <00100, 0000, mem[128..159]>
3100  miss  <00000, 0011, mem[3072..3103]>
 180  hit   <00101, 0000, mem[160..191]>
2180  miss  <00100, 0010, mem[2176..2207]>

As you can see there are four hits out of 12 accesses, so the hit rate should be 33%. (It looks like the provider of the answer thought there were 16 accesses.)

Side comment: Since this is starting from an empty cache, there is only one conflict miss (the mem[30] access) and the remaining seven misses are compulsory (first access) misses. However, if this was the body of a loop, in each iteration after the first there would be four conflict misses at index 00000 (address 0, 1024, 30, 3100), two conflict misses at 00100 (addresses 132, 2180), and six hits (addresses 4, 16, 140 are hits whose cache blocks have been reloaded in each iteration, corresponding to conflict misses; addresses 232, 160, 180 are hits whose cache blocks were loaded in the first iteration and not evicted).

Running through this trace, one can find that at the end the following blocks would be valid (being the last accessed for their index):

<00000, 0011, mem[3072..3103]>
<00100, 0010, mem[2176..2207]>
<00101, 0000, mem[160..191]>
<00111, 0000, mem[224..255]>

Note how this differs from the given answer which is clearly wrong because with 32-byte blocks, no block would start at mem[16] and 1024 divided by 32 gives a block number (in memory) of 32, 32 modulo 32 is 0 (not 1) for the index.

Incidentally, providing the byte range cached in the block is probably more helpful than just providing the starting address of the block.