Skip to content
Tutorials Center
My learning

Topics

Lesson 59 of 67 ยท Projects

Project: A Configurable Cache Simulator

Build a cache simulator with adjustable size, block size and associativity, feed it address traces, classify every miss and plot hit rates in Python.

Cache designers do not guess; they replay address traces through a simulator and measure. In this project you build that simulator. It takes the cache's size, block size and number of ways as parameters, replays a trace of reads and writes, and reports hits, misses, write-backs and the kind of every miss. Then you use it as a lab: change one parameter at a time and plot what happens to the hit rate.

You will use the ideas from Cache Memory Basics, mapping, replacement and write policies and the three Cs. If any of them feels hazy, the code below is a good place to see them in action.

The design

The simulator models a write-back, write-allocate cache with LRU replacement. It stores no actual data, only which blocks are present, because the hit rate depends only on addresses.

Three parameters describe the cache:

  • size: total capacity in bytes.
  • block: bytes per cache line.
  • ways: lines per set. One way is direct mapped; as many ways as lines is fully associative.

From them everything else follows: the number of lines is size / block, the number of sets is lines / ways, and an address splits into three fields.

flowchart LR
  A["Address"] --> T["tag<br/>the high bits"]
  A --> I["index<br/>log2(sets) bits"]
  A --> O["offset<br/>log2(block) bits"]
  I -->|"selects"| S["One set"]
  T -->|"compared with every way in the set"| S
  S --> R{"Tag found?"}
  R -->|"yes"| H["Hit: mark most recently used"]
  R -->|"no"| M["Miss: evict LRU way, load block"]

An access picks a set with the index bits, then compares the tag against every way in that set.

Each set is an OrderedDict that maps a tag to a dirty bit. The dictionary's order is the LRU order: the first entry is the least recently used, and on every hit the entry moves to the end. That makes LRU almost free to write.

Telling the three kinds of miss apart

A hit rate by itself does not tell you why misses happen, and the fix depends on the reason. The simulator classifies each miss with the standard definitions:

  1. Compulsory if this block has never been referenced before. No cache can avoid it.
  2. Conflict if a fully associative LRU cache of the same total size would have hit. The block was lost only because too many blocks crowded into the same set.
  3. Capacity otherwise: even a fully associative cache of this size would have missed, because the working set is simply too big.

To apply rule 2, the simulator runs a second, fully associative LRU "twin" alongside the real cache. It only tracks which blocks the twin holds.

Step 1: the simulator and a hand-written trace

A trace is a list of memory references, each a read (R) or a write (W) and an address. Real traces come from tools that record programs; here you parse a simple text format. Lines look like R 0x1F40, with # starting a comment.

The program below defines the whole simulator (Cache, parse_trace, report) and replays an eight-line trace on a tiny direct-mapped cache with 8 sets of 16-byte blocks. For every access it prints the tag, index and offset, and what happened.

Python The simulator and a tiny trace

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.

Walk through the output. The first read of 0x000 is a compulsory miss. 0x004 is in the same 16-byte block, so it is a hit: that is spatial locality at work. Then 0x080 has the same index (0) as 0x000 but a different tag, so it takes the one slot in set 0. When 0x000 comes back, it is a conflict miss: the cache has plenty of free sets, but this address maps to a busy one. The write to 0x010 hits and marks the block dirty. When 0x090 later maps to that set (index 1) and replaces the dirty block, the cache must write it back to memory, so the report shows 1 write-back.

The simulator requires block size and number of sets to be powers of two, because the index and offset are plain bit fields. log2_exact checks that and raises a clear error otherwise. Real caches make the same restriction for the same reason: slicing bits out of an address is free in hardware, while division is not.

Step 2: realistic workloads

One tiny trace proves the mechanics. To learn something, you need patterns that resemble real programs. The next program adds five trace generators:

  • Sequential words: walk an array 4 bytes at a time.
  • Stride 256: touch every 256th byte over a 16 KB region, over and over.
  • Matrix by rows and by columns: visit a 64 by 64 matrix of 8-byte numbers in the two orders.
  • Hot and cold: 80% of references go to a hot 1 KB region (30% of those are writes), the rest scatter across 1 MB. The random generator uses a fixed seed, so the numbers are repeatable.

All five go through the same 4 KB, 4-way cache with 64-byte blocks.

Python Five workloads, one cache

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 results show how much the access pattern matters, since the cache is identical in every run.

Workload Hit rate What dominates the misses
Sequential words 93.8% compulsory only: one miss per 16 words
Stride 256 0.0% conflict: 4,032 of 4,096 accesses
Matrix by rows 87.5% compulsory only: one miss per 8 numbers
Matrix by columns 0.0% conflict: 3,584 of 4,096 accesses
Hot 1 KB + cold 1 MB 79.8% compulsory (cold data), a few capacity misses

