cache - set associative

Cache Associative:

Full-Associative
If the replacement policy is free to choose any entry in the cache to hold the copy, the cache is called fully associative.
Direct-Mapped
At the other extreme, if each entry in main memory can go in just one place in the cache, the cache is direct mapped.
N-Way-Associative
Many caches implement a compromise in which each entry in main memory can go to any one of N places in the cache, and are described as N-way set associative.

If there are N places to which the replacement policy could have mapped a memory location, then to check if that location is in the cache, N cache entries must be searched. Checking more places takes
*PROs: caches with more associativity suffer fewer misses
*CONs: more power, chip area, and potentially time.


From direct mapped to 2-way, or from 2-way to 4-way, has about the same effect on hit rate as doubling the cache size.
Associativity increases beyond 4-way have much less effect on the hit rate


Example:
An 4K cache is often organized as a set of 256 lines(slots) of 16 bytes each.
Accordingly, a 4-way associative 4K cache has 64 sets, each set having 4 lines mapped.

A 32b address is divided into
[31:10] [9:4] [3:0]
tag set offset

For a given physical addr, first find the set with A[9:4] in cache.
Then search in all 4 slots to see if the tag A[31-10] matches the tag in the slot.