Skip to content
Tutorials Center
My learning

Topics

Lesson 44 of 67 ยท Memory Hierarchy

Cache Performance and the Three Cs

Classify cache misses as compulsory, capacity or conflict, compute AMAT for multilevel caches, and see how loop order changes the miss rate in Python.

A cache is only worth having if it makes the average memory access fast. To judge that, you need two tools: a way to explain misses (so you know which design change would remove them) and a way to measure the damage in time (so you can compare designs on one scale). The first tool is the "three Cs" model. The second is the average memory access time, AMAT, extended to several cache levels.

This lesson uses both, then finishes with a surprising experiment: the same program, with its loops swapped, changes the miss rate from a few percent to a hundred percent. The vocabulary of blocks, sets and ways comes from Cache Memory Basics and Direct, Associative and Set-Associative Mapping.

The three Cs of cache misses

Every miss in a cache falls into one of three categories:

  • Compulsory (also called cold or first-reference) misses happen the first time a block is ever touched. No cache can avoid them, since the data was never loaded. Larger blocks and prefetching reduce them.
  • Capacity misses happen because the cache cannot hold everything the program uses. If the working set is larger than the cache, blocks are evicted and then needed again. A bigger cache reduces them.
  • Conflict misses happen because of the mapping rule. The cache has room, but too many blocks compete for the same set. Higher associativity or a different layout reduces them.

A handy test separates capacity from conflict: replay the same trace on a fully associative LRU cache of the same total size. If that cache hits where yours misses, the miss was caused by placement restrictions, so it was a conflict miss. If even the fully associative cache misses (and the block had been seen before), it was a capacity miss.

flowchart TD
  M["A miss occurs"] --> Q1{"First time this block<br/>was ever referenced?"}
  Q1 -- "yes" --> C1["Compulsory"]
  Q1 -- "no" --> Q2{"Would a fully associative<br/>cache of the same size hit?"}
  Q2 -- "no" --> C2["Capacity"]
  Q2 -- "yes" --> C3["Conflict"]

The three Cs decision tree. The fully associative cache is the yardstick for "enough room".

The program below implements exactly this test. It runs an 8-block cache with 1, 2 and 8 ways (8 ways means fully associative) over three traces.

Python Classify misses: compulsory, capacity, conflict

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.

Study the three rows:

  • The ping-pong trace touches only three blocks, far fewer than the 8-block capacity, yet the 2-way cache gets zero hits: blocks 0, 4 and 8 all map to the same 2-line set, and LRU evicts each one just before it is needed. All 27 repeat misses are conflict misses. The fully associative cache gets 27 hits, because it has plenty of room.
  • The sweep of 10 blocks needs more than 8 blocks, so the working set exceeds the capacity. With 8 ways every repeat access misses (30 capacity misses), and no associativity can fix a trace this large. Only a bigger cache or a better access pattern helps.
  • The 6-block walk fits in the cache under every mapping. The only misses are the 6 compulsory ones.

One note on the 2-way and 1-way sweep rows: they show hits (12 and 18) that the fully associative cache does not get. LRU is not always optimal, and a cyclic pattern a little larger than the cache is exactly where full LRU behaves worst. Misses are still labelled "capacity" by the test, because the yardstick missed too.

The lesson for design: compulsory misses are fixed by block size and prefetching, capacity misses by size, conflict misses by associativity or by changing the data layout.

Average memory access time with several levels

Recall the formula for one cache level:

AMAT = hit time + miss rate x miss penalty

With several levels, the "miss penalty" of L1 is the time to get the data from L2, which is itself an AMAT. For two levels:

AMAT = T(L1) + m(L1) x [ T(L2) + m(L2 local) x T(memory) ]

Two kinds of miss rate appear and they are easy to confuse:

  • The local miss rate of L2 is the fraction of the accesses that reach L2 which miss in L2.
  • The global miss rate is the fraction of all CPU accesses that miss in L2. It equals m(L1) x m(L2 local).

Because L1 filters out most accesses, the accesses that arrive at L2 are the hard ones, so L2's local miss rate looks bad (maybe 20 to 50 percent) even when L2 works well. The global rate tells you how often memory is actually reached.

flowchart LR
  CPU["CPU"] -->|"every access"| L1["L1 cache<br/>1 cycle"]
  L1 -->|"L1 misses (5%)"| L2["L2 cache<br/>10 cycles"]
  L2 -->|"L2 local misses"| MEM["Main memory<br/>100 cycles"]

Each level only sees the misses of the level above, so the later levels trade speed for size.

Python AMAT with one and two cache levels

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.

If the L2 never helped (100 percent local misses), AMAT would be worse than having no L2, because every miss pays the 10-cycle detour. With a 20 percent local miss rate, AMAT drops from 6.00 to 2.50 cycles, and the CPI of a program with 1.3 memory references per instruction falls from 7.50 to 2.95. This is the same style of calculation you used in Measuring Performance: memory stalls simply add to the base CPI.

Design trade-offs follow from the formula. L1 is kept small and fast (a hit time of 1 to 4 cycles) because it is paid on every access. L2 and L3 are larger and slower, because their job is to cut the global miss rate, and their hit time matters only for the few accesses that reach them.

