set associative cache

architecture 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 rathethe r 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.

(2002-02-09)