Lesson 35 · Computer architecture

Caches: keeping memory close to the CPU

Main memory is slow next to a CPU, so every processor keeps a cache: a small, fast copy of memory it used recently. Watch a tiny cache at work, one address at a time. Each address splits into tag, index and offset; the index picks a row, the tag says whether the row holds the right line, and a miss brings the whole line in from memory. Then compare direct-mapped with 2-way set-associative placement, see LRU pick a line to evict, follow a store through write-through and write-back, and work out how hit rate sets the average access time.

14 min11 steps5 questionsAdvanced

Fig 35 · Interactive

Loading figure…

or ← →

Check yourself

5 quick questions

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

01The toy cache has 16-byte lines, 4 rows and 8-bit addresses. Which bits of 0x64 (0110 0100) are the index?

The low 4 bits (0100) are the offset inside a 16-byte line, the next 2 bits (10) are the index that picks one of 4 rows, and the top 2 bits (01) are the tag.

02Row 2 is valid and holds tag 00. The CPU asks for 0x28, whose index is 10 and tag is 00. What happens?

Valid bit 1 and matching tags mean the right line is already there. 0x28 sits in the same 16-byte line as 0x24, so loading 0x24 brought it along.

03In the direct-mapped cache, 0x24 and 0x64 keep throwing each other out while three rows sit empty. What fixes that without making the cache bigger?

Both lines have the same index, so a direct-mapped cache can keep only one of them. Grouping the same 4 rows into 2 sets of 2 ways lets 0x20 and 0x60 sit side by side, and the second 0x24 hits.

04A write-back cache stores a new byte into a line. What does it do to main memory right away?

That is the difference from write-through, which updates memory on every store. Write-back saves trips when the same line is written many times.

05Hit time is 1 ns and the miss penalty is 100 ns. What is the average memory access time with a 95% hit rate?

AMAT = hit time + miss rate × miss penalty = 1 + 0.05 × 100 = 6 ns. At 98% hits it falls to 1 + 0.02 × 100 = 3 ns.

Key terms

Glossary

Cache: A small, fast memory (SRAM) beside the CPU that keeps copies of recently used parts of main memory.
Cache line: The block of neighbouring bytes a cache copies as one unit: 64 bytes on most Intel and AMD chips, 16 in the figure.
Tag, index, offset: The three parts of an address: the offset picks a byte inside a line, the index picks a row (or set), and the tag says which line is stored there.
Valid bit: A bit on each cache row that says whether the row holds real data yet.
Hit and miss: A hit finds the line already in the cache; a miss has to fetch it from the next, slower level of memory.
Set-associative: A cache where each line can go in any of a few ways of one set (2 in the figure); direct-mapped is the 1-way case.
LRU: Least recently used: when a set is full, evict the line that has gone unused the longest.
Write-back and dirty bit: A write policy that updates only the cache and marks the line dirty; the line is written to memory when it is evicted. Write-through updates memory on every store instead.

Fine print

Notes and sources

A cache keeps copies of recently used memory in a small, fast memory (SRAM) near the processor and moves data in fixed-size blocks called lines; each address is split into a tag, an index and a block offset, and each row has a valid bit (Patterson and Hennessy, Computer Organization and Design RISC-V Edition, section 5.3).
Intel 64 and IA-32 processors and AMD Zen processors use 64-byte cache lines (Intel Optimization Reference Manual; AMD Software Optimization Guide). The figure uses 16-byte lines, 8-bit addresses and 4 rows so every bit fits on screen; the rules are the same.
In a direct-mapped cache each memory line can go in exactly one row; in an n-way set-associative cache it can go in any of the n ways of one set, and the cache compares all n tags at once. Misses caused by lines competing for the same place are conflict misses (Patterson and Hennessy, sections 5.4 and 5.8).
Least recently used (LRU) replacement evicts the line in the set that has gone unused the longest (Patterson and Hennessy, section 5.4). Real caches with many ways often use cheaper approximations of LRU.
Write-through updates the cache and the next level on every write, usually through a write buffer; write-back updates only the cache and writes a modified (dirty) line to the next level when it is replaced (Patterson and Hennessy, section 5.3, Handling Writes).
Average memory access time = hit time + miss rate × miss penalty (Hennessy and Patterson, Computer Architecture: A Quantitative Approach, appendix B). The figure uses a 1 ns hit and a 100 ns miss penalty, in line with an L1 cache of about 1 ns and DRAM of 50 to 100 ns (same book, figure 2.1).
The Python mirrors the hardware: shifting right by 4 drops the offset bits, & 0b11 keeps the 2 index bits, and the rows list remembers one tag per row of the direct-mapped cache.
Lit traces with moving dashes carry the value the step is about; the white tags riding them are those values (addresses, index and tag bits, lines and bytes). Round lamps on each row: V = valid, D = dirty, glowing = 1.

Quiz Unlocks after the last step.