A compromise between a
direct mapped cache
and a
fully associative cache where each address is mapped
to a certain set of cache locations. The address space is
divided into blocks of 2^m bytes (the
cache line size),
discarding the bottom m address bits. An "n-way set
associative" cache with S sets has n cache locations in each
set. Block b is mapped to set "b mod S" and may be stored in
any of the n locations in that set with its upper address bits
as a tag. To determine whether block b is in the cache, set
"b mod S" is searched associatively for the tag.
A direct mapped cache could be described as "one-way set
associative", i.e. one location in each set whereas a fully
associative cache is N-way associative (where N is the total
number of blocks in the cache). Performance studies have
shown that it is generally more effective to increase the
number of entries rather than associativity and that 2- to
16-way set associative caches perform almost as well as fully
associative caches at little extra cost over direct mapping.