The two 0% rows are the instructive ones. A stride of 256 bytes is exactly four blocks, so every access lands in one of just 4 of the 16 sets; the trace has 64 distinct blocks, but those 4 sets hold only 16 lines between them. A fully associative cache of the same size would hold all 64 blocks and hit nearly always, which is exactly how the simulator knows these are conflict misses and not capacity misses. Walking the matrix by columns jumps 512 bytes per step, with the same unfortunate mapping. The fix for such patterns is one of: more ways, a padded array width, or a different loop order, as discussed in writing cache-friendly code.

Step 3: sweep a parameter and plot it

A simulator earns its keep by answering "what if". The last program runs three parameter sweeps over three traces and draws one chart for each:

  1. Vary the number of ways from 1 to 64 (4 KB cache, 64-byte blocks).
  2. Vary the block size from 8 to 256 bytes (4 KB, 4-way).
  3. Vary the cache size from 1 KB to 32 KB (64-byte blocks, 4-way).

The traces are: a loop that sweeps a 6 KB array eight times, the stride-256 pattern, and the hot and cold mix. The program prints the numbers and draws the charts with Matplotlib. The first import of Matplotlib is slow because it builds a font cache, so wait a few seconds before the picture appears.

Python Parameter sweeps and a plot

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.

Read the three panels as three lessons.

Associativity helps only when conflicts are the problem. For the stride trace the hit rate stays at 0% from 1 to 16 ways and jumps to 98.4% at 64 ways, when the cache is fully associative. For the 6 KB loop it does something odd: one way scores 95.6%, better than the 93.8% of every higher associativity. The loop is larger than the 4 KB cache and LRU always evicts the block needed soonest (the loop revisits blocks in a fixed cycle), so a fully LRU cache keeps nothing useful. The direct-mapped cache cannot make that mistake, and by luck of its mapping keeps part of the loop. LRU is not always best.

Block size helps sequential access a lot (the 6 KB loop goes from 50.0% with 8-byte blocks to 98.4% with 256-byte blocks) because each miss brings in neighbours that are used next. It does almost nothing for the hot and cold trace, where hits come from reuse, not neighbours. Very large blocks eventually hurt, because they waste bandwidth and reduce how many distinct blocks fit.

Cache size gives a stepped curve: the 6 KB loop jumps from 93.8% to 99.2% only when the cache reaches 8 KB, the first power of two that holds the whole loop. Past that, extra capacity buys nothing, so doubling the cache again is wasted silicon. That is a working-set effect.

When a hit rate surprises you, look at the miss classification before changing anything. Conflict misses call for more associativity or a different layout; capacity misses call for a bigger cache or a smaller working set; compulsory misses call for prefetching or bigger blocks.

Extensions

Try these once the basics work:

  • Add replacement policies (FIFO, random, pseudo-LRU) behind a policy parameter and compare them on the traces above.
  • Add write-through with no-write-allocate and count memory traffic for both write policies.
  • Compute the average memory access time from the hit rate, a hit time of 1 cycle and a miss penalty of 100 cycles: AMAT = hit time + miss rate x miss penalty.
  • Stack two caches (L1 and L2): send L1's misses to an L2 Cache object and report both hit rates.
  • Read a real trace file: parse_trace already accepts text; paste in a longer trace and test your own program's access pattern.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A cache has 8 KB capacity, 32-byte blocks and 4 ways. How many sets does it have?

    There are 8192 / 32 = 256 lines, and 256 lines / 4 ways = 64 sets.
  2. 2. How does the simulator decide that a miss is a conflict miss?

    If a fully associative cache of equal capacity would have kept the block, the only reason for the miss is that too many blocks mapped to the same set.
  3. 3. Why is the block size required to be a power of two in this simulator?

    The address is split by shifting and masking, which only works when the block size and number of sets are powers of two.
  4. 4. The stride-256 trace has a 0% hit rate at 4 KB, 4-way, but 98.4% at 64 ways. What does that show?

    The 64 blocks fit in the 64-line cache, but with 4 ways they pile into a few sets. Full associativity removes the pile-up.
  5. 5. In this simulator, what makes a write-back happen?

    Only dirty blocks differ from memory. They are written back when evicted; clean blocks are simply dropped.

Summary

  • A cache simulator needs only addresses: it tracks which blocks are present, split into tag, index and offset.
  • Size, block size and ways are the three knobs; sets = size / (block x ways).
  • An OrderedDict per set gives LRU almost for free, and a dirty bit per line gives write-back counts.
  • Running a fully associative twin lets you classify misses as compulsory, capacity or conflict, which tells you which remedy to try.
  • Strides and layouts that map many blocks to few sets cause conflict misses; more ways or padding fixes them.
  • Block size rewards spatial locality, cache size rewards fitting the working set, and associativity rewards avoiding conflicts.
  • Parameter sweeps plus a plot turn the simulator into a design tool.

Now switch from the cache to the pipeline in Project: A Pipeline Hazard Visualizer.