Skip to main content
Be Bitwise

CPU Cache Architecture

Cache & Performance · Memory & Systems track

7 min read

Part ofSystems Programming Companion, week 7

In this module

The Memory Wall

Modern CPUs can crunch billions of operations per second, but main memory (DRAM) takes around 100 nanoseconds per access — enough time for hundreds of CPU operations to complete. This yawning gap is the memory wall, and it's bridged by caches: small, fast memories that hold recently accessed data close to the CPU.

Key Concept

CPU caches exist because main memory is slow. Each cache level trades capacity for speed: L1 is tiny but about 4 cycles away, L3 is megabytes but 30 to 70 cycles, DRAM is gigabytes but a couple of hundred cycles or more.

Cache Hierarchy

Modern CPUs have multiple cache levels, each larger and slower than the one before:

  • L1 Cache (~32-64 KB per core, ~4 cycles): split into separate instruction (L1I) and data (L1D) caches. Private to each core.
  • L2 Cache (~256 KB - 1 MB per core, ~12 cycles): unified (instructions and data). Private to each core on modern designs.
  • L3 Cache (~8-64 MB shared, ~30-70 cycles): shared among all cores. Also called the Last Level Cache (LLC).
  • Main Memory (DRAM, ~80-100 ns, which is 200-400 cycles at typical clock speeds): shared by all cores.

Each level caches for the level below. An L1 miss falls through to L2; L2 misses head to L3; L3 misses end up at main memory. The hit rate at each step shapes overall performance.

Cache Lines

The fundamental unit of the cache is the cache line — 64 bytes on nearly every modern CPU. Read a single byte from memory and the entire 64-byte line containing it gets pulled into the cache. The bet here is spatial locality: if you touched byte N, you're probably about to touch bytes N+1, N+2, and so on.

Each cache line holds three things: the data (64 bytes), a tag identifying which memory line it stores (the high bits of the address), and state bits (valid, dirty, MESI state).

Associativity

A cache has to figure out fast whether a given address is already stored. There are three approaches. Fully associative caches let any address live anywhere, but checking requires comparing against every tag — punishingly expensive at scale. Direct-mapped caches assign each address to exactly one location, which is fast but creates ugly conflicts when two hot addresses map to the same slot. Modern caches split the difference with set-associative designs.

An N-way set-associative cache divides into sets of N lines each. An address maps to a specific set (determined by the middle bits of the address), and the cache searches all N lines in that set. L1 caches are usually 8-way, L2 caches 8-16 way, and L3 caches 12-20 way.

text
Address bits: [Tag | Set Index | Byte Offset]
| 6 bits (64-byte line)
determines |
which set |
v
Set 0: [Line 0] [Line 1] ... [Line N-1] <- N-way
Set 1: [Line 0] [Line 1] ... [Line N-1]
...

Put numbers on it for a typical L1 data cache: 32 KiB, 8-way, 64-byte lines. That's 32,768 / 64 = 512 lines, grouped 8 to a set, so 64 sets. A 64-byte line needs 6 offset bits, 64 sets need 6 index bits, and everything above bit 11 is tag.

Take the address 0x7ffd12345678. The low 6 bits are 0x38, so the byte sits 56 bytes into its line. The next 6 bits, (addr >> 6) & 63, come to 25, so it lives in set 25. Now add 4 KiB to get 0x7ffd12346678. Only bits 12 and up changed, and those are all tag, so it lands in set 25 as well. Any addresses that are a multiple of 4 KiB apart compete for the same 8 ways. Walk nine arrays in step that are each page-aligned and the ninth evicts the first, even though most of the cache is sitting empty.

The simulators below show that kind of conflict on a toy cache with 8 lines of 16 bytes. Addresses 0 and 128 are exactly one cache-size apart, so in the direct-mapped version they both want set 0 and keep throwing each other out. Run the sequence: every access misses.

Sequence [0/6]:
500ms
012801280128
Hits: 0Misses: 0Rate: 0.0%

Cache Contents(Direct-Mapped, 8 lines, 16B/line)

IndexVTagData
00--
10--
20--
30--
40--
50--
60--
70--

Same lines, same addresses, but now 2-way set-associative, so set 0 has room for both. Two misses to fill the set, then four hits.

Sequence [0/6]:
500ms
012801280128
Hits: 0Misses: 0Rate: 0.0%

Cache Contents(2-Way Set Associative, 8 lines, 16B/line)

SetWay 0Way 1
0emptyempty
1emptyempty
2emptyempty
3emptyempty
Eviction Policies

When all N ways in a set are occupied and a new line must be cached, one existing line must be evicted. The most common policy is pseudo-LRU (Least Recently Used): the line that has been unused the longest is evicted. True LRU is expensive to implement in hardware, so CPUs use approximations. Some Intel L3 caches use adaptive replacement policies that blend LRU with frequency-based eviction. The eviction policy affects which data stays cached, directly impacting hit rates.

Write-Back vs Write-Through

Two strategies handle writes from the CPU.

Write-through: every write hits both the cache and main memory. Simple, always consistent, but the memory traffic is brutal. You'll find this in some embedded processors and specific cache levels.

Write-back: writes go to the cache only, and the line gets flagged as dirty. The dirty line drops back to memory only when it's evicted. Memory traffic plummets, since a hundred writes to the same line collapse into a single write-back. Almost every modern L1 and L2 cache works this way.

Inclusive vs Exclusive

Cache levels can be organised three different ways.

Inclusive: every line in L1 also lives in L2, and every line in L2 also lives in L3. Checking the L3 directory tells you whether any core has a particular line cached. Intel's L3 has traditionally been inclusive of L1/L2.

Exclusive: a line exists in exactly one cache level at a time. Promoted from L3 to L1? Then it gets yanked from L3. AMD's L3 has traditionally been exclusive, acting as a victim cache that holds only lines evicted from L2.

Non-inclusive: L3 doesn't guarantee inclusion, but doesn't explicitly exclude either. Recent Intel server chips have shifted to non-inclusive L3 designs, gaining capacity (no duplication) at the price of trickier directory tracking.

The choice affects cache capacity (inclusive caches duplicate data, eating into effective capacity) and the complexity of the coherence protocol.

Impact on Software

The cache hierarchy is invisible at the ISA (instruction set architecture) level. There are no "cache instructions" in regular code. And yet the cache shapes performance more than almost anything else. Code that walks memory sequentially, reuses data within a small working set, and avoids thrashing the cache can run 10-100x faster than code scattering accesses randomly across the address space. Knowing how the cache works is the price of admission for writing fast code.

Seeing the Levels from Software

You can find the cache boundaries without reading a spec sheet. The program below gives each node its own 64-byte line, links the nodes into one random cycle and follows the pointers. Every load has to wait for the one before it, and the prefetchers have no pattern to guess, so the time per load tracks whichever level the working set fits in.

Try itRun it and find the working-set sizes where the time per load jumps: those are the edges of L1, L2 and L3.
C (GCC 9.2.0)

Expect a flat stretch while everything fits in L1, a step up past it, a gentler climb through L2 and L3, then a much bigger jump once the walk spills into DRAM. The sizes depend on the machine running your code, and at -O0 each hop carries some loop overhead, so read the steps rather than the absolute numbers. If the last rows haven't jumped yet, that server's L3 is bigger than 32 MiB.