Direct Mapped Cache Hit/Miss

Question

My apologies if this is the wrong stackexchange for this; it just seemed like the closest one to a place that could be of help for computer architecture. For a homework problem in computer systems I was asked:

Consider three direct mapped caches X, Y, and Z each interpreting an
8-bit address slightly differently according to the {tag:setIdx:byteOffset}
format specified. For each address in the reference stream, indicate whether the
access will hit (H) or miss (M) in each cache.

                  C1       C2     C3
Address Formats: {2:2:4} {2:3:3} {2:4:2}

Address References in Binary: 00000010, 00000100...

I'm supposed to say whether each of the address references will result in a hit or miss but I don't know where to begin.

For formats, I thought that tag meant the tag of the data in a block of cache, setIdx meant the amount of bits given to represent the different blocks in a cache, and offset was the particular byte within a block that you can choose from.

I feel like I don't understand what a hit or miss is. I thought there were 3 types: compulsory, capacity, and conflict. How would I know which is a compulsory miss if I don't know what is already in the cache? How can I tell the capacity of the cache given the tag formats?

Thanks for any hints or tips.

Answer 1

Take C1 for example, it has 2 bits for setIdx, and 4 bits for byteOffset.

So this cache will have 2^2 = 4 blocks (00, 01, 10, and 11), and each block will have 2^4 = 16 bytes.

The address reference can now be split into C1 format: {00 00 0010}

Assuming cache is empty by default, the first lookup will result in a miss. However, cache will now have the block "00" loaded with tag "00".

The next reference {00 00 0100} will look up block "00", it sees that the tag is also "00", we have a hit.

Answer 2

I don't think that you would have a hit. Even though the address 00 00 0100 would look up the same block, it would be looking up a different address in memory. In a direct mapped cache hits are only cause by trying to access the same address in memory in the same block in consecutive instructions. The address in memory is given by the byte address and not the block number. A direct mapped cache will replace the contents of a block so long as it isn't trying to access the same address in the block. If 00 00 0100 were to precede another 00 00 0100 then there would be a hit in a direct mapped cache.

In an associated cache, the memory address in given by the block number and not the byte address so a hit would be generated here.

The block number is given by floor(Byte address/Bytes per block) mod (number of blocks)