Direct-Mapped vs Set-Associative vs Fully Associative Cache

A cache must decide where each block of memory may be stored. In a direct-mapped cache each block has exactly one possible line, which is simple and fast but suffers conflicts when two blocks share a line. In a fully associative cache a block can go anywhere, which avoids conflicts but needs a comparison against every line. A set-associative cache is the compromise: a block can go in any of a few ways within one set. Most CPU caches are set-associative.

AspectDirect-mappedSet-associativeFully associative
Where a block can goExactly one line, chosen by the index bitsAny of the ways (for example 4 or 8) in one setAny line in the cache
Tag comparisons per accessOneOne per way (for example 8)All lines at once, in parallel
Hit timeFastestSlightly slowerSlowest
Hardware cost and powerLowestModerateHighest: a comparator for every line
Conflict missesMost frequentReduced as the number of ways growsNone: only compulsory and capacity misses remain
Replacement policyNot needed: only one choiceChosen within the set (LRU or approximations)Chosen among all lines
Typical usesSmall, simple caches and some microcontrollersL1, L2 and L3 caches in most CPUs, usually 4 to 16 waysSmall structures such as TLBs and victim caches

Figures are typical orders of magnitude and vary by process generation and product.

When to use which

Direct-mapped
When simplicity, low power and speed matter more than hit rate.
Set-associative
The practical choice for most caches, since a few ways remove most conflict misses at modest cost.
Fully associative
For very small structures where the hit rate is critical and the comparison cost is affordable.

FAQ

What is a conflict miss?

A miss that happens because two blocks map to the same place even though other cache lines are free. Direct-mapped caches suffer most, and fully associative caches have none.

How many tags does an 8-way cache compare per access?

Eight, one for each way of the selected set.

Why are most CPU caches set-associative?

A few ways remove most conflict misses at a modest cost, while a fully associative cache needs a comparator for every line.

Where is a fully associative cache used?

In small structures such as TLBs and victim caches, where the hit rate matters most and the comparison cost is affordable.

Check your understanding

For a direct-mapped cache with 32-bit addresses, 32 KB capacity and 64-byte lines, how many tag bits are there?

  1. A15 bits
  2. B19 bits
  3. C17 bits
Show answer and explanation

Answer: C. 17 bits

A 64-byte line = 2⁶, so the offset is 6 bits. The number of lines is 32 KB ÷ 64 B = 32,768 ÷ 64 = 512 = 2⁹, and in a direct-mapped cache each line is its own set, so the index is 9 bits. The rest is the tag: 32 − 9 − 6 = 17 bits. 19 bits would apply to a 4-way set-associative cache, where the index shrinks by 2 bits, not to a direct-mapped one.

How many sets does a 4-way set-associative cache with 32-bit addresses, 32 KB capacity and 64-byte lines have?

  1. A128
  2. B512
  3. C32
Show answer and explanation

Answer: A. 128

The number of lines is 32 KB ÷ 64 B = 512. A 4-way cache holds four lines per set, so there are 512 ÷ 4 = 128 = 2⁷ sets, giving a 7-bit index and a 32 − 7 − 6 = 19-bit tag. 512 is the line count itself, which equals the set count only when direct-mapped. Raising associativity reduces the number of sets, which adds tag bits and comparators. 32 comes from wrongly dividing the 64-byte line size by the number of ways.

In a fully associative cache, how many address bits are used for the index (the part that selects a set)?

  1. A6 bits, determined by the line size
  2. BAs many bits as there are lines
  3. C0 bits
Show answer and explanation

Answer: C. 0 bits

In a fully associative cache any data can go anywhere, so the whole cache is a single set. No set needs to be selected, so the index is 0 bits; the address splits into just offset and tag, and every access compares against all tags. That requires many comparators, so it does not suit large caches and is used for small structures such as TLBs. The line size determines the offset width, not the index.

  1. In a direct-mapped cache, elements of two arrays map to the same cache location and evict each other on every alternating access. How is this miss classified?
  2. What changes when a cache is switched from direct-mapped to set-associative?
  3. In an 8-way set-associative cache, how many tags are compared in parallel on each access?

Practice Memory Hierarchy questions

Key terms explained

Direct-mapped cache
A cache organization in which each address can be placed in exactly one location. It is simple with short hit time, but prone to conflict misses when addresses compete for the same slot.
Set-associative cache
A cache organization in which data can go in any of several locations (ways) within the one set selected by the address. An n-way cache compares n tags in parallel on each access.
Fully associative cache
A cache organization in which any data can be placed in any location. It has no conflict misses but must compare against every tag, so it suits small structures such as TLBs rather than large caches.
Cache line
The unit in which data moves between a cache and the level below, also called a cache block. Many CPUs use 64 bytes, and the low address bits give the position (offset) within the line.

Related comparisons