TLB — structure, TLB miss handling: Exercises

Quick symbol refresher (so line one is followable):

$V$ = number of bits in a virtual address; $M$ = number of bits in a physical address.
$P = 2^{p}$ = page size in bytes, so $p$ = number of offset bits.
VPN = Virtual Page Number = the top $V - p$ bits (which page).
PFN = Physical Frame Number = the top $M - p$ bits of the physical address (physical width minus the $p$ offset bits — the offset is shared, so a frame number needs exactly the bits above the offset).
$h$ = TLB hit ratio (fraction of accesses found in the TLB), $t_{TLB}$ = TLB lookup time, $t_{m}$ = one DRAM access, $k$ = number of page-table levels walked on a miss.

Figure — TLB — structure, TLB miss handling

Level 1 — Recognition

Exercise 1.1 — Name the parts

A virtual address on a machine is 0x00007F3A_12345ABC. The page size is $4 KB$ . Without doing arithmetic yet, state: how many bits are the offset, and which part of the address is the VPN?

Recall Solution

Page size $4 KB = 4096 = 2^{12}$ bytes, so $p = 12$ → offset = 12 bits. $12$ bits = exactly $3$ hex digits (each hex digit = $4$ bits). So the bottom 3 hex digits ABC are the offset, and everything above them is the VPN: 0x7F3A12345. Why: translation happens at page granularity — only the "which page" bits (VPN) get looked up; the "where inside the page" bits (offset) pass through untouched. This is the cut in Figure s01.

Exercise 1.2 — Miss vs fault

Classify each event as TLB miss, page fault, both in sequence, or neither: (a) Translation is in the page table but not in the TLB. (b) The PTE's valid bit is 0 (page is on disk). (c) The VPN is already sitting in the TLB with Valid=1 and matching ASID.

Recall Solution

(a) TLB miss only — nanoseconds; hardware/OS just fetches the PTE. (b) A TLB miss occurs first (nothing cached), the walk then finds an invalid PTE, which raises a page fault → both in sequence. Milliseconds. (c) Neither — this is a plain TLB hit. Why it matters: a TLB miss is a caching event; a page fault is a "page not in RAM" event. See the parent's Page Faults & Demand Paging link.

Level 2 — Application

Exercise 2.1 — Bit split

A CPU has $V = 48$ -bit virtual addresses and uses $2 MB$ huge pages. Compute the offset bits, the VPN bits, and the number of virtual pages a process could address.

Recall Solution

$2 MB = 2 \times 2^{20} = 2^{21}$ bytes → $p = 21$ → offset = 21 bits. VPN $= V - p = 48 - 21 = 27$ bits. Number of pages $= 2^{27} = 134, 217, 728$ . Why huge pages help: with $4 KB$ pages the VPN was $36$ bits ( $2^{36}$ pages); a $2 MB$ page covers $512 \times$ more memory per TLB entry, boosting TLB reach (see Huge Pages / TLB Reach).

Exercise 2.2 — Form the physical address

Page size $4 KB$ ( $p = 12$ ). The TLB reports VPN 0x2B00F → PFN 0x000C4. The virtual address is 0x2B00F_2A7. Compute the physical address. (Figure s02 shows the bit-slot picture that this arithmetic is really doing.)

Recall Solution

Offset = low 12 bits = 0x2A7 (3 hex digits). VPN = 0x2B00F → matches the TLB entry, PFN = 0x000C4. $PA = (PFN ≪ 12) ∣ offset = (0xC4 ≪ 12) ∣ 0x2A7 = 0xC4000 ∣ 0x2A7 = 0x0C42A7 .$ Why the shift: the PFN names a frame; a frame is $2^{12}$ bytes wide, so it must sit in the bits above the 12 offset bits. Then the untranslated offset drops back into the bottom — exactly the "slide then stitch" of Figure s02.

Level 3 — Analysis

Exercise 3.1 — EMAT with a 4-level walk

$t_{TLB} = 1 ns$ , $t_{m} = 80 ns$ , hit ratio $h = 0.95$ , and a hardware walker touches $k = 4$ levels on a miss. Compute the Effective Memory Access Time using the parent's boxed formula. (Figure s03 draws the walk as a chain of DRAM reads.)

