Skip to content
Tutorials Center
My learning

Topics

Lesson 42 of 67 ยท Memory Hierarchy

Direct, Associative and Set-Associative Mapping

Compare direct-mapped, fully associative and set-associative cache placement, see conflict misses appear and disappear, and run a cache simulator class.

A cache has far fewer lines than main memory has blocks, so a rule is needed that says where a given memory block may be stored. The rule is the cache's mapping. It decides how quickly the hardware can find a block, how many comparisons it needs, and how often two blocks fight over the same place.

There are three families, and one idea ties them together: associativity, the number of lines in which a block is allowed to live. In this lesson you will compare the three, build a cache simulator class in Python, and see conflict misses vanish as associativity grows. It continues from Cache Memory Basics, where you split addresses into tag, index and offset.

Three placement rules

Take a small cache with 8 lines and ask where memory block number 13 may go.

flowchart LR
  B["Memory block 13"] --> D["Direct-mapped:<br/>line 13 mod 8 = 5<br/>(only one choice)"]
  B --> S["2-way set-associative:<br/>set 13 mod 4 = 1<br/>(either of 2 lines)"]
  B --> F["Fully associative:<br/>any of the 8 lines"]

The same block, three rules: one place, a small group of places, or anywhere.

Direct-mapped

Each block has exactly one possible line: line = block number mod number of lines. The index bits of the address are that line number.

  • Fast and cheap: one tag comparison, no choice of victim.
  • Weakness: two blocks with the same index keep evicting each other even when the rest of the cache is empty. These are conflict misses.

Fully associative

A block can go in any line. The hardware compares the address tag with every line's tag in parallel, and when the cache is full it has a free choice of victim.

  • No conflict misses: the cache is used completely.
  • Expensive: one comparator per line, which costs area, power and time. There are no index bits at all, so the whole block number is the tag.
  • Where it is used: small structures such as TLBs, where the number of entries is tiny.

Set-associative

The compromise. Lines are grouped into sets of k lines (a k-way cache). The index selects a set, and the block may occupy any of the k lines in that set. The hardware reads all k tags of the chosen set in parallel and compares each with the address tag.

TEXT
sets = lines / ways        index bits = log2(sets)

Direct-mapped is just 1-way, and fully associative is "one set containing all lines". Real L1 caches are typically 4-way to 12-way, and L2 and L3 caches 8-way to 16-way or more.

flowchart TD
  A["Address"] --> I["Index: pick a set"]
  I --> W0["Way 0:<br/>valid, tag, data"]
  I --> W1["Way 1:<br/>valid, tag, data"]
  A --> T["Tag from address"]
  T --> C0{"= way 0 tag?"}
  T --> C1{"= way 1 tag?"}
  W0 --> C0
  W1 --> C1
  C0 --> O["OR: hit if any matches,<br/>select that way's data"]
  C1 --> O

A 2-way lookup: the index reads both ways, two comparators check tags at once, and the matching way supplies the data.

A cache simulator class

The class below models any of the three mappings with one parameter, ways. Each set is a Python list of tags, kept in least-recently-used order, so a hit moves the tag to the end and a miss on a full set removes the first entry. (Replacement policies get their own lesson: Replacement and Write Policies.)

The experiment reads several arrays in lock-step, like c[i] = a[i] + b[i]. The arrays are placed exactly one cache size apart, so element i of every array maps to the same set. This is a classic accident: power-of-two array sizes line up perfectly.

Python Cache simulator and the lock-step arrays experiment

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The pattern in the results is clean. The best possible hit rate for this trace is 75%: each 16-byte block holds four 4-byte integers, so the first access misses and the next three hit, if the block is still present.

  • With 2 arrays, the direct-mapped cache scores 0%: a[i] and b[i] take turns evicting one another on every single access, even though the cache is almost empty. This effect is called thrashing. Two ways are enough to reach 75%.
  • With 3 arrays, two ways are no longer enough, and 4 ways recover 75%.
  • With 5 arrays, you need 8 ways.

