Miss Types and Average Memory Access Time

When a cache misses, there is a reason, and the reason decides the cure. Some misses are unavoidable, some mean the cache is too small, and some mean the blocks happen to collide. This three-part view of misses, together with the average memory access time formula, lets an engineer predict what a change will do before making it. This article explains the three kinds of miss, measures them on real programs, works through multi-level AMAT, and shows how the miss rate turns into CPI.

12 min read | Intermediate

What You'll Learn

• Classify a miss as compulsory, capacity or conflict
• Choose the right cure for each kind of miss
• Calculate AMAT for one and two levels of cache
• Convert a miss rate into cycles per instruction

The Three Cs

A classification proposed by Mark Hill in the 1980s splits misses into three kinds, known as the three Cs:

• A compulsory miss, also called a cold miss, is the very first access to a block. The block has never been in the cache, so nothing could have prevented the miss, short of fetching it early.
• A capacity miss happens because the program needs more data than the cache can hold. Even a fully associative cache of the same size would have missed: the block was evicted earlier for lack of room.
• A conflict miss happens because of how blocks map to sets. A fully associative cache of the same size would have hit, but in this cache too many active blocks fell in one set.

The definitions suggest how to measure them. Run the address trace through three models. A block never seen before counts as compulsory. Otherwise, if a fully associative LRU cache of the same size also misses, it is capacity. If that cache would have hit, it is conflict.

What Real Programs Show

Here is that measurement for a 1 KB direct-mapped data cache on four small programs, with 16-byte lines:

Each program has a different problem.

The checksum reads a table and a buffer that fit in the cache. Nearly all of its misses are compulsory: it pays once to bring each block in, and it never misses on it again. The 3 percent left is the price of the first touch.

The memory copy is mostly conflict misses. Its two arrays are each larger than the cache, so it has capacity misses too. But its source and destination elements also keep landing on the same lines, pushing each other out. With a 4-way cache of the same size, its conflict misses disappear, and the miss rate falls from 62.5 to 25 percent.

The linked list is mostly capacity misses. Its data spans about 6 KB, six times the cache size. In this case, associativity does nothing: at 4 ways, it had 36.6 percent misses compared with 35.9 at direct-mapped, a slight worsening. The only cure is more capacity.

A strange thing appears here. A direct-mapped cache can sometimes beat a fully associative one, so a "conflict" count can be odd in detail, because LRU replacement is not perfect. The three Cs are a useful way to think, rather than exact physics.

Curing Each Kind

Once you know the type, the cure follows:

Software can help too. A programmer who knows the cache can split a large computation into blocks that fit in it, which is called loop tiling or blocking. It is a standard trick in matrix libraries. Moving a buffer can cure a conflict. Packing the fields of a structure together improves spatial locality.

Average Memory Access Time

The Memory Hierarchy and Locality introduced this formula:

AMAT = hit time + miss rate x miss penalty

Its value is that it shows how the three parts trade against each other. Say a 1-cycle, 8 KB cache misses 8 percent of the time, with a 40-cycle penalty: AMAT = 1 + 0.08 x 40 = 4.2 cycles. A 32 KB cache misses 3 percent of the time, but it takes 2 cycles to hit: AMAT = 2 + 0.03 x 40 = 3.2 cycles. The larger cache wins, despite the slower hit. If the penalty were only 10 cycles, the numbers would be 1.8 against 2.3, and the smaller one would win. These numbers are assumptions for this example, but the logic holds: the larger the penalty, the more a low miss rate is worth.

Two Levels

With two levels of cache, the penalty of the first level is itself an AMAT:

AMAT = L1 hit time + L1 miss rate x (L2 hit time + L2 miss rate x L2 miss penalty)

The L2 miss rate here is the local miss rate: of the accesses that reach L2, the share that miss. Take L1: 1 cycle, 5 percent misses. L2: 10 cycles, 40 percent local misses. DRAM: 100 cycles more:

AMAT = 1 + 0.05 x (10 + 0.40 x 100)
     = 1 + 0.05 x 50
     = 3.5 cycles

Without the L2, it would be 1 + 0.05 x 100 = 6 cycles, or more with a slow memory. A 40 percent local miss rate looks terrible, but L2 sees only the accesses that L1 could not handle, so it is a hard stream by nature. The global miss rate, the share of all accesses that reach DRAM, is 0.05 x 0.40 = 2 percent, and that is the number to compare with a one-level design.

From Miss Rate to CPI

Each instruction is fetched, and some access data, so:

stall cycles per instruction =
      instruction misses per instruction x penalty
    + data accesses per instruction x data miss rate x penalty

Take the linked-list program from above, where about 8 percent of the instructions are loads or stores. With a 1 KB data cache missing 36 percent of the time and a 20-cycle penalty, the data stalls come to about 0.08 x 0.36 x 20 = 0.58 cycles per instruction. On a core with a CPI of 1.1 otherwise, that is about a third of the run time. With an 8 KB cache, the miss rate falls to about 3 percent, and the stalls to 0.05 cycles per instruction. The penalty here is an assumption, and it would be several times higher with DRAM on a fast clock.

A warning: this works well for a simple pipeline, in which every miss freezes everything. In a large out-of-order core, the processor keeps working during a miss and several misses can overlap, so the true cost is less than the formula says. Out-of-Order Execution and Register Renaming explains why. MPKI, misses per thousand instructions, is the usual way to report it, for caches just as for branches.

Classifying a Miss by Hand

A short example shows how the definitions work. Take a direct-mapped cache of 2 lines, where blocks 0 and 2 map to line 0 and blocks 1 and 3 map to line 1. The program reads blocks 0, 2, 0, 2:

Both blocks would fit in a 2-line cache, so the last two misses have nothing to do with capacity. A fully associative cache hits on them, so they are conflict misses. With 2 ways, this sequence would have only the two compulsory misses.

A script applies the same rule to every access of a real trace, which is how the chart in this article was produced.

What Happens During a Miss

A simple cache is blocking: while one miss is being served, it can do nothing else, and the pipeline waits. Larger processors use a non-blocking cache, which goes on serving hits, and even further misses, while earlier misses are outstanding. A small table of miss status holding registers (MSHRs) tracks each outstanding miss: which line is coming and which instructions are waiting for it. If a second access hits a line already on its way, it just joins the same entry. This matters because a real program's misses often come in bursts, and overlapping them reduces their total cost.

Non-blocking caches change how a miss rate should be read. Two misses that overlap cost less than two misses one after the other, so the same number of misses can cost a very different number of cycles, depending on how they cluster. This is one reason a simple AMAT figure is only a first estimate for a large core.

A Fourth C

With several cores, a fourth kind of miss appears. A coherence miss happens when another core writes to a block, which removes the copy from this core's cache. No size or associativity can stop that. Cache Coherence Protocols explains it. Also, the operating system switching between programs refills the cache with other data, so a program returning to a core may suffer many misses that are not compulsory in any deep sense.

Common Mistakes