Caches use various strategies for choosing which block to replace:
Direct-mapped cache:
When a miss occurs, the requested block can go in exactly one position, and the block must be replaced.
Set-associative cache:
There is a choice of where to place the requested block.
One scheme is least recently used (LRU), in which the block replaced is the one that has been unused for the longest time.
Fully associative cache:
All blocks are candidates for replacement.
Size of Tags versus Set Associativity
Increasing associativity requires more comparators and more tag bits per cache block.
Assuming a cache of 4096 blocks, a 4-word block size, and a 32-bit address, find the total number of sets and the total number of tag bits:
Direct-mapped cache
Since there are 16 (or 24) bytes per block, a 32-bit address yields 32-4=28 bits to be used for index and tag.
The index has 12 bits since log2(4096)=12; hence the total number is (28-12)×4096=65,536 or about 66 K tag bits.
Two-way set-associative cache
Each degree of associativity decreases the number of sets by a factor of 2 and thus decreases the number of bits used to index the cache by 1 and increases the number of bits in the tag by 1.
Thus,
For a two-way set-associative cache, there are 2048 sets, and the total number of tag bits is (28-11)×2×2048=34×2048=69,632 or about 70 K tag bits.
Four-way set-associative cache
For a four-way set-associative cache, the total number of sets is 1024, and the total number is (28-10)×4×1024=72×1024=73,728 or about 74 K tag bits.
Fully associative cache
There is only one set with 4096 blocks, and the tag is 28 bits, leading to 28×4096×1=114,688 or about 115 K tag bits.