The Machine · Chapter 5.c
Optional read: How does a CPU hide slow memory?

Watch the opener · 1:12

Transcript

How does a CPU hide slow memory? If one cycle took a second, main memory would take seven minutes.

So I figured it just waits, seven minutes a word, every time. But programs keep asking for the words they just used, or the one next door.

So keep a small, fast copy right beside the core: a cache. Ask for a word. It's not there. That's a miss: make the long trip. But don't bring back one word. Bring its whole line of eight. Now ask for the next word. It's already here: a hit. The next six hit too. One slow trip buys seven fast ones. And a loop keeps asking for the same words, so it hits again and again.

So it hides slow memory by barely going there! The cache doesn't make memory fast; it makes the slow trip rare.

Slide the hit rate below. Why do a few misses cost so much?

The pipeline model of Chapter 5.b can finish an independent instruction every cycle once filled. But every instruction is fetched from memory, and memory is slow. A core can do an addition in about a cycle; a read from main memory can cost a few hundred. Without faster storage nearby, a core would spend almost all of its life waiting for the next word to arrive. This chapter is about the trick that hides the wait, one of the central performance ideas in hardware.

5.c.1 How far away memory is

The gap is easier to feel if we stretch time. Suppose one clock cycle lasted one whole second. Then reaching the nearest, smallest, fastest memory takes a few seconds; reaching main memory takes minutes; reaching the disk takes days; and reaching another machine across the network takes over a year. Figure 5.c.2 lays the distances out on that human scale.

The interactive version needs the in-browser runtime.

No single memory can be both large and close, so machines use several at once: a small, fast one right beside the core, backed by larger, slower ones further out. The small fast pools are caches, built from the same idea of cross-coupled stored bits as the registers of Chapter 4. The whole scheme works only because programs are predictable, in two ways. A word just used is likely to be used again soon (temporal locality), and the words next to it are likely to be used soon after (spatial locality). Figure 5.c.3 shows how the second of those leads a cache to move data in whole lines, not single words.

5.c.2 Keeping the hot data near

The model here is the simplest cache that works, a direct-mapped one. Each line of memory maps to exactly one slot in the cache, chosen by its number. A load hits if that slot already holds the line it wants, and otherwise misses, fetches the line, and evicts whatever was there.

Example 5.c-1. A direct-mapped cache

class Cache:
    """A direct-mapped cache: every memory line maps to exactly one slot."""

    def __init__(self, slots: int = SLOTS, line: int = LINE):
        self.line = line
        self.blocks = [None] * slots   # the line number in each slot, or None

    def load(self, address: int) -> bool:
        """Look up an address. Return True on a hit; on a miss, load its line into
        the one slot it maps to, evicting whatever was there, and return False."""
        block = address // self.line1
        slot = block % len(self.blocks)
        hit = self.blocks[slot] == block2
        self.blocks[slot] = block3
        return hit

• the address divided by the line size names the line it belongs to
• a hit is when the one slot that line maps to already holds it
• on a miss the line is loaded into that slot, evicting the old one: this is why two lines that map to the same slot keep pushing each other out

The model tracks which line occupies each slot, not the data words themselves. To see locality at work, feed it three fixed address traces. Each run starts with an empty cache of four slots and eight words per line:

These are the constants in ftb.cache; for example, run(Cache(), SCAN) returns (56, 8). The scan misses once per new line. The loop’s two lines stay cached after their first visits. The thrashing trace visits line numbers 0,4,8,12, all mapping to slot 0 in a four-slot cache, so each visit evicts the previous line. It demonstrates a conflict even though four lines would fit in four slots.

5.c.3 The hit rate is everything

A cache only helps when it hits, so the number that matters is the hit rate. The arithmetic is brutal. An average access costs the fast hit time always, plus the slow miss penalty on the fraction that miss. When the penalty is a hundred times the hit, even a small miss rate dominates the average.

Example 5.c-2. The average cost of an access

def average_access(hit_rate: float) -> float:
    """The cost of an average access: the hit time always, plus the miss penalty
    on the fraction that miss. A small miss rate on a large penalty still hurts."""
    return HIT_TIME + (1 - hit_rate) * MISS_PENALTY1

• the hit time is paid on every access; the miss penalty only on the misses, but it is so large that a few percent of them decide the average

The cache does not make memory fast; it makes the slow trip rare. That closes the processor performance path. The next optional read asks how an FPGA loads a circuit as data. You can stop here with the CPU and its performance tradeoffs in view, or follow that last hardware connection to memory.

Exercises

• Run the same SCAN through Cache(line=16), doubling the line size. What happens to its hit rate, and why?
• Run each fixed trace through Cache(slots=16), increasing the slots from four to sixteen. Which pattern improves? Why does Cache(slots=8) still give no hits for THRASH? Change the cache instance, leaving the trace addresses unchanged.
• At a miss penalty of a hundred cycles, what hit rate does a program need to average under two cycles per access?