= Fully associative cache
A <memory cache> allowing any <cache block> to occupy any resident slot. When full, its replacement policy chooses a victim from all resident <cache lines>. The examples in <temporal locality> and <spatial locality> use <LRU replacement>, so no additional placement restriction causes eviction.
The diagram enumerates every read of the fixed <memory access trace> under <memory cache>. Keep <cache slots> fixed: fill the lowest-numbered unused slot first, and subsequently reuse the victim's slot. Separately list recency from least recently used to most recently used. A <cache hit> refreshes that recency without moving the resident data to another <cache slot>.
\Image[/fully-associative-lru-read-trace.png]
{title=Every read, <cache hit> or <cache miss>, eviction, <cache slot> and recency state of the synthetic two-slot <fully associative cache> with <LRU replacement>}
After read 3, <cache block> 0 is older than <cache block> 2. Read 4 hits <cache block> 0, making <cache block> 2 older; read 5 must therefore evict <cache block> 2 to load <cache block> 1. Omitting recency updates on <cache hits> would choose the wrong victim. Read 6 immediately needs the evicted <cache block> 2, showing that <LRU replacement> uses past demand rather than knowledge of future demand.
With capacity four <cache slots> and the same <cache line> size, the same <memory access trace> has just its four <compulsory misses> and eight <cache hits>, since all four distinct <cache blocks> fit. Greater capacity helps this trace, but full associativity alone does not make <LRU replacement> optimal. Its attraction is freedom from placement restrictions; a hardware implementation must still identify a matching <cache tag> among eligible entries, and exact recency tracking adds work. <Memory part 2: CPU caches by Ulrich Drepper>{ref}
Back to article page