Recall Solution

$EMAT = t_{TLB} + t_{m} (1 + (1 - h) k) = 1 + 80 (1 + 0.05 \times 4) .$ $(1 - h) k = 0.05 \times 4 = 0.20$ , so the bracket $= 1.20$ . $EMAT = 1 + 80 (1.20) = 1 + 96 = 97 ns .$ Reading it: the $t_{m} \cdot 1 = 80 ns$ is the unavoidable data fetch; the extra $16 ns$ is the average walk penalty spread over all accesses — the four DRAM hops of Figure s03, but paid only on the $5%$ of accesses that miss.

Exercise 3.2 — How much does the walk cost?

Using the numbers of 3.1, what fraction of EMAT is pure translation overhead (everything except the single mandatory data access $t_{m} = 80 ns$ )?

Recall Solution

Overhead $= EMAT - t_{m} = 97 - 80 = 17 ns$ . Fraction $= 17/97 = 0.1753 \dots \approx 17.5%$ . Why care: nearly one-fifth of every memory access is "just finding out where to go." This is exactly why the TLB (and huge pages) earn their silicon.

Exercise 3.3 — Solve for required hit ratio

You need EMAT $\leq 85 ns$ with $t_{TLB} = 1$ , $t_{m} = 80$ , $k = 4$ . What minimum hit ratio $h$ is required?

Recall Solution

Read the figure first: its horizontal axis is the TLB hit ratio $h$ (from $0.80$ to $1.0$ ), its vertical axis is EMAT in ns. The magenta curve is our formula; the dashed violet line is the $85 ns$ target; the orange dot is where they cross — the answer we now compute algebraically. Set the formula to the target and solve for $h$ : $85 \geq 1 + 80 (1 + 4 (1 - h)) .$ Subtract 1: $84 \geq 80 (1 + 4 (1 - h))$ . Divide by 80: $1.05 \geq 1 + 4 (1 - h)$ . So $0.05 \geq 4 (1 - h)$ → $1 - h \leq 0.0125$ → $h \geq 0.9875$ (98.75%). Reading the figure: EMAT falls steeply as $h \to 1$ ; the orange dot sits far to the right, showing the last few percent of hit rate buy the biggest wins — the whole design story of TLBs.

Level 4 — Synthesis

Exercise 4.1 — Context switch: to flush or not?

Process A ran and filled the TLB. Now the OS switches to Process B. Both use virtual address 0x400000, mapping to different frames. (a) Without ASIDs, what must the OS do and why? (b) With ASIDs/PCIDs, what does it do instead? (An ASID = Address Space ID; PCID = Process-Context ID, Intel x86's name for the same idea — a small tag stored in each TLB entry naming its owning address space.) (c) What happens to kernel pages tagged Global?

Recall Solution

(a) Without ASIDs, entries carry no owner tag, so A's 0x400000→frameₐ could be wrongly used by B. The OS must flush the entire TLB on every switch — throwing away good entries and forcing cold misses afterward (see Context Switching). (b) With ASIDs / PCIDs, each entry is tagged by owning address space. A lookup only hits if VPN matches AND the tag matches. B's accesses simply miss A's entries and coexist safely — no flush needed; entries reload lazily. (ASID is the generic term; PCID is Intel's implementation of it.) (c) Global entries (kernel pages, shared by all processes) match regardless of tag and are kept across the switch — never flushed, so kernel translations stay warm.

Exercise 4.2 — Design a two-level TLB budget

You may spend silicon on either a bigger L1 TLB or add an L2 TLB. L1 hit $= 0.90$ ( $t_{TLB1} = 1 ns$ ). Option X: enlarge L1 to hit $= 0.97$ . Option Y: keep L1 at $0.90$ but add an L2 TLB with $t_{TLB2} = 7 ns$ that catches $80%$ of L1 misses (so a further $0.80$ of the $0.10$ that missed L1). $t_{m} = 80$ , $k = 4$ . Which gives lower EMAT?

