5

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.

Greg Hewgill
  • 951,095
  • 183
  • 1,149
  • 1,285
KWJ2104
  • 1,959
  • 6
  • 38
  • 53

2 Answers2

3

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.

DON'TPANIC
  • 191
  • 1
  • 5
  • What's the byte offset for then? – KWJ2104 Apr 30 '12 at 06:58
  • the byte offset is how large one block is. For example, using the same reference as above, assuming C1 has {00 00 0010} loaded in block {00}, this block contains memory {00 00 0000} to {00 00 1111}. However, if you try to look up {01 00 0010}, it will be a miss because the tag is different. (Also I am assuming this is a 1-way set-associative mapping) – DON'TPANIC May 01 '12 at 15:26
1

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)

Bryce
  • 11
  • 1
  • Generally caches load an entire block on a miss not just the requested bytes. (Some caches use sectoring, providing more than one valid bit per block, but no mainstream processor provides a valid bit per byte or even per 4-byte chunk. In addition, with current DRAM the minimum burst length is 4—using burst chop, which can reduce performance—, so a 64-bit wide interface gives a *minimum* 32-byte transfer.) –  Apr 15 '14 at 14:25
  • @PaulA.Clayton Can you take a look at this caching question as well? http://stackoverflow.com/questions/30555623/how-many-bits-are-in-the-address-field-for-a-directly-mapped-cache – committedandroider May 31 '15 at 17:06