The Memory Hierarchy: Caches, Virtual Memory, and the Memory Wall

Lesson 1, Part 7 built a pipelined datapath and confronted the hazards that come with it. Now let's move from computation to storage: none of that pipeline throughput matters if every instruction stalls waiting for data to arrive from memory.

1. Why Memory Is a Hierarchy, Not a Single Thing

Start with the assumption everyone quietly makes: "memory" is one thing with one speed. It isn't, and it can't be, for a reason rooted in physics rather than engineering taste.

A memory cell that is fast has to be built from more transistors and more wiring per bit — SRAM cells (6 transistors each, holding state in cross-coupled inverters) are physically bigger and burn more static power than DRAM cells (1 transistor + 1 capacitor per bit). A bigger, more complex cell array also means longer wires to reach any given bit, and wire delay does not shrink just because you want it to. So there is a real physical tradeoff:

SmallAndFast XOR LargeAndSlow — you cannot cheaply get both in the same technology.

Given that constraint, the natural engineering response is not to pick one point on the tradeoff curve — it's to build several layers, each optimized for a different point, and let data migrate between them automatically.

CPU
 │
 ▼
Registers   (tens of bytes,   ~1 cycle,        built into the datapath)
 │
 ▼
L1 cache    (tens of KB,      ~4 cycles,       SRAM, per-core)
 │
 ▼
L2 cache    (hundreds of KB,  ~12 cycles,      SRAM, per-core or shared)
 │
 ▼
L3 cache    (tens of MB,      ~40 cycles,      SRAM, shared across cores)
 │
 ▼
DRAM        (tens of GB,      ~200 cycles,     off-chip, 1T1C cells)
 │
 ▼
SSD / disk  (TBs,             ~10,000-100,000+ cycles, flash / NAND)

A representative modern hierarchy (exact numbers vary by vendor and generation, but the shape is universal):

The key first-principles idea:

Fast memory is expensive and physically constrained to be small. Large memory is necessarily built from slower, denser technology. A hierarchy lets software experience something close to "the size of DRAM at the speed of registers" — but only if the access pattern cooperates.

That last clause is the entire subject of this chapter.

2. Why Caches Work: Locality Is an Empirical Law, Not a Guarantee

Caches are a bet. The bet is that programs don't access memory uniformly at random — they cluster their accesses in ways that are predictable a fraction of a second in advance. This clustering is called locality, and it comes in two flavors.

2.1 Temporal locality

If an address was accessed recently, it is likely to be accessed again soon.

x = A[10];
// ... some other work ...
x = A[10];   // same address, reused shortly after

Loop counters, accumulator variables, and hot function-local state are the textbook cases.

2.2 Spatial locality

If one address was accessed, nearby addresses are likely to be accessed soon.

A[0]
A[1]
A[2]
A[3]

Arrays traversed in order, struct fields accessed together, and instruction fetch (code executes mostly sequentially) are the textbook cases.

2.3 Why this justifies fetching in blocks

Because of spatial locality, a cache never fetches a single byte or word from DRAM. It fetches a whole aligned block called a cache line — commonly 64 bytes on modern x86 and ARM cores. Ask for A[0] (a 4-byte int), and the cache pulls in A[0] through A[15] in one DRAM transaction (16 ints × 4 bytes = 64 bytes), betting that you'll touch the rest of that line soon. If your access pattern really is sequential, this converts many potential misses into one miss and fifteen guaranteed hits.

