Teaching / Memory hierarchy
Interactive lesson
The Memory Hierarchy
The CPU is fast and memory is slow, so computers stack several kinds of memory between them: small and fast near the CPU, big and slow far away. Ask for data and watch where it is found, what it costs, and how it moves up. Then change the program’s habits and see the cost change.
This page supports British University Vietnam students in the module Introduction to Computing Science (2024–2027 and onwards). It follows the Week 8 “Systems” lecture and continues from the Fetch–Execute cycle lesson.
Each box is one level of memory. Small squares are cache lines holding a block of 4 words.
—What just happened
Pick an access pattern and press Run, or click blocks in the memory map. Every access starts at the CPU and goes down the levels until the data is found.
Last 80 accesses: where each one was served
How slow is “slow”?
Typical figures for a desktop CPU at about 3 GHz. Real machines differ, but the ratios are what matter. Tick the box to stretch time so that one CPU cycle lasts one second.
| Level | Typical size | Latency (cycles) | Real time | Relative (log scale) |
|---|
Going to RAM costs about 60 L1 hits; going to an SSD costs about 40,000. A CPU that waits for the SSD could have run hundreds of thousands of instructions.
Key ideas
Hit and miss
A cache hit means the data is already in that level. A cache miss means it is not, so the request goes one level further down and the block is copied back up on the way. The hit rate is hits ÷ accesses.
Blocks, not words
Memory moves in blocks (cache lines). Here a block is 4 words; real CPUs use 64 bytes. Reading word 37 brings words 36–39 with it, so the next three reads are free.
Temporal locality
Data used recently is likely to be used again soon (a loop counter, a total). Caches keep recently used blocks and evict the least recently used one when full.
Spatial locality
Data next to what you just used is likely to be used soon (the next array element). Fetching whole blocks pays off when you walk memory in order.
Average access time
Average cost = Σ (share served by each level × that level’s latency). With 95% L1 hits at 4 cycles and 5% from RAM at 250 cycles: 0.95×4 + 0.05×250 = 16.3 cycles. A small miss rate dominates the cost.
Three kinds of miss
Cold: first ever touch of a block. Capacity: the cache is too small to keep it. Conflict: there was room, but the placement rule (direct-mapped) forces two blocks into one slot. The results panel counts each kind for L1.
How to avoid cache misses
- Walk memory in order. Use the row by row and column by column patterns on the same 16×8 table: the same 128 reads, very different costs.
- Keep the working set small. Slide the working set up and watch the cliffs: it falls out of L1, then L2, then L3, then RAM. Past RAM, every access is an SSD page fault.
- Reuse data while it is hot. Do all the work on a block before moving on (loop tiling or “blocking”), instead of sweeping the whole data set several times.
- Prefer contiguous data. Arrays are friendly; linked lists and scattered objects behave like the random access pattern.
- Let the prefetcher help. Tick Prefetch next block on a sequential scan, then on random access: prefetching only works when the pattern is predictable.
- Add the right memory. If the working set slightly exceeds RAM, performance collapses (thrashing). More RAM, or a smaller data set, fixes it.
The Von Neumann bottleneck
In a Von Neumann computer, instructions and data live in the same memory and travel to the CPU over the same bus. The CPU can do work far faster than that bus can deliver, so it spends much of its time waiting. The memory hierarchy is the main fix: most accesses are answered by a fast cache close to the CPU. Switch Caches off in the simulator and compare the “CPU waiting” figure.
One shared path or two?
Each instruction needs one trip to fetch itself (I) and, if it reads or writes data, another (D). Drag to change how many instructions touch data.
Modern CPUs soften this with separate L1 caches for instructions and data (a “modified Harvard” design), so the CPU can fetch both at once, while main memory stays Von Neumann. Other tricks: wider and faster buses, prefetching, and running other work while waiting.
Things to try
- Cold start. Reset, choose Scan an array in order and run 64 accesses. Why is the L1 hit rate exactly 75%? (One miss per 4-word block.) Which level served those misses?
- Warm vs cold. Run One variable repeatedly. Press Clear counters (keeping the cache contents) and run again. What changed?
- Find the cliffs. Use Loop over a working set and raise the size from 1 to 64 blocks. At which sizes does each level stop helping? How do they relate to the L1, L2, L3 and RAM sizes shown?
- Same work, different order. Run 16×8 table, row by row then column by column. Compare the average cost per access, and which level serves the column-by-column reads.
- Conflict misses. Choose My own list and enter
0 16 32 0 16 32 0 16 32: three blocks that all map to the same L1 slot. Run it with L1 “one fixed slot”, then with “any slot”, and compare the conflict count. - Thrashing. Loop over 33 blocks, then 32. RAM only holds 32 blocks. Why does one extra block make such a huge difference to the cost of every pass?
- Remove the caches. Switch caches off and run anything. How long would the CPU spend waiting, as a percentage?