Associative Cache: A type of CACHE designed to solve the problem of cache CONTENTION that plagues the DIRECT MAPPED CACHE. In a fully associative cache, a data block from any memory address may be stored into any CACHE LINE, and the whole address is used as the cache TAG: hence, when looking for a match, all the tags must be compared simultaneously with any requested address, which demands expensive extra hardware. However, contention is avoided completely, as no block need ever be flushed unless the whole cache is full, and then the least recently used may be chosen.
A set-associative cache is a compromise solution in which the cache lines are divided into sets, and the middle bits of its address determine which set a block will be stored in: within each set the cache remains fully associative. A cache that has two lines per set is called two-way set-associative and requires only two tag comparisons per access, which reduces the extra hardware required. A DIRECT MAPPED CACHE can bethought of as being one-way set associative, while a fully associative cache is n-way associative where n is the total number of cache lines. Finding the right balance between associativity and total cache capacity for a particular processor is a fine art- various current cpus employ 2 way, 4-way and 8-way designs.