Model for Y: a miss in L1 (prob $0.10$ ) checks L2 (costs $t_{TLB2}$ ). L2 hit (prob $0.80$ of those) → then the data access $t_{m}$ . L2 miss (prob $0.20$ of those) → full walk $k t_{m}$ then data. L1 hit (prob $0.90$ ) → $t_{m}$ . Ignore $t_{TLB1}$ differences beyond the base $1 ns$ paid always.

Recall Solution

Option X (single-level formula, $h = 0.97$ ): $EMAT_{X} = 1 + 80 (1 + (1 - 0.97) \times 4) = 1 + 80 (1.12) = 1 + 89.6 = 90.6 ns .$ Option Y (two-level), always pay $1 ns$ L1 lookup:

L1 hit ( $0.90$ ): cost $= t_{m} = 80$ .
L1 miss → L2 lookup $7 ns$ , then split:
- L2 hit ( $0.80$ ): $+ t_{m} = 80$ .
- L2 miss ( $0.20$ ): walk gives PFN then one data access: $+ k t_{m} + t_{m} = 4 \times 80 + 80 = 400$ . $EMAT_{Y} = 1 + 0.90 (80) + 0.10 [7 + 0.80 (80) + 0.20 (400)] .$ Inner bracket $= 7 + 64 + 80 = 151$ . So $0.10 \times 151 = 15.1$ . $EMAT_{Y} = 1 + 72 + 15.1 = 88.1 ns .$ Option Y wins (88.1 < 90.6). Why: the cheap L2 (7ns) absorbs most L1 misses far more cheaply than a full 4-level walk (320ns), even though the L1 hit rate stayed low. This is why real CPUs ship a small fast L1 TLB plus a larger L2 TLB (see Cache Memory & Associativity).

Level 5 — Mastery

Exercise 5.1 — Huge pages vs TLB reach, end to end

A workload touches $256 MB$ of memory uniformly. The L1 TLB has $64$ entries. (a) With $4 KB$ pages, how much memory does the TLB cover (its reach), and what fraction of the $256 MB$ working set fits? (b) With $2 MB$ huge pages, recompute reach and fraction. (c) Explain, using these numbers, why huge pages slash TLB misses here — and name one cost.

Recall Solution

(a) 4KB pages: reach $= 64 \times 4 KB = 256 KB$ . Fraction of the $256 MB$ set covered $= 256 KB /256 MB = 1/1024 \approx 0.098%$ . The TLB covers almost nothing → the working set thrashes the TLB, misses everywhere. (b) 2MB pages: reach $= 64 \times 2 MB = 128 MB$ . Fraction $= 128 MB /256 MB = 50%$ . Now half the entire working set is covered by the TLB at once — misses plummet. (c) Reach scaled by $2 MB /4 KB = 512 \times$ , turning $0.098%$ coverage into $50%$ . Cost: internal fragmentation (a page barely used still costs $2 MB$ ), harder allocation of contiguous physical memory, and coarser permission granularity. It is a tradeoff, not a free win (see Huge Pages / TLB Reach).

Exercise 5.2 — Software vs hardware managed miss cost

On a MIPS-style software-managed TLB, a miss traps to the OS: trap entry/exit $= 60 ns$ , then the handler does $k = 3$ memory reads to walk the table ( $t_{m} = 80 ns$ each) and one special "write TLB" instruction $= 5 ns$ . On an x86-style hardware-managed walker the same $k = 3$ reads happen but with no trap and no special instruction (walker in hardware). Compare the per-miss cost (translation only, exclude the final data access which both pay).

Recall Solution

Software-managed miss: $60 + 3 \times 80 + 5 = 60 + 240 + 5 = 305 ns$ . Hardware-managed miss: $3 \times 80 = 240 ns$ . Difference $= 305 - 240 = 65 ns$ of pure trap/handler overhead per miss. The tradeoff: software management gives the OS total freedom over page-table format (Page Tables (Multi-level) can be anything), but pays that $65 ns$ overhead on every miss. Hardware management is faster but locks the table format into the ISA. Neither is universally "better."

Related: Virtual Memory · Page Tables (Multi-level) · Cache Memory & Associativity · Page Faults & Demand Paging · Context Switching · Huge Pages / TLB Reach