Multi-Level Caches and Prefetching

A single cache cannot be both fast and large, so processors stack several levels of cache, each one catching what the last one missed. They also try to go one better than waiting for misses: a prefetcher watches the pattern of accesses and fetches data before the program asks for it. This article explains why several levels work, how the levels relate to each other, what inclusion means, how prefetchers work and when they backfire, with results from real address traces.

12 min read | Intermediate

What You'll Learn

• Explain why a hierarchy of caches beats one large cache
• Describe how goals differ between L1, L2 and L3
• Explain inclusive and exclusive cache policies
• Describe common prefetchers and how to judge them

Why More Than One Level

A first-level cache must answer in a few cycles, because every instruction and most data goes through it. That limits it to tens of kilobytes. A cache large enough to catch most misses would be megabytes, and it would take many cycles to read. The solution is the same as for the whole memory hierarchy: use both.

The figures in the picture are rough, for a large core at a high clock. Each step is around three to six times slower and around ten or more times larger. Using AMAT, the average memory access time, with those numbers and assumed miss rates of 5 percent at L1, 40 percent local at L2, and 40 percent local at L3:

AMAT = 4 + 0.05 x (14 + 0.40 x (50 + 0.40 x 300))
     = 4 + 0.05 x (14 + 0.40 x 170)
     = 4 + 0.05 x 82
     = 8.1 cycles

Without L2 and L3, it would be 4 + 0.05 x 300 = 19 cycles. And each level does not need to be perfect, because it only filters what comes through.

Each Level Has a Different Job

L1 caches are built for speed. They are split into instruction and data caches, because the pipeline needs both in the same cycle. They use lower associativity, or careful tricks, to keep the hit time down, and several ports so that a core can do several loads per cycle.

L2 caches are usually private to one core, unified, meaning they hold both instructions and data, and larger. A few extra cycles matter less here, so designers trade them for capacity, higher associativity, and lower power: for example, reading the tags first and only then the one data way that matched.

L3, the last-level cache, is usually shared by all the cores of a chip. Its job is to avoid DRAM, whose latency is so large that almost any hit is worth having. It is also a meeting point, where one core can find data recently used by another. It is often divided into slices across the chip, with the address deciding which slice holds a line, so that access time depends a little on distance.

Line sizes are usually the same at all levels, most often 64 bytes, which keeps transfers between levels simple.

How Levels Relate: Inclusion

When a line is in L1, is it also in L2? There are three common answers:

• Inclusive: everything in L1 is also in L2. When L2 evicts a line, it must also remove it from L1. The advantage is that L2's tags tell you exactly what might be in L1, which helps with coherence. The cost is that L1's contents are duplicated.
• Exclusive: a line lives in one level or the other, but not both. A line moves up to L1 on a hit, and when it leaves L1 it goes down to L2. Total capacity is the sum of the two. The cost is more data movement.
• Non-inclusive: no rule either way. A line may be in both, or just one. This is the simplest and most flexible, but it needs extra tracking to know who holds what.

Designers often use different policies at different levels. Over time, the ratio of L3 size to the size of the private caches has fallen, and pure inclusion has become less attractive, since it wastes more space. Many recent designs use a non-inclusive L3 plus a snoop filter, a separate tag store that tracks what the private caches hold.

Prefetching

Every cache so far waits for a miss. But many miss patterns are predictable. If a program is walking through an array, the next line is an easy guess. A prefetcher makes that guess and brings a line into the cache before it is needed. If it is right, a future miss becomes a hit. It can remove compulsory misses, the kind that no cache size can help with.

Next-Line Prefetch

The simplest prefetcher fetches the next line after a miss:

A model of a 1 KB, 2-way data cache with 16-byte lines ran with and without it, on six small programs:

The sequential programs halve their misses, which is exactly what the picture predicts. The linked list barely changes, because its next node can be anywhere, and neighbors in memory have nothing to do with each other.

Stride Prefetchers

Many loops step through memory with a fixed gap, such as one field of each element in an array of structures. A stride prefetcher keeps a small table indexed by the address of the load instruction. It records the last address and the difference, or stride. If the same stride repeats, it predicts the next one, and it can run ahead several strides, so the data arrives in time.

Other Prefetchers

Instruction prefetchers fetch the next lines of code, and they work very well on straight code. Software can prefetch as well: RISC-V's Zicbop extension provides prefetch hints, and C compilers offer __builtin_prefetch, so code that walks a known structure can ask for data early. Modern large cores contain several hardware prefetchers at once, including ones that learn repeating sequences of addresses, and these can handle some pointer-chasing patterns.

Judging a Prefetcher

Three measures matter:

• Coverage: the share of misses it removes.
• Accuracy: the share of prefetched lines that are actually used.
• Timeliness: whether the data arrives before it is needed, but not so early that it gets evicted first.

A wrong prefetch has real costs. It uses memory bandwidth, and it pushes a possibly useful line out of the cache. A very aggressive prefetcher can make a program slower, especially on a shared cache or a loaded memory system, where it takes capacity from other cores. Good designs watch their own accuracy, and back off when it falls. Prefetched lines are often placed into a small side buffer or at low priority, so that a wrong guess costs less.

Small Tricks Between the Levels

Several small structures sit between the levels and remove a surprising share of misses. A victim cache, proposed in 1990, is a tiny fully associative buffer that holds lines just evicted from L1. If a line is needed again soon after being pushed out, it can be swapped back in a cycle or two instead of being fetched from L2. It is a cheap cure for conflict misses in a low-associativity cache.

Way prediction keeps a small record of which way of a set was used last, and reads only that way, saving the power of reading them all. A correct guess is as fast as a direct-mapped cache, and a wrong guess costs a cycle. Critical word first delivers the wanted word of a line before the rest. And a load buffer holds a line that has just arrived, so that the next few accesses can be served at once while the cache array is busy with something else.

None of these changes the big picture. Each one takes a small amount of area to remove a part of the cost at a boundary between levels. Good cache designs are full of such details, and they account for much of the difference between two caches with the same headline size.

Some Costs of Many Levels

More levels bring side effects. A miss that goes all the way to DRAM must first fail at each level, and the tag checks add to its latency. So some designs start a DRAM access in parallel with the L3 lookup, or they predict that a miss is coming and go straight to memory. Static power rises with the amount of SRAM, and in many chips caches take more than half the die, so leakage is significant. And the whole structure needs to stay coherent, as Multicore Processors and Shared Memory describes.

Whether all of this is needed depends on the product. A small microcontroller has no cache, or one small one. A phone core has three levels, and a server chip may add yet another very large cache stacked on top of the die.

Common Mistakes