Cache comparator usage

Question

Referring to the photo below, in direct-mapping cache design, why we need a comparator to compare between the tag in the address and the tag in the cache?

Isn't a valid bit enough?

source:https://courses.cs.washington.edu/courses/cse378/07au/lectures/L16-More-Cache-Organizations.pdf

• user16324: A valid bit is not enough. It tells you that a valid cache line has been loaded : it doesn't tell you the cache line YOU NEED NOW is loaded. There might be valid data from an address with different tag bits.

Answer 1

No, because you have less cache than memory.

If you have, let's say, 4GB of memory and 4MB of cache with 64-byte cache lines, then you have addresses that look like this:

1111 1111 1111 1111 1111 1111 1111 1111 <- example memory address
 11 1111 1111 1111 11 <- example cache index

It's direct-mapped which means each memory address can only be cached in one specific line. Since the cache lines are 64 bytes, the bottom 6 bits are irrelevant (they just identify which byte in the cache line, but it's the same cache line). And since there are only 4MB of cache, they repeat every 4MB. The memory address "64" goes to the exact same cache line (the second one) as the memory address "4MB plus 64", "8MB plus 64", and so on. (If they didn't have to go to the same cache line, then it wouldn't be a direct-mapped cache!)

So how does the cache remember whether it's currently storing the data for address 4MB+64, or address 20MB+64? Well that's what the tag is for. The tag is all the extra bits that the cache can't figure out by itself. Addresses with different cache indexes go to different cache lines, so that doesn't need to be part of the tag. But the tag needs to remember which address that could go into the same cache line, is currently in that cache line.

0000 0000 0100 0000 0000 0000 0100 0000 <- example memory address (4MB+64)
 00 0000 0000 0000 01 <- cache index (1)
 00 0000 <- which byte in the cache line (0)
0000 0000 01 <- tag (1)

If the cache wants to find memory address 4MB+64, it looks at cache index 1, and checks the current tag. If the tag is 1, then it's found it. If the tag is 2, then the cache line is actually storing the data for address 8MB+64, not 4MB+64. So the CPU has to save the cached data to address 8MB+64 in main memory, read the data for 4MB+64 and put that data in the cache (and update the tag).