Lesson 27 · Memory

The memory hierarchy

Fast memory is small and expensive; big memory is slow. So a computer stacks several kinds: registers inside the core (under a nanosecond), three SRAM caches (about 1 to 20 ns), DRAM main memory (about 100 ns), then an SSD (tens of microseconds) and a hard disk (milliseconds). Watch a request fall down the staircase, level by level, until one level has the data, and see why locality, programs reusing data and using nearby data, lets the small fast levels answer almost every request.

12 min11 steps5 questionsIntermediate

Fig 27 · Interactive

Loading figure…

or ← →

Check yourself

5 quick questions

Pick an answer to see why. Your score saves with your progress.

01Which list goes from fastest to slowest?

Registers answer in under a nanosecond, L1 in about 1 ns, RAM in about 100 ns, an SSD in tens of microseconds and a hard disk in milliseconds.

02The core asks for a value. L1 and L2 do not have it, L3 does. What happens?

A request falls down the levels until one has the data (a hit). On the way back up, the caches it passed keep a copy, so the next request for it can hit in L1.

03A loop adds to the variable total on every pass. Which idea explains why total stays in L1?

Temporal locality: data used recently is likely to be used again soon. total is used on every pass, so it stays in the fastest cache.

04Why does a cache bring a whole 64-byte line from RAM, not just the one value that was asked for?

Spatial locality: reading a list in order uses neighbouring entries next. One miss brings a 64-byte line, eight of the list's 8-byte slots, so the next several reads hit L1.

05L1 takes 1 ns, 5% of requests miss and each miss costs 100 ns more. What is the average access time?

Average = hit time + miss rate × miss penalty = 1 + 0.05 × 100 = 6 ns: close to L1's speed.

Key terms

Glossary

Memory hierarchy: The stack of memories in a computer, from small, fast and costly (registers, caches) to big, slow and cheap (RAM, SSD, hard disk).
Nanosecond (ns): A billionth of a second. A microsecond (µs) is 1,000 ns; a millisecond (ms) is 1,000,000 ns.
Cache: A small, fast memory that keeps copies of data used recently, so the next use does not have to wait for slower memory.
SRAM and DRAM: SRAM (static RAM) keeps each bit in about six transistors: fast, used for caches. DRAM keeps each bit as charge on a tiny capacitor: dense and cheap, used for main memory.
Hit and miss: A hit: the level asked has the data. A miss: it does not, so the request goes to the next, slower level.
Cache line: The block of data a cache moves at a time, usually 64 bytes, so the neighbours of a value come along with it.
Temporal locality: Data used recently is likely to be used again soon (a loop counter, a running total).
Spatial locality: Data next to recently used data is likely to be used soon (the items of an array, read in order).

Fine print

Notes and sources

Typical sizes and access times after Hennessy and Patterson, Computer Architecture: A Quantitative Approach (6th ed., figure 2.1): registers about 1000 bytes and 300 ps, L1 64 KB at about 1 ns, L2 3-10 ns, L3 10-20 ns, main memory 50-100 ns, flash 25-50 microseconds, disk 5-10 ms. Real chips vary; AMD's Ryzen 9 7950X has 1 MB of L2 per core and 64 MB of L3.
SRAM keeps each bit in a loop of about six transistors and needs no refresh; DRAM keeps each bit as charge on one capacitor behind one transistor, so it is denser and cheaper but slower (Patterson and Hennessy, Computer Organization and Design, sections 5.1-5.2).
Temporal locality: an item used recently is likely to be used again soon. Spatial locality: items near one used recently are likely to be used soon. Caches exploit both by keeping recent data and fetching whole blocks (Patterson and Hennessy, section 5.1; Denning, The locality principle, 2005).
Caches move data in fixed-size blocks called cache lines; on Intel processors a line is 64 bytes (Intel 64 and IA-32 Architectures Optimization Reference Manual). A CPython list stores references to its items side by side, 8 bytes each on a 64-bit build.
Average memory access time = hit time + miss rate × miss penalty (Hennessy and Patterson, appendix B). With a 1 ns hit, a 5% miss rate and a 100 ns penalty: 1 + 0.05 × 100 = 6 ns.

Quiz Unlocks after the last step.