Why caches
Main memory (DRAM) answers in 50 to 100 ns. A 3 GHz CPU ticks 300 times in 100 ns. A cache is a small, fast memory (SRAM, about 1 ns) beside the CPU that keeps copies of memory it used recently.
A cache copies memory in lines: blocks of neighbouring bytes, 64 bytes on most Intel and AMD chips. This toy uses 16-byte lines and 8-bit addresses, so its 256 bytes of memory make 16 lines, and the cache holds 4.
Hits and misses
To find a byte, the cache splits its address. 0x24 is 0010 0100 in binary. The low 4 bits (offset) pick a byte inside the line. The next 2 (index) pick one of 4 rows. The top 2 (tag) tell apart lines sharing a row.
The CPU asks for 0x24. Index 10 picks row 2, but its valid bit V is 0: nothing there. That is a miss. The whole line 0x20 to 0x2F comes from memory, row 2 keeps tag 00, and the byte goes on.
Next the CPU asks for 0x28. Index 10 again, and row 2 is valid with tag 00, the same as the address's tag. That is a hit: about 1 ns, no trip to memory. The neighbouring bytes came along with the line.
Where a line can go
Now 0x64: index 10 again, but tag 01. It misses, and line 0x60 throws out line 0x20. Asking for 0x24 again misses too, while rows 0, 1 and 3 sit empty. In a direct-mapped cache each line can live in only one row.
A 2-way set-associative cache groups the same 4 rows into 2 sets of 2 ways. Now the index is 1 bit and the tag 3. Replaying 0x24, 0x28, 0x64, 0x24, lines 0x20 and 0x60 share set 0, so 0x24 hits.
0xA4 also maps to set 0, with tag 101, and both ways are full. The cache evicts the least recently used (LRU) line. 0x24 was used just now, so line 0x60 leaves and line 0xA0 takes its way. It was clean, so it is dropped.
Writes and speed
Writes change data. The CPU stores 7 at 0x28, a hit in set 0. A write-through cache writes the new byte into the cache and into memory. Memory always matches, but every store makes the slow trip.
Had the cache been write-back instead, the same store goes into the cache only, and sets the row's dirty bit D to 1. Memory would be out of date. The line goes back to memory once, when it is evicted, however many stores it took.
Average memory access time = hit time + miss rate × miss penalty. With 1 ns hits and a 100 ns miss penalty, 95% hits gives 1 + 0.05 × 100 = 6 ns. At 98% hits it is 3 ns: twice as fast.
The working
;; step 1/11 · why ;; about: CPU, Cache, Main memory typical times L1 cache (SRAM) ~1 ns main memory (DRAM) 50–100 ns 3 GHz clock = 3 ticks per ns 100 ns × 3 = 300 ticks waiting The cache sits between the CPU and memory. When it already has a copy, the CPU skips the long trip. This figure: CPU, a 4-row cache and 256 bytes of main memory.
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. 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.