The rule of thumb behind this: if n blocks compete for one set at the same time, you need at least n ways to hold them all. Associativity is insurance against unlucky alignment.

Conflict misses in a realistic workload

Real programs do not line up as neatly as the arrays above. Here the access pattern is random but uses only 48 distinct blocks, scattered over a 256 KB address range, in a 2 KB cache that has room for 64 blocks. In a perfect world every block would fit. Whether they do depends on the mapping.

Python Hit rate versus associativity

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Direct-mapped delivers only 70.8% although everything would fit; 2-way gives 79.3% and 4-way 93.8%. At 8 ways the cache reaches 99.76% with just 48 misses, one per distinct block: these are the unavoidable first-touch (compulsory) misses. Going to 16 ways or full associativity changes nothing. That is the usual shape of the curve, diminishing returns: the first doubling of associativity helps a lot, later ones less and less. Typical measurements on real programs show that 8-way performs nearly as well as fully associative.

What associativity costs

More ways means more work per lookup. The next snippet counts the hardware needed for a 32 KB cache with 64-byte blocks and 32-bit addresses.

Python Comparators and tag storage per design

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Reading across the table:

  • Every doubling of ways removes one index bit and adds one tag bit per line, so the tag array grows slowly (8,704 bits direct-mapped, 13,312 fully associative).
  • The number of comparators doubles with each step, up to 512 for a fully associative cache. Parallel comparison is why fully associative caches are only practical for tiny structures.
  • Reading k ways in parallel also means k data blocks may be read before the tag check finishes, which raises energy per access. For this reason L1 caches often have lower associativity than L2.

The summary of trade-offs:

Direct-mapped Set-associative Fully associative
Places per block 1 k all lines
Comparators 1 k one per line
Hit time shortest slightly longer longest
Conflict misses most fewer none
Typical use simple L1/L2 in small chips most L1-L3 caches TLBs, small buffers

How to find your block's place by hand

For exam-style questions, the steps are always the same:

  1. Compute the block number: address // block size.
  2. Compute the number of sets: lines / ways.
  3. The set is block number mod sets; the tag is block number // sets.

For example, with 8 lines and 2 ways there are 4 sets. Block 13 goes to set 13 mod 4 = 1 with tag 3. Block 9 also maps to set 1 (tag 2), so set 1 holds both blocks without conflict, but a third such block (say block 5, tag 1) would evict one of them.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A cache has 64 lines and is 4-way set-associative. How many sets does it have?

    sets = lines / ways = 64 / 4 = 16, so the index has 4 bits.
  2. 2. Which type of miss does a fully associative cache never have?

    A block can go in any line, so it is evicted only when the whole cache is full. Compulsory (first-touch) misses still happen.
  3. 3. Three arrays are read in lock-step, and element i of each maps to the same set. What is the smallest associativity that avoids thrashing?

    Three blocks need to be present in the set at once, so at least three ways. Real caches use power-of-two associativity (or a few fixed designs), so 4-way is the practical answer, as in the experiment.
  4. 4. Why are fully associative caches rarely used for large caches?

    Every tag must be compared in parallel. For thousands of lines that is too much hardware and energy, so large caches use limited associativity.
  5. 5. A 16 KB, 2-way cache has 32-byte blocks. Which set does byte address 0x1A40 map to?

    0x1A40 is 6720. Block number = 6720 / 32 = 210. The cache has 16384 / 32 / 2 = 256 sets, so the set is 210 mod 256 = 210.

Summary

  • Mapping decides which cache lines a memory block may occupy: one (direct-mapped), a group of k (set-associative) or any (fully associative).
  • sets = lines / ways, the index selects the set, and the tag is compared with all ways of that set in parallel.
  • Direct-mapped caches are simplest but suffer conflict misses, such as thrashing between aligned arrays.
  • More ways remove conflict misses with diminishing returns; about 8 ways is close to fully associative in practice.
  • The price of associativity is more comparators, more parallel data reads, higher energy and slightly longer hit time.
  • Fully associative placement is reserved for small structures such as TLBs.

Next, learn what the cache does when a set is full and when you write data in Replacement and Write Policies.