Cache tag value

Question

In reference to the cache question at the following link : link

Question is : Using the the series of addresses below, show the hits and misses and final cache contents for a two-way set-associative cache with one-word blocks, 4-byte words, and a total size of 16 words. Assume FIFO replacement.

0, 4, 64, 0, 128, 32, 12, 96, 128, 64

My question is : Why is the tag value set to word address / 8 ?

Thanks.

Answer 1

Short explanation - If the cache holds 16 words total ( = 64 bytes cache, pretty small :), and it's 2-way set associative, then you have 8 sets that are directly mapped by the address. You don't need the set bits to be part of the tag because you've already used them to map to the correct set.

Assuming the access granularity is 1 byte, than you address has 2 LSB bits that map you inside a block (4 bytes), you need to ignore these when accessing the cache since you're reading the full block (the memory unit would then use these 2 bits to give you the exact bytes within the block according to the read size and alignment). So word address = real_address / 4

Now, since you have 8 sets, you use the next 3 bits to map to the correct set.

+--------------------------------------+----------------------+-------------------+
|          Tag (bits 5 and above)      |     Set (bits 2,3,4) | Offset (bits 0,1) |
+--------------------------------------+----------------------+-------------------+

That is, addr 0x0 would map to set 0, addr 0x4 (word addr 0x1) would always sit at set no. 1, no matter what. set 2 would have addr 0x8 (word addr 0x2), set 3 would have addr 0xC (word addr 0x3), ... and so on , until set 7 would be used for addr 0x1C (word addr 0x7).

The next address would simply wrap - addr 0x20 (word addr 0x8) would check bits 2..4 and see they're zeroed, so would map again to set 0, and so on. At this point comes the tag to distinguish between address 0x0, addr 0x20, addr 0x10000, or any other address that maps there (addr % 0x20 == 0, or word_addr % 8 == 0). Since you don't care about the offset inside the line here, and the set bits are already known when you decide to access a given set, the only thing missing that requires storage (aside from the data of course), are the bits above the set bits - this is required (and enough) to determines the line identity in a given set, and to know if a lookup hits or misses. These bits are addr / 0x20 (or addr >> 5), or word_addr / 8 ( = word_addr >> 3)

Note that this means that a tag alone is not enough to identify the line addr, you need tag and set bits to reconstruct that.