Chapter — Memory systems

1.The memory wall & locality

1.1Why a flat memory wouldn't work

A 32-bit address space points at 4 GiB of bytes. If we built that as one giant SRAM (cache-speed memory), it would be the size of a building. If we built it as DRAM and connected it directly to the CPU, every load would stall the pipeline for 100+ ns.

1.2The hierarchy

1.3Temporal & spatial locality

2.Caches from first principles

2.1The four parameters

2.2Direct-mapped (N = 1)

Each block has exactly one possible slot. Quickest tag check (one comparison), cheapest, but two hot blocks that happen to map to the same slot will keep evicting each other (conflict misses).

2.3N-way set-associative

Each block can live in any of N slots within its set. The hardware does N tag comparisons in parallel on every access. Typical N: 2, 4, 8.

2.4Fully associative (N = total blocks)

Any block can live anywhere. One set, all slots. No conflict misses ever — but tag check requires comparing against every slot in parallel. Used for tiny structures like the TLB (§6) where N is small.

2.5Address breakdown

Every memory address the CPU emits is split into three (or four) parts:

1. Byte offset picks the byte inside a word (2 bits for 4-byte words).
2. Block offset picks the word inside the block.
3. Set index picks which set to look in.
4. Tag is compared against the stored tag in each slot of that set — match + valid = hit.

2.5.1Worked example (GQ Q0)

Cache total  = 2^8 = 256 bytes = 64 words
Block size   = 8 bytes = 2 words   (b ≥ 8)
Blocks total = 64 / 2 = 32  ... wait, let's use words.
                       Actually: 256 B / 8 B = 32 blocks if b=8 bytes,
                       OR if b=8 words=32 B: 256/32 = 8 blocks.

Sticking with the GQ paper's choice (b=8 words = 32 B per block):
  Blocks total = 8
  Associativity N ≥ 8 ⇒ N = 8
  Sets S       = 8 / 8 = 1 set

Block offset = log2(8 words) = 3 bits
Byte offset  = 2 bits
Set index    = log2(1) = 0 bits  ← no set bits needed!
Tag          = 32 − 3 − 2 = 27 bits

2.6Replacement policies

When a set is full and a new block arrives, which slot do we evict?

• LRU (Least Recently Used): evict whichever slot hasn't been touched longest. Best behaviour, expensive to implement perfectly beyond 2-way.
• FIFO: evict the oldest insertion.
• Random: picks at random — surprisingly competitive and very cheap.

3.Cache calculations

3.1Hit rate & miss rate

Misses split into three flavours (the "3 C's"):

• Compulsory: first access ever to this block (cold start). Unavoidable.
• Conflict: two blocks map to the same set and keep evicting each other (DM & low-assoc only).
• Capacity: working set doesn't fit at all. Need a bigger cache.

3.2AMAT — average memory access time

Read it: "You always pay the hit time, plus, with probability MR, the cost of going to the next level."

3.3Multi-level AMAT

The recursive structure: each level's "miss penalty" is the AMAT of the next level.

3.4Worked: figuring out a cache from miss-rate fingerprint

74  A0  78  38C  AC  84  888C  7C  34  3813C  38818C

4.Virtual memory motivation

4.1The illusion of unlimited RAM

If physical RAM is 8 GiB but processes act like they have 4 GiB each, the OS+MMU must be juggling. Virtual memory:

1. Each process gets its own virtual address space (VAS) starting at 0.
2. The CPU emits virtual addresses. Assembly works in these.
3. The MMU translates virtual → physical every cycle using a page table.
4. If the physical page isn't resident, the OS pages it in from disk (a page fault).

4.2The RISC-V memory map

0xFFFFFFFC ┌──────────────────┐
           │   OS & I/O       │
0xC0000000 ├──────────────────┤
           │   Stack    ←─ sp │  grows down
           │      ↑           │
           │   Heap           │  grows up
0x10001000 ├──────────────────┤
           │   Global / Data  │
0x10000000 ├──────────────────┤
           │   Text (code)    │
0x00010000 ├──────────────────┤
           │   Exception hdr  │
0x00000000 └──────────────────┘

4.3Pages, VPN, page offset

4.3.1GQ Q29 example

1 segment = 1 page = 2·1024 words
4 segments        = 8·1024 words = 2^13 words
1 word            = 4 B = 2^2 B
Total bytes       = 2^13 · 2^2 = 2^15 bytes

5.Page tables

5.1Single-level — and why it's too big

A page table has one PTE per virtual page. PTE = { Valid bit, PPN, perm bits }.

VPN ──► PageTable[VPN] = {V, PPN, perms}
         │                     │
         └─ if V=0: page fault └─ if V=1: form PA = PPN ‖ offset

5.2Multi-level page tables

Break the VPN into chunks. Each chunk indexes a smaller table; only allocate the second-level tables for VPN ranges actually used.

• Root PT (L0) is always resident in physical memory.
• Inner PTs (L1, L2, …) live in virtual memory and can themselves be paged out.
• Address translation now costs multiple memory accesses — one per level.

5.3Sizing a multi-level PT (GQ Q0(f))

VPN bits = 32 − 13 = 19

L0 = 2^8  (X = 0 → 8, last digit)  ⇒ 8 bits
L1 = 2^6  (Y = 6, 2nd-last digit)   ⇒ 6 bits
L2 = 2^4  (Z = 4, 3rd-last digit)   ⇒ 4 bits
Running total: 8 + 6 + 4 = 18 (short by 1)

L3 = 2^1                            ⇒ 1 bit
Total: 8+6+4+1 = 19 ✓

⇒ 4 levels needed.

6.The TLB

6.1Why we need it

If every load/store needs a page-table walk (1 to 4 memory accesses), the memory system would collapse. The TLB is a tiny, fast cache that stores recent VPN → PPN translations.

6.2Full translation flow

VA ──► TLB lookup
        │
        ├─► HIT  ──► PPN ──► PA = PPN ‖ offset
        │
        └─► MISS ──► Walk page table (1 to N memory hits)
                         │
                         ├─► PTE valid: get PPN, fill TLB, retry
                         └─► PTE invalid: page fault → load from disk
                                                    │
                                                    ▼
                                              cache lookup
                                              (L1 → L2 → MM)

7.Memory performance calculations

7.1AMAT with TLB & multi-level PT

7.1.1GQ Q5 worked

Take V = 5:
  t_TLB = 5 ns
  MR_TLB = 5%
  t_MM   = 100 − 20·5 = 0 ns  ← degenerate; pick V=6 from adjacent
With V=6:
  t_MM = 100 − 120 = ??  ← also invalid; per GQ, AMAT ≈ 5 ns

7.2Memory-stall CPI

Where f = fraction of memory-touching instructions (loads + stores). This is the formula that connects memory back to the CPI math from Chapter 7 of microarchitecture.

7.2.1GQ Q4 worked

7.3Hooking back into the CPU CPI

Memory misses don't appear in our CPI_pipeline from the microarchitecture chapter — that calculation assumed 1-cycle MEM. The true CPI of a real processor combines both:

And the end-to-end timing becomes:

The next page (System Performance →) walks through a full worked example combining a pipelined CPU CPI from §7.3 of the microarch chapter with an AMAT-derived memory penalty.

Next: Combined system performance → (pipeline + memory together)