Lesson 7: The Memory Hierarchy & Cache Architecture

Introduction: a very fast CPU is useless if it waits forever on memory

Lesson 6 built a highly sophisticated out-of-order CPU — but however many reservation stations it has, every LW/SW instruction (Lesson 3) still has to reach main memory (DRAM) in the end. The problem: DRAM is hundreds of times SLOWER than the CPU — this is the Memory Wall . The answer is not to make DRAM faster (physics will not allow that cheaply) but to insert a small, extremely fast, extremely expensive layer of SRAM between the CPU and DRAM — called a Cache.

1. The memory wall & the principle of locality

CPU speed has risen faster than DRAM speed for decades — that gap is the memory wall. Before looking at how a cache works, look at the whole picture: a computer's memory is not ONE thing but a stack of tiers, each trading capacity for speed along exactly the SRAM/DRAM line drawn above:

A cache "hides" DRAM latency by exploiting 2 statistical rules that hold ALMOST ALWAYS for real programs:

• Temporal Locality — an address just accessed tends to be accessed AGAIN in the near future (a loop counter, for instance).
• Spatial Locality — if address X was just accessed, addresses NEAR X (in the same cache line) tend to be accessed SOON (walking an array in order, for instance).

2. Cache mapping: direct-mapped & set-associative

A memory address is split into 3 parts for the cache lookup: Offset (the lowest bits, selecting a byte WITHIN the cache line), Index (selecting the LINE or set in the cache), and the Tag (everything left, used to CONFIRM this really is the data you wanted rather than other data sharing the same index).

function splitAddress(address, offsetBits, indexBits) {
  const offset = address & ((1 << offsetBits) - 1);
  const index = (address >>> offsetBits) & ((1 << indexBits) - 1);
  const tag = address >>> (offsetBits + indexBits);
  return { tag, index, offset };
}
// Verified: splitAddress(0x1234, 4, 2) -> offset=0x4; recombining gives back the address

Direct-Mapped: each index maps to EXACTLY 1 cache line — simple and extremely fast to look up, but 2 addresses with different tags sharing an index will keep evicting each other even while other lines sit empty (aConflict Miss). Set-Associative N-way: each index maps to a SET of N lines — addresses sharing an index but differing in tag no longer fight over one slot, and LRU (least recently used) decides which line is replaced once the set is full.

// 2 addresses with the SAME index but DIFFERENT tags, alternating 10 times (20 accesses):
// addrA = 0, addrB = numSets * lineSize (same index as A)
const dm = makeDirectMappedCache(4, 4);   // direct-mapped: 20/20 MISS (100%!)
const sa = makeSetAssociativeCache(4, 2, 4); // 2-way: only 2/20 MISS (10%)
// Set-associative holds BOTH addresses at once in the SAME set

3. The cache performance metric: AMAT

The average memory access time with 1 level of cache:

$$AMAT = T_{Hit} + \text{MissRate} \times T_{MissPenalty}$$

With a 2-level L1+L2 system the formula extends — missRateL2Local is the LOCAL miss rate of L2 (counted only over the accesses where L1 ALREADY missed, not over all program accesses):

$$AMAT = T_{HitL1} + \text{MissRateL1} \times (T_{HitL2} + \text{MissRateL2}_{local} \times T_{MissPenalty\_DRAM})$$

Verified for real (the classic Patterson & Hennessy example): $T_{HitL1}=1$, MissRateL1=2%, $T_{HitL2}=10$, LOCAL MissRateL2=25%, DRAM penalty=200 cycles → $AMAT = 1 + 0.02 \times (10 + 0.25 \times 200) = \mathbf{2.2}$ cycles.

function amat(hitTime, missRate, missPenalty) {
  return hitTime + missRate * missPenalty;
}
function amatTwoLevel(hitTimeL1, missRateL1, hitTimeL2, missRateL2Local, missPenaltyMem) {
  return hitTimeL1 + missRateL1 * (hitTimeL2 + missRateL2Local * missPenaltyMem);
}
// Verified: amat(1, 0.05, 100) = 6
// Verified: amatTwoLevel(1, 0.02, 10, 0.25, 200) = 2.2 (the classic P&H example)

// An 8x8 array of 4-byte elements, cache of 4 lines x 16 bytes/line (64 bytes total)
const rowMajorAddrs = []; // walk: for row { for col { addrOf(row,col) } }
const colMajorAddrs = []; // walk: for col { for row { addrOf(row,col) } }

runCacheTrace(makeDirectMappedCache(4, 4), rowMajorAddrs); // 16/64 miss (25%)
runCacheTrace(makeDirectMappedCache(4, 4), colMajorAddrs); // 64/64 miss (100%!)
// The SAME elements are accessed - only the ORDER differs - yet 4x the miss rate

4. When the CPU WRITES: write-through & write-back

Everything so far has been about READING. But real programs write too — every sw (store word) instruction is a write. And this question has no obvious answer: when the CPU writes to an address that IS already in the cache, does the DRAM underneath get updated right away?

Two choices, and they split every cache design in existence down the middle:

• Write-Through — write to the cache AND straight down to DRAM immediately. DRAM is always correct, the design is simple, nothing extra to track. In exchange: EVERY store costs a trip to DRAM.
• Write-Back — write only to the cache, and set a marker bit on that line called the dirty bit (meaning "this line has been modified, DRAM is now stale"). Only when that line is EVICTED (or at the very end) does the write actually go down to DRAM. Writing 100 times to the same variable costs EXACTLY 1 trip to DRAM.