This single design decision — amortize one slow DRAM access across many fast cache hits by moving data in blocks — is responsible for a huge fraction of real-world performance behavior, and for a huge fraction of real-world performance bugs (see Drepper's paper, cited below, for exhaustive detail on getting this wrong).

A cache is a bet on locality. Sequential, blocked, reused access patterns win the bet. Pointer-chasing, random-stride, or single-pass-huge-working-set access patterns lose it — and the loss is not small. It is often the entire difference between a kernel running at hardware peak and running at 5-10% of peak.

3. The Cache Address Breakdown, Derived From First Principles

This is the part of cache design that becomes mechanical once you set it up correctly, so let's set it up correctly.

3.1 The three questions a cache must answer

Given a memory address, a cache controller must answer, in order:

1. Offset — within the cache line that holds this address, which byte do I want?
2. Index — which set (group of cache lines) should hold this address?
3. Tag — of the several blocks that could map to that set, which one is actually sitting there right now (or is it a miss)?

The address is decomposed into three contiguous bit-fields:

Every bit-field width is derived, not chosen freely, once you fix three design parameters: CacheSize, LineSize, and Associativity (ways per set).

3.2 Worked example: 32 KB, 8-way set-associative, 64-byte lines

This is a realistic modern L1 data cache configuration (close to several real Intel/AMD/ARM L1Ds). Let's derive every field width from scratch.

Step 1 — offset bits. The offset must be able to address every byte within one cache line.

LineSize = 64 bytes
OffsetBits = log2(LineSize) = log2(64) = 6 bits

Check: 6 bits addresses 2^6 = 64 distinct byte positions. Correct.

Step 2 — number of sets. A cache is organized as NumSets sets, each holding Associativity lines ("ways"). The total capacity is:

CacheSize = NumSets × Associativity × LineSize

Rearranged:

NumSets = CacheSize / (Associativity × LineSize)

Plugging in numbers:

CacheSize     = 32 KB = 32,768 bytes
Associativity = 8
LineSize      = 64 bytes
 
NumSets = 32,768 / (8 × 64)
        = 32,768 / 512
        = 64 sets

Step 3 — index bits. The index must select one of NumSets sets.

IndexBits = log2(NumSets) = log2(64) = 6 bits

Step 4 — tag bits. Everything left over identifies which specific memory block (of all the blocks that could alias to this set) is currently resident. On a 48-bit virtual address space (typical for current x86-64/ARM64 implementations, even though the architectural field is wider):

AddressBits = 48
TagBits     = AddressBits − IndexBits − OffsetBits
            = 48 − 6 − 6
            = 36 bits

Putting it together:

On every access, hardware does the following in parallel, on the critical path of essentially every load instruction:

1. Split the address into Tag | Index | Offset using the widths above.
2. Use Index to select one of the 64 sets.
3. Compare the incoming Tag against the tags of all 8 ways in that set (in parallel, using 8 comparators).
4. If exactly one way matches AND its valid bit is set → HIT.
     Use Offset to select the byte(s) within that way's 64-byte line.
5. If no way matches → MISS.
     Fetch the 64-byte line from the next level down, install it in one of
     the 8 ways of that set (evicting something if all 8 are occupied and valid),
     then retry.

The index bits are not "chosen" by the tag/index/offset split — they are the low-order bits of the address, immediately above the offset. This is deliberate: consecutive cache lines land in consecutive sets, which spreads sequential access patterns evenly across the whole cache instead of hammering one set.

4. Direct-Mapped vs. Set-Associative vs. Fully-Associative

The Associativity parameter in the formula above isn't cosmetic — it is the single biggest lever on conflict behavior, and it trades hardware cost against miss rate in a very concrete way.

4.1 Direct-mapped (associativity = 1)

Every memory block maps to exactly one possible cache line: Index = (Address / LineSize) mod NumSets. Lookup is trivial — one tag comparator, one line to check — which makes direct-mapped caches fast and cheap in hardware. But it has a sharp failure mode.

Conflict-miss example. Suppose two arrays A and B, each larger than the cache, happen to be allocated such that A[i] and B[i] map to the same set (this happens whenever their base addresses differ by a multiple of NumSets × LineSize — a distressingly common coincidence with power-of-two strides, e.g. both allocated at the start of separate 4 KB-aligned pages when the cache is a power-of-two size). Now run:

for (int i = 0; i < N; ++i)
    C[i] = A[i] + B[i];

Every iteration: load A[i] (installs into set S), then load B[i] (maps to the same set S, evicts A[i]'s line). Next iteration wants A[i+1], which is probably still in the line just evicted's neighborhood — but the line is gone. The cache thrashes on one set while the other 63 sets sit idle, even though the working set per iteration is tiny. This is a conflict miss: a miss caused not by the data being genuinely too large for the cache (a capacity miss) nor by first-touch (a compulsory miss), but purely by an unlucky mapping.

4.2 Fully-associative (associativity = NumLines)

The opposite extreme: any memory block can go in any line, anywhere in the cache. There is no index field at all — the entire non-offset address is the tag, and every line's tag must be compared in parallel on every access.

This eliminates conflict misses entirely (a miss only happens from compulsory or capacity reasons), but the cost is a comparator per line. For a 32 KB / 64-byte-line cache that's 512 lines and 512 parallel tag comparators — power and area explode, and it stops being practical much beyond a few dozen entries. This is why fully-associative structures show up for small things (TLBs, victim caches) but essentially never for a full L1/L2/L3.

4.3 Set-associative — the pragmatic middle

Set-associative is literally "N direct-mapped caches operating in parallel, one per way, sharing an index." It needs Associativity comparators (8 for our worked example, not 512), and it converts most conflict misses into ordinary capacity misses because a set can hold several competing blocks simultaneously instead of exactly one.

Associativity is the hardware's answer to "what if the workload's stride is unlucky." Every additional way removes a class of pathological worst-case access patterns, at a real and non-negotiable cost in comparators, power, and hit latency (more ways to check = slightly slower hit path). Real designs converge on 4-16 ways as the practical sweet spot.

5. Replacement Policy: What Gets Evicted

Associativity only defers the eviction question — once all Associativity ways in a target set are occupied and valid, something has to leave to make room for the incoming line. Which one leaves is the replacement policy, and it matters because a bad choice throws away data that was about to be reused.

5.1 True LRU (Least Recently Used)

The ideal policy is exactly what its name says: evict whichever line in the set was accessed longest ago, on the theory that recency predicts future reuse (this is just temporal locality applied to eviction). It works well empirically. The problem is implementing it exactly.

For an N-way set, tracking a total order of recency among N items in general requires log2(N!) bits of state per set (updated on every access to that set, not just misses). For 8-way that's log2(8!) = log2(40320) ≈ 15.3 bits — awkward, and the update logic touches every way's state on every hit, adding latency to the hottest path in the whole memory system.

5.2 Pseudo-LRU (PLRU) — what hardware actually implements

Because exact LRU is expensive to track and update at speed, real CPUs almost universally implement an approximation. The most common scheme is tree-based pseudo-LRU: for an N-way set, keep N-1 single bits arranged as a binary tree, each bit recording "which half of this subtree was accessed more recently." A lookup walks the tree from the root, and each bit is flipped to point away from the way just accessed. Eviction walks the tree following the bits as they currently point, landing on an approximately-least-recently-used way.

For 8-way associativity this needs only 7 bits per set instead of ~15, and both the update and the eviction-selection are simple bit-flips/comparisons rather than a full re-sort. It is not always exactly LRU — it can occasionally evict something slightly more recent than the true LRU line — but empirically the miss-rate penalty versus true LRU is small (typically well under 1 percentage point of miss rate), which is a very good trade for the hardware savings. Some designs use even cheaper approximations (NRU — not-recently-used, a single bit per line; or random replacement, which is surprisingly competitive at high associativity and trivial in hardware).

True LRU is optimal but expensive to track exactly at hardware speed. Pseudo-LRU is the standard real-world compromise: a few bits of tree state per set buy nearly all of LRU's benefit at a fraction of the bookkeeping cost. This is the same "good enough approximation beats exact-but-expensive" theme that recurs throughout microarchitecture — branch predictors and prefetchers make the same trade.

6. Write Policies: What Happens on a Store

Everything above concerns loads. Stores raise a second, independent set of questions: when a CPU writes to an address, does the write go to the cache only, or all the way to DRAM? And what happens if the write misses — the line isn't cached at all?

6.1 Write-through vs. write-back

Write-through: every store updates the cache line and immediately propagates to the next level (and ultimately DRAM). Simple, and it keeps memory always consistent with the cache — useful for multi-core coherence and for devices that snoop memory directly. But it turns every store into a DRAM transaction, which defeats much of the purpose of caching for write-heavy code, so it is usually paired with a write buffer to avoid stalling the CPU on every store.

Write-back: a store updates only the cache line and marks it dirty (one extra bit per line). The line is written back to the next level only when it is evicted (or explicitly flushed). This is what essentially all modern L1/L2/L3 caches do, because it turns N stores to the same line into exactly one eventual DRAM write instead of N — another instance of exploiting temporal locality, this time on writes.

The cost of write-back is complexity: on eviction, a dirty line must be written back before the space can be reused (a "victim write-back"), and in a multi-core system, another core reading the same address from DRAM would see stale data unless a cache-coherence protocol (MESI and its relatives — beyond this chapter's scope, but built directly on top of the dirty bit) intervenes.

6.2 Write-allocate vs. no-write-allocate

Independently: what happens on a store that misses — the address isn't cached at all yet?

Write-allocate: fetch the line into the cache first (like a read miss), then apply the write to the now-resident line. This pairs naturally with write-back, on the bet that a location just written to will likely be read or written again soon.

No-write-allocate (write-around): write the data straight to the next level, without pulling the line into the cache. This pairs naturally with write-through, and makes sense for data unlikely to be reread soon — e.g. streaming output buffers.

Write-back + write-allocate wins by default in general-purpose CPUs because most write-heavy code re-reads or re-writes what it just touched (temporal locality again). But the "streaming write, never reread" pattern is common enough in practice — memcpy of huge buffers, video encode output — that real ISAs expose explicit non-temporal store instructions (e.g. MOVNTI on x86) precisely to opt out of the default and avoid cache pollution.

7. Virtual Memory: A Second Address Space Stacked on Top

Everything so far assumed the CPU's addresses are physical DRAM addresses. They almost never are. Every load and store a user-space program issues is a virtual address, and hardware plus the OS cooperate to translate it before it ever reaches a cache or DRAM.

Virtual Address (what the program computes)
      ↓
     TLB  ── (fast path: translation already cached)
      ↓  (miss)
Page Table  ── (walked by hardware or OS)
      ↓
Physical Address
      ↓
   Cache (indexed/tagged using the physical — or sometimes virtual — address)
      ↓
    DRAM

A virtual address decomposes analogously to the cache address split, but for a different reason — page granularity rather than cache-line granularity:

VA = VPN ‖ PageOffset

where VPN (virtual page number) is translated by the page table into a PPN (physical page number), and the offset within the page passes through untouched (pages are aligned, so the low bits of virtual and physical addresses are identical):

PPN = PageTable[VPN] PA = PPN ‖ PageOffset

7.1 Why not a single flat page table? The arithmetic that forces multiple levels

The naive design: one giant array, indexed by VPN, where PageTable[VPN] directly stores the PPN (plus permission bits). Let's compute how big that array would have to be for a modern 64-bit address space with 4 KB pages.

PageSize        = 4 KB = 2^12 bytes → PageOffset = 12 bits
VirtualAddrBits = 48 bits (current x86-64 / ARM64 implementations, not the full 64)
VPN bits        = 48 − 12 = 36 bits
NumPages        = 2^36 ≈ 68.7 billion pages
 
Assume each page-table entry (PTE) is 8 bytes (PPN + permission/dirty/present bits):
 
FlatTableSize = NumPages × 8 bytes
              = 2^36 × 8
              = 2^36 × 2^3
              = 2^39 bytes
              = 549,755,813,888 bytes
              ≈ 512 GB

Half a terabyte of page table — per process — just to describe its address space, most of which is unused, sparse, wasted mapping-table space for a program that might only touch a few megabytes. This is the arithmetic that makes a single-level, flat page table absurd, and it's the reason every real 64-bit system uses a multi-level (hierarchical) page table instead.

7.2 Multi-level page tables — pay only for what's mapped

The idea: split the 36-bit VPN into several smaller indices, each selecting an entry in a smaller table, and only allocate the lower-level tables for regions of the address space that are actually in use. x86-64 with 4-level paging is the canonical real example:

Virtual Address (48 bits) = PML4[9] ‖ PDPT[9] ‖ PD[9] ‖ PT[9] ‖ Offset[12]
                              9+9+9+9+12 = 48 bits ✓

Each level is a table of 2^9 = 512 entries, and — critically — each entry is 8 bytes, so each level's table is exactly 512 × 8 = 4096 bytes = 4 KB: one page. Walking a translation means four sequential dependent memory reads (one per level), each a single 4 KB page:

1. Read PML4 table (1 page, always resident for the process) at PML4[VA bits 47:39]
     → gives physical address of the PDPT for this region
2. Read PDPT at PDPT[VA bits 38:30]
     → gives physical address of the PD for this region
3. Read PD at PD[VA bits 29:21]
     → gives physical address of the PT for this region
4. Read PT at PT[VA bits 20:12]
     → gives the PPN itself
5. PA = PPN ‖ Offset[11:0]

If a whole 512-entry branch of the tree is unused (e.g. a huge swath of unmapped address space between the heap and the stack, which is normal), the corresponding lower-level tables simply don't exist — that pointer is null. Sparse regions cost nothing. This is the direct structural fix to the 512 GB flat-table problem: pay per mapped region, not per possible address.

The cost: a full walk on a cold miss is 4 dependent DRAM accesses before the "real" access even happens — potentially 4× ~100 ns ≈ 400 ns just for translation, before the actual load or store. That cost is exactly what the next piece exists to hide.

7.3 The TLB — caching translations, because walking the tree every time would be ruinous

The Translation Lookaside Buffer is, structurally, just another cache — but instead of caching data, it caches recent VPN → PPN translations, keyed by VPN, typically fully- or highly-associative because it's small (tens to low hundreds of entries) and misses are so expensive that minimizing conflict misses matters more than lookup cost.

• TLB hit: the translation is available in ~0-1 cycles (parallel with, or ahead of, the cache access) — effectively free.
• TLB miss: the hardware (on x86, a hardware page-table walker; on some RISC/MIPS-style designs, a trap into OS software) performs the full multi-level walk described above — hundreds of cycles — then installs the result in the TLB before retrying.

Because TLB entries are scarce and the walk on a miss is so expensive, TLB reach — how much address space is covered by all currently-cached translations — becomes a real performance variable: TLBReach = NumTLBEntries × PageSize. With ~1500 entries and 4 KB pages, reach is only ~6 MB; a workload that scans working sets bigger than that (which is extremely common — think a large mmap'd file, a big hash table, or a tensor arena in an edge-AI inference buffer) will constantly miss the TLB even though the data itself might be sitting comfortably in L2 or L3.

7.4 Huge pages — the real, load-bearing optimization

This is where virtual memory stops being abstract and becomes something the reader, coming from Android kernel and edge-AI memory work, has almost certainly touched directly: Linux exposes huge pages (2 MB, and on some platforms 1 GB) as an explicit alternative to the default 4 KB page, both transparently (Transparent Huge Pages / THP, which the kernel opportunistically assembles) and explicitly (via mmap with MAP_HUGETLB, or madvise(..., MADV_HUGEPAGE) hinting the kernel to promote a region).

The mechanism is the same TLB-reach arithmetic run the other direction:

4 KB pages:  TLBReach = 1536 entries × 4 KB   =    6 MB
2 MB pages:  TLBReach = 1536 entries × 2 MB   ≈    3 GB   (512× improvement)
1 GB pages:  TLBReach = 1536 entries × 1 GB   ≈  1.5 TB

A single 2 MB huge page also collapses the page-table walk itself: with a 2 MB page, the walk stops one level earlier (the PD entry directly marks "this is a 2 MB leaf," so the PT level is skipped entirely), meaning fewer TLB entries are needed to cover the same footprint and each miss that does occur is one memory access cheaper to resolve.

This is precisely why memory-bandwidth-hungry, large-working-set code — big malloc arenas, mmap'd model weights, large matrix/tensor buffers in an NPU or edge-AI runtime — benefits disproportionately from huge pages: the translation overhead that would otherwise be paid on every 4 KB boundary essentially disappears. It is also exactly why malloc implementations backing large allocations (glibc's threshold is around a few hundred KB to low MB) fall back to mmap directly rather than extending the heap via brk — a large mmap region is a natural place for the kernel to opportunistically back with THP, whereas growing the small-object heap incrementally is not.

A TLB miss is not "a cache miss" in the everyday sense — it can trigger up to four dependent DRAM accesses before the real access even starts. Huge pages are a direct, load-bearing fix: multiply TLB reach by 512× or more (2 MB vs. 4 KB), and collapse a level out of the page-table walk itself. This is one of the few pieces of computer-architecture theory that maps onto a single flag you can flip in production (MADV_HUGEPAGE, MAP_HUGETLB) and measure the win directly.

8. The Memory Wall

Zoom out from any single mechanism and look at the long-run trend line instead. For decades, CPU clock frequency and per-cycle work (superscalar width, out-of-order depth) grew rapidly. DRAM latency, by contrast, improved far more slowly — DRAM density (capacity per dollar) scaled beautifully with Moore's Law, but the physical act of activating a row, sensing a bit line, and returning data is bounded by capacitor and wire physics that didn't share in the frequency scaling.

The gap between those two curves is the memory wall: expressed in CPU cycles, a DRAM access has gone from "a handful of cycles" in early microprocessors to "hundreds of cycles" today, purely because the CPU side of the ratio kept climbing while the DRAM side stayed roughly flat. This is exactly the reasoning the entire hierarchy in Section 1 exists to fight — every level between the CPU and DRAM is an attempt to keep the effective latency the program experiences close to the fast end of that gap, as long as locality holds.

The wall changes how you should think about performance at a fundamental level. Consider:

C[i] = A[i] + B[i]

Mathematically this is one floating-point addition. But the work the memory system must do to service it — one load of A[i], one load of B[i], one store to C[i] — can easily dominate execution time, especially if the arrays are large enough to blow past cache capacity and every access is a DRAM round-trip.

Performance is, overwhelmingly often, about moving data — not about computing on it. The arithmetic is nearly free; the transport is not.

This reframing matters most exactly where the reader's own background sits: AI accelerators, GPUs, NPUs, and embedded/edge systems are all, at core, exercises in fighting the memory wall, because their compute throughput (many parallel MACs) so vastly outstrips what a naive memory access pattern can feed them.

9. Arithmetic Intensity and the Roofline Model

Given that data movement, not computation, is usually the bottleneck, we need a way to predict — before running anything — whether a given piece of code will be memory-bound or compute-bound. The tool for this is arithmetic intensity:

ArithmeticIntensity = Operations / BytesMoved

measured in FLOPs (or ops) per byte transferred to/from memory.

9.1 Worked example: elementwise add vs. matrix multiply

Elementwise add, C[i] = A[i] + B[i], in float32:

Operations per iteration = 1 (one addition)
Bytes moved per iteration:
    load A[i]  = 4 bytes
    load B[i]  = 4 bytes
    store C[i] = 4 bytes
    total      = 12 bytes
 
ArithmeticIntensity ≈ 1 / 12 ≈ 0.083 FLOP/byte

That is a very low ratio — for every byte hauled across the memory bus, less than a tenth of a floating-point operation gets done. This kernel is almost certainly memory-bound: the CPU/GPU/NPU's compute units will sit idle waiting for data, no matter how fast they can add.

Naive matrix multiply, C = A × B for N×N matrices, float32, no tiling:

Operations = 2N³ (N³ multiply-adds, counted as 2 FLOPs each)
Bytes moved (naive, no reuse) ≈ each element of A and B re-read
    O(N³) times in the innermost loop if the working set doesn't fit in cache
 
ArithmeticIntensity (naive, cache-unfriendly) can degrade toward the same
poor ratio as elementwise ops, DESPITE the O(N³) operation count, purely
because of poor reuse in the inner loop.

This is the crucial and slightly counterintuitive point: raw operation count (O(N³)) does not by itself guarantee high arithmetic intensity. A naively-written triple-nested-loop matmul with a bad loop order can be just as memory-bound as the elementwise add, because it keeps re-fetching the same rows/columns from DRAM instead of reusing what's already in cache. Tiling / blocking — restructuring the loops to operate on small sub-blocks of A, B, C that fit entirely in L1 or L2, and reusing each loaded element many times before evicting it — is precisely what converts matmul's theoretical O(N³) operations over O(N²) data into actual high arithmetic intensity in practice. Done well, tiled matmul can approach arithmetic intensity proportional to the tile dimension, pushing it firmly into compute-bound territory.

9.2 The roofline model

Plot achievable performance (FLOP/s, y-axis) against arithmetic intensity (FLOP/byte, x-axis) on log-log axes, and two hardware limits become straight lines:

• To the left of the ridge point (low arithmetic intensity): performance is capped by PeakBandwidth × ArithmeticIntensity — the sloped line. You are memory-bound; buying a faster ALU does nothing until you increase reuse.
• To the right of the ridge point (high arithmetic intensity): performance is capped by the flat peak compute line. You are compute-bound; the fix is faster arithmetic units, more parallelism, or better instruction scheduling — not memory optimization.

The elementwise add above sits far to the left — deep in memory-bound territory on essentially any hardware. A well-tiled matmul sits far to the right, near or at the compute roof.

Compute-bound vs. memory-bound is not a property of the algorithm in the abstract — it's a property of the algorithm's actual implementation on actual hardware, and arithmetic intensity is the number that tells you which regime you're in before you profile anything.

This is precisely why NPU and edge-AI kernel design obsesses over data reuse and tiling: an NPU's whole value proposition is a huge number of parallel MAC units, which only pays off if arithmetic intensity is pushed high enough (via tiling, operator fusion, weight-stationary or output-stationary dataflows) to reach the flat part of the roofline. A kernel with beautiful theoretical FLOP counts but poor tiling will simply starve the compute array waiting on DRAM — which is exactly the memory wall from Section 8, expressed as a single measurable ratio instead of a vague warning.

Further Reading

• Patterson, D. A. & Hennessy, J. L., Computer Organization and Design: The Hardware/Software Interface — the standard undergraduate treatment of cache hierarchies, address decomposition, and virtual memory.
• Hennessy, J. L. & Patterson, D. A., Computer Architecture: A Quantitative Approach — deeper treatment of associativity/replacement tradeoffs, multi-level page tables, and the roofline model's formal origins.
• Drepper, U., "What Every Programmer Should Know About Memory" (2007) — the canonical systems-programming deep dive on cache behavior, prefetching, and NUMA effects; originally serialized on LWN.net.
• MIT OpenCourseWare 6.004, Caches and the Memory Hierarchy.
• MIT OpenCourseWare 6.823, Lecture 7: Caches and Lecture 8: Caches II.
• GeeksforGeeks, "Cache Mapping Techniques" and "Multi-Level (Hierarchical) Page Tables".
• GeeksforGeeks, "Translation Lookaside Buffer (TLB) in Paging".
• NERSC, "Roofline Performance Model" — a practical reference for applying the roofline model to real kernels.

With storage and translation handled, the next question is what the CPU is actually built to execute — Lesson 1, Part 9 turns to ISA vs. microarchitecture, RISC vs. CISC, and the role of the compiler in bridging the two.