Consider a set-associative cache with fixed address width, total cache…

Concept

Set associativity is the number of cache lines, or ways, in each set. A cache address is divided into tag, set-index, and block-offset fields. With fixed address width and block size, the block-offset width is fixed.

For fixed cache capacity, increasing associativity reduces the number of sets. Fewer sets require fewer index bits, so more address bits become tag bits in every cache line.

Application

1. Let a cache have 256 lines. In a direct-mapped organization there are 256 sets, so 8 address bits select the set.

2. At 4-way associativity, the same 256 lines form 64 sets, so only 6 address bits select the set.

3. The index loses 2 bits; therefore the tag in each of the 256 lines gains 2 bits. Total tag storage gains 256 × 2 = 512 bits.

Cross-check

The number of cache lines stays fixed because cache capacity and block size are fixed. Valid and replacement metadata may add further overhead, but they do not reverse the increase in tag-bit storage.

Therefore, the total tag-storage size increases.