There is a follow-up question: what if the write MISSES (the address is not in the cache yet)? Write-Allocate loads the line into the cache first and then writes (a good fit for write-back, since the following writes will hit); No-Write-Allocate writes straight to DRAM and loads nothing (a good fit for write-through, since loading the line would not save a single write anyway). That is why these two pairs almost always travel together.

This is the easiest place in the lesson to get wrong, so measure rather than believe. The scenario: accumulate into ONE variable 10 times — each round a read then a write to the same address, 20 accesses in total:

// Accumulate into ONE variable 10 times: read then write, same address
const accesses = [];
for (let i = 0; i < 10; i++) {
  accesses.push({ address: 0, isWrite: false }); // lw
  accesses.push({ address: 0, isWrite: true });  // sw
}

runWriteTrace(makeWritePolicyCache(4, 2, 4, { writePolicy: 'through' }), accesses);
// -> { hits: 19, misses: 1, memWrites: 10 }   every store goes down to DRAM

runWriteTrace(makeWritePolicyCache(4, 2, 4, { writePolicy: 'back' }), accesses);
// -> { hits: 19, misses: 1, memWrites: 1 }    one dirty line, written back once

// Same hit rate. 10x the DRAM traffic. That is the whole trade-off.

5. Not every miss is the same: the 3C taxonomy

We have now met two scenarios that both fail badly: the column walk missing 100%, and two contending addresses also missing 100%. But those are two DIFFERENT diseases with two different cures. Collapsing them into a single "miss rate" throws away exactly the information you need to fix them. The standard classification (Hill, 1989) splits misses into three kinds — known as the 3C:

• Compulsory — the FIRST time the program touches a block. No cache avoids these, not even an infinite one: data that has never been loaded must be loaded. Reduced by larger cache lines or by prefetching (loading before the data is needed).
• Capacity — the block WAS in the cache but got evicted because the working set is simply larger than the cache. Cured by a BIGGER cache, and by nothing else.
• Conflict — the cache still has free room, but the block was evicted because it contended for that exact set with another block. Cured by raising ASSOCIATIVITY — precisely the effect measured in section 2.

You measure this by comparing the real cache against two imaginary ones: an infinite cache (leaving only compulsory misses) and a fully-associative cache of the same capacity (compulsory + capacity). Whatever is left over is conflict:

// The conflict trace from section 2, on a direct-mapped cache
classifyMisses(conflictSeq, 4, 1, 4);
// -> { total: 20, compulsory: 2, capacity: 0, conflict: 18 }   almost all conflict
classifyMisses(conflictSeq, 4, 2, 4);
// -> { total:  2, compulsory: 2, capacity: 0, conflict:  0 }   2-way cured it

// The column-major walk from section 1, SAME cache, also ~100% miss
classifyMisses(colMajorAddrs, 4, 1, 4);
// -> { total: 64, compulsory: 16, capacity: 48, conflict: 0 }  NOT conflict at all
// More associativity would fix nothing here. Only a bigger cache would.

6. Hands-on: an L1 cache simulator

The address splitter below computes tag/index/offset directly from any hex address you type. The hit/miss simulator runs the 4 scenarios verified above — switch between direct-mapped and set-associative to watch the conflict misses disappear for yourself:

Three things worth trying rather than just looking at: (1) keep the address 0x1234 and change the offset bits from 4 down to 2 — how do index and tag shift, and why does a smaller cache line make the tag longer? (2) run the COLUMN scenario and read the hit/miss trace: not a single H, exactly as the 3C taxonomy said, because these are capacity misses. (3) switch between the last two conflict scenarios and compare traces: the point where M M M M… turns into M M H H H… is the moment the second way starts holding both addresses at once.

Summary

• ✅ A cache hides the memory wall by exploiting temporal and spatial locality — it does not make DRAM faster, it reduces how often you must REACH DRAM at all.
• ✅ Verified: walking BY ROW (good locality) misses only 25%; BY COLUMN (locality lost) misses 100% — 4 times worse for the same elements.
• ✅ Direct-mapped is simple but prone to conflict misses (verified: 100% miss with 2 addresses sharing an index); 2-way set-associative all but eliminates it (verified: only 10% miss).
• ✅ Verified: 2-level $AMAT$ (2% L1 miss, L2 hit=10, 25% local L2, DRAM penalty=200) = 2.2 cycles.
• ✅ Pitfall: the local miss rate (25%) and the global one (0.5%) are two entirely different numbers — do not confuse them.
• ✅ Write policy: verified on the same access trace, write-through goes down to DRAM 10 times while write-back goes once — at an IDENTICAL hit rate (19/20). Judging write-back by hit rate is measuring the wrong axis.
• ✅ The 3C taxonomy: verified, the conflict trace is 2 compulsory + 18 conflict (2-way wipes them out), while the column walk is 16 compulsory + 48 capacity + 0 conflict — the same high miss rate, two opposite cures.

One link has stayed hidden through this whole lesson. The cache looks up by index and tag cut out of an address — but whichaddress? Your program only knows the virtual address the operating system handed it, while DRAM only understands physical addresses. Who translates between them, when, and if the translation itself needs a table that lives in memory, does that not cost another trip to DRAM on every single access? That is exactly the problem Lesson 8 solves, with a second cache dedicated to caching address translation — the TLB.

Review quiz