Associativity vs blocks per set in fixed size caches I am trying to understand the following claim:


  For a fixed size cache, each increase by a factor of two
  in associativity doubles the number of blocks per set
  (i.e., the number or ways) and halves the number of
  sets – decreases the size of the index by 1 bit and
  increases the size of the tag by 1 bit.



I am just wondering if someone can clear this up for me. For example, if there is a cache with 16 cachelines and it's 2-associative the number of blocks per set is 8, but if we increase by a factor of two associativity then the number of blocks per set decreases to 4.
The number of sets determines the size of the index, because the index tells you what set to refer to.  If you increase associativity by giving more blocks to each set then you run out of blocks sooner and so you can afford fewer sets.  If you have fewer sets then you have a smaller index.

If half the sets disappear then those addresses have to be handled by the remaining sets.  Because each set now has more addresses that it serves, it needs an extra bit of tag to distinguish them.