Cache is close to CPU and faster than main memory. But at the same time is smaller than main memory. The cache organization is about mapping data in memory to a location in cache.
A Simple Solution:
One way to go about this mapping is to consider last few bits of long memory address to find small cache address, and place them at the found address.
Problems With Simple Solution:
The problem with this approach is, we loose the information about high order bits and have no way to find out the lower order bits belong to which higher order bits.
What is a Cache Block?
Since programs have Spatial Locality (Once a location is retrieved, it is highly probable that the nearby locations would be retrieved in near future). So a cache is organized in the form of blocks. Typical cache block sizes are 32 bytes or 64 bytes.
The above arrangement is Direct Mapped Cache and it has following problem
We have discussed above that last few bits of memory addresses are being used to address in cache and remaining bits are stored as tag. Now imagine that cache is very small and addresses of 2 bits. Suppose we use the last two bits of main memory address to decide the cache (as shown in below diagram). So if a program accesses 2, 6, 2, 6, 2, …, every access would cause a hit as 2 and 6 have to be stored in same location in cache.
Solution to above problem – Associativity
What if we could store data at any place in cache, the above problem won’t be there? That would slow down cache, so we do something in between.
We will soon be discussing more details of cache organization.