Caches and the memory hierarchy
Keeping the data you need within reach
A cache is a small, fast memory that holds recently and nearby-used data so the processor can avoid the slow trip to main memory, and the memory hierarchy is the stack of register, cache, DRAM, and disk levels that keeps the data most likely to be needed in the fastest level that can hold it.
You built RAM as a bank of registers behind an address decoder, and it works, but there is a problem the diagrams hide: real main memory (DRAM) is slow compared with the CPU. A processor can run a hundred or more operations in the time one DRAM access takes to come back. If every instruction had to wait on memory, all the gates and registers you assembled would sit idle most of the time. A cache is the fix: a small, fast memory that keeps copies of the data the CPU is using right now, so most accesses never reach the slow bus to DRAM.
The memory hierarchy
Fast memory is expensive and small; cheap memory is large and slow. You cannot have all three of fast, big, and cheap, so a computer uses layers, each larger and slower than the one above it. The CPU looks in the top layer first and only drops to a lower one on a miss. The trick is to arrange things so it rarely has to.
| Level | Typical size | Typical access time |
|---|---|---|
| Registers | under a kilobyte | 0 cycles (in the datapath) |
| L1 cache | tens of KB | about 1 to 4 cycles |
| L2 cache | hundreds of KB | about 10 cycles |
| L3 cache | several MB | about 40 cycles |
| DRAM (main memory) | gigabytes | about 200 cycles |
| Disk or SSD | terabytes | millions of cycles |
Why it works: locality
A cache only helps if the data it holds is the data you ask for next. That bet pays off because real programs have locality, two everyday patterns in how they touch memory:
- Temporal locality: if you used an address recently, you are likely to use it again soon. A loop counter, a running total, the top of a stack: the same few locations get hit over and over.
- Spatial locality: if you used an address, you are likely to use its neighbours soon. Walking through an array, executing instructions in order: accesses cluster together in nearby addresses.
Locality is the single assumption all of memory-system design rests on. Temporal locality is why keeping a *recent* copy is worth it; spatial locality is why a cache fetches a whole block of neighbouring bytes on a miss, not just the one byte asked for, so the neighbours are already present when you reach them.
Lines, hits, and misses
A cache does not store single bytes; it stores lines (also called blocks), a fixed run of neighbouring bytes (say 16 or 64). When the CPU requests an address, the cache checks whether the line containing it is present. A hit means yes, served at cache speed (the hit time). A miss means no: the cache must fetch the whole line from the next level down, which costs the miss penalty, then hand over the byte. The fraction of accesses that miss is the miss rate.
Where can a block go?
When a line is fetched, where in the cache does it land? Three policies trade lookup cost against flexibility:
- Direct-mapped: each memory block maps to exactly one cache line (by its address). Lookup is one comparison, but two hot blocks that map to the same line evict each other repeatedly (a conflict miss), even when the rest of the cache is empty.
- Fully-associative: a block may sit in any line. No conflict misses, but every lookup must compare against every line, which is expensive in hardware.
- Set-associative: the middle ground used in practice. The cache is split into sets; a block maps to one set (like direct-mapped) but may occupy any of the N lines in that set (N-way associative). A 4-way cache compares 4 tags per lookup and tolerates a few colliding blocks.
Splitting the address: tag, index, offset
To find a block, the cache slices the address into three fields. The low bits pick the byte inside a line; the middle bits pick which line (or set) to look in; the top bits are the tag stored alongside the line to confirm it is really the block you wanted.
Take a direct-mapped cache with 8 lines of 16 bytes each, and 16-bit addresses. The offset needs
log2(16) = 4 bits, the index needs log2(8) = 3 bits, and the tag is whatever is left: 16 - 4 - 3 = 9 bits.| Field | Address bits | Width | What it selects |
|---|---|---|---|
| Tag | 15..7 | 9 bits | confirms which block is stored in the line |
| Index | 6..4 | 3 bits | which of the 8 lines to look in |
| Offset | 3..0 | 4 bits | which byte inside the 16-byte line |
Decode address
0x1234 (binary 0001 0010 0011 0100) with this split:- Offset = low 4 bits =
0100=4. So this is byte 4 within its line. - Index = next 3 bits =
011=3. Look in cache line 3. - Tag = top 9 bits =
0 0010 0100=36. Compare against the tag stored in line 3: if it matches and the line is valid, it is a hit. - Check:
36 x 128 + 3 x 16 + 4 = 4608 + 48 + 4 = 4660 = 0x1234, the address recombines.
Replacement and writes
In a set-associative cache, when a set is full and a new block arrives, something must be evicted. The common policy is LRU (least-recently-used): throw out the line that has gone untouched the longest, betting (by temporal locality) it is least likely to be needed again. On a write, two policies decide when main memory is updated. Write-through writes to both the cache and memory every time, keeping memory always current but generating traffic. Write-back writes only to the cache, marks the line dirty, and copies it to memory only when that line is evicted, which is far less traffic but means memory is temporarily stale.
Common mistakes. The offset width comes from the line (block) size, not the word size, so a bigger line means more offset bits and fewer index bits. A bigger cache does not always cut misses: a small direct-mapped cache can thrash on two colliding hot blocks while most lines sit empty, which is why associativity exists. And write-through versus write-back is not about correctness, both are correct; it is about *when* memory catches up and how much bus traffic that costs.
Putting a number on it: AMAT
The headline metric is average memory access time (AMAT): you always pay the hit time to check the cache, and on the fraction of accesses that miss you also pay the miss penalty.
AMAT = hit time + miss rate x miss penalty
Suppose the hit time is
1 cycle, the miss rate is 5% (0.05), and a miss costs 100 cycles to fetch the line from DRAM. Then AMAT = 1 + 0.05 x 100 = 1 + 5 = 6 cycles. A 5% miss rate may sound small, but because a miss is so expensive it still multiplies the average access from 1 cycle to 6. That is why hardware works hard to push the miss rate down, and why adding an L2 between L1 and DRAM (a smaller miss penalty for L1 misses that hit in L2) is worth the silicon.Try it
A direct-mapped cache has 64 lines of 32 bytes each, addressed with 20-bit addresses. How many bits are the offset, index, and tag? Then, if a hit takes 2 cycles, the miss rate is 4%, and a miss costs 80 cycles, what is the AMAT?
Answer
Offset =
log2(32) = 5 bits (the line is 32 bytes). Index = log2(64) = 6 bits (there are 64 lines). Tag = 20 - 5 - 6 = 9 bits. AMAT = 2 + 0.04 x 80 = 2 + 3.2 = 5.2 cycles. The 4% of accesses that miss add 3.2 cycles on average, more than doubling the 2-cycle hit time.Caches are why the fast machine you built is not starved by slow memory. They add no new logic idea, just storage placed cleverly between the registers and RAM you already understand, exploiting locality to make the common case fast. They are also the clearest example of the speed-versus-cost tradeoffs that the performance lesson turns into an equation, and a partner to pipelining, which hides latency by overlapping work rather than by storing copies.
Frequently asked
What is a CPU cache?
A cache is a small, fast memory that holds copies of recently and nearby-used data so the processor avoids the slow trip to main memory (DRAM). It sits between the registers and RAM, and most accesses are served from it at a fraction of DRAM's latency.
What is the difference between temporal and spatial locality?
Temporal locality is reusing the same address soon after using it (a loop counter, a running total). Spatial locality is using addresses near one you just used (walking an array, fetching instructions in order). Caches exploit temporal locality by keeping recent data and spatial locality by fetching a whole block of neighbours on a miss.
What is the difference between direct-mapped and set-associative caches?
In a direct-mapped cache each block has exactly one possible line, so lookup is one comparison but two blocks that map to the same line keep evicting each other. A set-associative cache lets a block sit in any of N lines within its set, tolerating collisions at the cost of N comparisons per lookup. Fully-associative (a block anywhere) removes conflicts entirely but is the most expensive.
How do you split an address into tag, index, and offset?
The low bits are the offset (
log2 of the line size in bytes), selecting a byte inside the line. The next bits are the index (log2 of the number of lines or sets), selecting where to look. The remaining high bits are the tag, stored with the line to confirm a hit. For an 8-line, 16-byte cache with 16-bit addresses: 4 offset, 3 index, 9 tag.How do you calculate average memory access time (AMAT)?
AMAT = hit time + miss rate x miss penalty. You always pay the hit time to probe the cache, and the fraction of accesses that miss also pays the penalty to fetch from the next level. For a 1-cycle hit, 5% miss rate, and 100-cycle penalty: 1 + 0.05 x 100 = 6 cycles.Every lesson here builds toward one thing: a working CPU, from the transistor up.
Open the free lab →Builds towardVirtual memory