An experiment: loop order and miss rate

Two nested loops over a matrix can visit the same elements in different orders. In C, Java and NumPy the default layout is row-major: the elements of one row sit next to each other in memory. Walking along a row uses every byte of each fetched block (good spatial locality). Walking down a column jumps by a whole row between accesses.

The program builds the address of each element of an N x N matrix of 4-byte integers with NumPy and replays the trace through an 8 KB, 4-way, 64-byte-block cache with LRU.

Python Row order versus column order

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 explain themselves:

  • Row order always misses 6.2 percent of the time: one miss per 16 integers (a 64-byte block holds 16 four-byte integers), and the other 15 accesses hit. That is pure compulsory misses.
  • At 32 x 32 (4 KB) the whole matrix fits in the 8 KB cache, so column order also only pays the compulsory misses and the two orders tie.
  • At 64 x 64 (16 KB) the matrix is larger than the cache, and column order jumps to a 100 percent miss rate. Each row is 256 bytes, so the column walk touches blocks 4 apart; only 8 of the 32 sets are ever used, so 64 blocks compete for 32 lines (8 sets x 4 ways) and LRU throws each block out before its neighbours in the row are reached. This is a mix of capacity and conflict misses, the second one getting worse when the row length is a power of two.

On a real machine this shows up as wall-clock time: large matrices traversed in the wrong order can run several times slower with identical arithmetic. The trick is to match the loop order to the memory layout. You will apply this idea, and its cousin loop tiling, in Writing Cache- and CPU-Friendly Code.

When profiling a slow loop, ask three questions in order: does the data fit in the cache (capacity)? Does the stride land on a power of two that maps to few sets (conflict)? Is each fetched block used fully before it is evicted (spatial locality)?

Simultaneous versus hierarchical access

The AMAT formulas above assume that the next level is only consulted after a miss is detected. That is one of two ways to organize a pair of levels, and exam questions often ask you to compute both.

  • Hierarchical (sequential) access. The CPU asks level 1 first. Only if it misses does the request go to level 2. A miss therefore pays the time of level 1 and level 2.
  • Simultaneous (parallel) access. The request goes to both levels at the same moment. If level 1 hits, level 2's work is abandoned; if level 1 misses, level 2 is already under way, so a miss pays only the time of level 2.

With hit ratio H1 at level 1, access times T1 and T2, and every request satisfied at level 2:

Text
Hierarchical:   T = H1 x T1 + (1 - H1) x (T1 + T2)   =  T1 + (1 - H1) x T2
Simultaneous:   T = H1 x T1 + (1 - H1) x T2

Example with H1 = 0.9, T1 = 10 ns and T2 = 100 ns: hierarchical gives 0.9 x 10 + 0.1 x 110 = 20 ns, simultaneous gives 9 + 10 = 19 ns. Simultaneous access is never slower, but it saves only (1 - H1) x T1, a small amount when the hit ratio is high, and it costs hardware: the lower level is busy with requests that mostly turn out to be unnecessary, which wastes bandwidth and energy. That is why caches in front of main memory use hierarchical access, while some designs read a cache's tag and data arrays in parallel (a different kind of simultaneity).

Python Hierarchical versus simultaneous AMAT

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 saving (1 - H1) x T1 shrinks as the hit ratio rises, which is the numerical reason designers accept the simpler hierarchical scheme.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A block is referenced for the very first time and misses. What kind of miss is it?

    A first reference cannot hit in any cache because the block was never loaded. These cold misses are called compulsory misses.
  2. 2. How do you tell a conflict miss from a capacity miss in a simulation?

    If a fully associative cache of equal size hits, there was room and the miss came only from the placement rule: a conflict miss. If it misses too, the working set was too large: a capacity miss.
  3. 3. L1 miss rate is 4%, L2 local miss rate is 25%. What is the global miss rate of L2?

    The global rate is m(L1) x m(L2 local) = 0.04 x 0.25 = 0.01, or 1% of all CPU accesses reach main memory.
  4. 4. Why is a column-order traversal of a large row-major matrix slow?

    Walking down a column jumps by a full row between accesses. Each fetch uses one element of a 64-byte block, and the block is gone from the cache before the next element of its row is visited.
  5. 5. Which change reduces compulsory misses?

    Compulsory misses come from first touches. Fetching more data per miss (larger blocks) or fetching it before it is requested (prefetching) turns some first touches into hits.

Summary

  • Misses come in three kinds: compulsory (first touch), capacity (working set larger than the cache) and conflict (too many blocks mapped to one set).
  • A fully associative cache of equal size is the yardstick that separates capacity from conflict misses.
  • Remedies differ: larger blocks and prefetching for compulsory, bigger caches for capacity, more associativity or a different data layout for conflict.
  • Multilevel AMAT = T(L1) + m(L1) x [T(L2) + m(L2 local) x T(memory)]; the global miss rate is the product of the local rates.
  • A good L2 can cut AMAT and CPI sharply even when its own local miss rate looks high.
  • Traversal order matters: matching loops to the row-major layout can change the miss rate from a few percent to 100 percent.

Continue with Cache Coherence and Memory Consistency.