TLB (translation lookaside buffer): Exercises — Hardware deep dive

Reference numbers used throughout (unless a problem overrides them):

Before touching a single problem, see what that formula means. The picture below breaks the EMAT into three stacked blocks: the pale lavender block $t_{TLB}$ you pay on every access (searching the TLB), the butter block $t_{m}$ you also pay on every access (the final data read), and the thin coral block $(1 - h) W t_{m}$ — the miss penalty — which is present only for the miss fraction. Notice the coral block shrinks toward nothing as $h \to 1$ : that visual shrinking is the whole reason the TLB helps.

Figure — TLB (translation lookaside buffer)

Every access also has to decide hit vs. miss, and a miss is not the end of the story — it can end in a clean fill, or in a page fault if the page isn't in memory at all. That branching is easiest to follow as a flowchart:

Keep this flowchart in mind: the valid-bit branch (E) is the case most students forget, and it is the subject of Exercise 3.4.

Level 1 — Recognition

Exercise 1.1 — Splitting an address

A system uses $P = 4 KiB$ pages and 32-bit virtual addresses. For the virtual address 0x00012ABC, state (a) how many offset bits, (b) the offset value, (c) the VPN.

The bit-field picture below shows exactly where the cut falls: the top 20 bits are the VPN (lavender), the bottom 12 bits are the offset (mint), and the vertical dashed line is the boundary at bit 11/12.

Recall Solution 1.1

(a) $4 KiB = 2^{12}$ bytes, so the offset needs 12 bits to name each byte inside the page. (b) The offset is the low 12 bits. 0x00012ABC in the bottom 3 hex digits is ABC — but 3 hex digits = 12 bits exactly, so offset = 0xABC. (c) The VPN is everything above bit 11 → the high 20 bits = 0x00012. Why split this way? Paging never moves a byte within its page, so the low $lo g_{2} P$ bits pass through untranslated; only the page number is looked up.

Exercise 1.2 — What lives in a TLB entry?

Which of these belong inside a single TLB entry? (VPN, PFN, the page offset, valid bit, permission bits, the ASID tag, the whole page's data.)

Recall Solution 1.2

A TLB entry stores: VPN (the tag/key), PFN (the answer), a valid bit, permission bits (read/write/execute, user/kernel), and — on designs that avoid flushing — an ASID (Address-Space Identifier) tag naming which process owns the mapping. It does NOT store the page offset (that comes from the address itself, untranslated) and it does NOT store the page's data (that's in cache/DRAM, not the TLB). Why the ASID field matters: without it, VPN 0x5 for process A is indistinguishable from VPN 0x5 for process B, forcing a full flush on every Context Switch. The tag lets both entries live side by side (used in Exercise 4.2).

Level 2 — Application

Exercise 2.1 — Build the physical address

Given VPN 0x00012 → PFN 0x0037 in the TLB, $P = 4 KiB$ , translate VA = 0x00012ABC to a physical address.

Recall Solution 2.1

Split: offset = 0xABC, VPN = 0x00012 (from Exercise 1.1).
Lookup: VPN 0x00012 is present → hit, PFN = 0x0037.
Form PA: $PA = (PFN ≪ 12) ∣ offset$ . Shifting 0x0037 left by 12 bits = 0x00037000 (three hex zeros appended = 12 bits). OR with 0xABC → PA = 0x00037ABC. Why shift by 12? The PFN names a whole 4KiB frame; its base byte address is $PFN \times P = PFN \times 2^{12}$ , which is exactly a left shift by 12.

Exercise 2.2 — EMAT plug-in

$t_{TLB} = 1$ ns, $t_{m} = 100$ ns, single-level walk ( $W = 1$ ), hit rate $h = 0.95$ . Find the EMAT.

Recall Solution 2.2

Extra miss cost $= (1 - h) W t_{m} = (0.05) (1) (100) = 5$ ns. $EMAT = t_{TLB} + t_{m} + extra = 1 + 100 + 5 = 106 ns$ . Why this shape? You always search the TLB ( $t_{TLB}$ ) and always do one final data read ( $t_{m}$ ); the walk is the only extra cost and it only happens on the $5%$ of accesses that miss. This is exactly the three-block picture from the top of the page with $h = 0.95$ .

Level 3 — Analysis

Exercise 3.1 — Multi-level walk hurts more

Same system as 2.2 ( $t_{TLB} = 1$ , $t_{m} = 100$ ) but a 4-level page table ( $W = 4$ ) and $h = 0.98$ . Compare EMAT to the single-level case at the same hit rate.

Recall Solution 3.1

Single-level ( $W = 1$ ): extra $= (0.02) (1) (100) = 2$ → EMAT $= 1 + 100 + 2 = 103$ ns. Four-level ( $W = 4$ ): extra $= (0.02) (4) (100) = 8$ → EMAT $= 1 + 100 + 8 = 109 ns$ . Analysis: the miss fraction is identical (2%), but each miss now costs 4× the walk work. So deeper page tables multiply the penalty per miss, which is exactly why high $h$ matters more on x86-64.

Exercise 3.2 — Solve for the required hit rate

You want $EMAT \leq 105$ ns with $t_{TLB} = 1$ , $t_{m} = 100$ , $W = 1$ . What minimum hit rate $h$ do you need?

Recall Solution 3.2

Set up: $1 + 100 + (1 - h) (1) (100) \leq 105$ . $\Rightarrow 101 + 100 (1 - h) \leq 105$ $\Rightarrow 100 (1 - h) \leq 4$ $\Rightarrow 1 - h \leq 0.04 \Rightarrow h \geq 0.96$ . Minimum hit rate = 96%. Why invert the formula? EMAT rises as $h$ falls; the constraint is an inequality on the miss fraction $(1 - h)$ , so we isolate it and read off the boundary.

Exercise 3.3 — Speedup vs. no TLB

With $h = 0.98$ , $t_{m} = 100$ , $t_{TLB} = 1$ , single-level walk, compare against a machine with no TLB (every access pays one page-table read + one data read $= 2 t_{m}$ ). What is the speedup?

Recall Solution 3.3

No TLB: every access $= 2 t_{m} = 200$ ns. With TLB: $EMAT = 1 + 100 + (0.02) (100) = 103$ ns. Speedup $= 200/103 \approx 1.94 \times$ . Reading it: locality concentrates accesses on a few pages → high $h$ → the TLB nearly halves access time here.

Exercise 3.4 — The miss that isn't just a walk (valid-bit edge case)

Follow the flowchart's branch E. A memory access misses in the TLB, so hardware walks the page table — and finds the PTE's valid bit = 0, meaning the page is not resident in physical memory. Times: $t_{TLB} = 1$ ns, single walk $t_{m} = 100$ ns ( $W = 1$ ), and servicing a Page Fault from disk costs $t_{fault} = 5, 000, 000$ ns (5 ms). After the OS loads the page it re-walks (another $100$ ns) and does the data read ( $100$ ns). What is the total time for this one access, and how many times larger is it than an ordinary TLB hit ( $t_{TLB} + t_{m} = 101$ ns)?

Recall Solution 3.4

Walk down the flowchart branch by branch:

TLB search: $t_{TLB} = 1$ ns.
First walk finds valid bit = 0: $W t_{m} = 100$ ns.
Page fault to disk (branch E → G → H): $t_{fault} = 5, 000, 000$ ns.
Re-walk after the page is resident: $100$ ns.
Data read: $t_{m} = 100$ ns.

Total $= 1 + 100 + 5, 000, 000 + 100 + 100 = 5, 000, 301 ns$ . Ratio vs. a hit $= 5, 000, 301/101 \approx 49, 508 \times$ . The point: a TLB miss and a page fault are different quadrants. Most misses stop at step 2 (valid bit = 1 → clean fill, ~100ns). The valid-bit-zero branch is the rare, catastrophic one — five million nanoseconds — because it hits the disk. The EMAT formula only models the common (resident) miss; page faults are a separate, much rarer term.

Level 4 — Synthesis

Exercise 4.1 — Two-level TLB EMAT

A design has an L1 TLB (search $t_{1} = 1$ ns) and an L2 TLB (search $t_{2} = 4$ ns). L1 hit rate $h_{1} = 0.90$ . Of the L1 misses, the L2 catches $h_{2} = 0.80$ . An L2 miss triggers a full walk $W t_{m}$ with $W = 4$ , $t_{m} = 100$ . On any access you also pay one final data read $t_{m}$ . Ignore $t_{2}$ when L1 hits (parallel/short-circuit). Compute EMAT.

Recall Solution 4.1

Build cost by cases, then always add the final data read $t_{m} = 100$ :

L1 hit (prob $0.90$ ): translation cost $= t_{1} = 1$ .
L1 miss, L2 hit (prob $0.10 \times 0.80 = 0.08$ ): cost $= t_{1} + t_{2} = 1 + 4 = 5$ .
L1 miss, L2 miss (prob $0.10 \times 0.20 = 0.02$ ): cost $= t_{1} + t_{2} + W t_{m} = 1 + 4 + 400 = 405$ .

Expected translation cost: $0.90 (1) + 0.08 (5) + 0.02 (405) = 0.90 + 0.40 + 8.10 = 9.40 ns .$ Add the data read: $EMAT = 9.40 + 100 = 109.4 ns$ . Why two levels? A tiny fast L1 keeps the common case cheap; a bigger L2 rescues most L1 misses without paying the 400ns walk — same layering idea as data caches.

Exercise 4.2 — Flush vs. ASID cost after a context switch

On a Context Switch, design A flushes the TLB; design B uses ASIDs — the Address-Space Identifier field from Exercise 1.2 that tags each entry with its owning process, so no flush is needed. After a switch, the returning process makes $N = 1000$ accesses. With ASIDs its warm hit rate is $h = 0.98$ . After a flush the TLB is cold: for these $1000$ accesses the average hit rate drops to $h^{'} = 0.85$ (miss storm while it refills). Using $t_{TLB} = 1$ , $t_{m} = 100$ , $W = 1$ , how much total time does ASID save over flush across these 1000 accesses?

Recall Solution 4.2

Per-access EMAT:

ASID: $1 + 100 + (0.02) (100) = 103$ ns.
Flush: $1 + 100 + (0.15) (100) = 116$ ns. Over $N = 1000$ accesses:
ASID total $= 1000 \times 103 = 103, 000$ ns.
Flush total $= 1000 \times 116 = 116, 000$ ns. Savings $= 116, 000 - 103, 000 = 13, 000$ ns $= 13 μ s$ per switch window. Synthesis point: the flush's damage is the cold-start miss storm — the cost isn't the flush instruction itself but the many walks that follow. The ASID tag lets entries survive the switch, avoiding refill.

Level 5 — Mastery

Exercise 5.1 — When is a bigger TLB actually worse?

A small TLB has $t_{TLB} = 1$ ns and hit rate $h_{S} = 0.95$ . A big TLB raises the hit rate to $h_{B} = 0.99$ but, being on the critical path of every access, its search time rises to $t_{TLB} = 2$ ns. With $t_{m} = 100$ , $W = 1$ , which wins on EMAT?

Recall Solution 5.1

Small: $EMAT_{S} = 1 + 100 + (0.05) (100) = 106$ ns. Big: $EMAT_{B} = 2 + 100 + (0.01) (100) = 103$ ns. Big TLB wins here (103 < 106). But notice the tension: the big TLB saved $4$ ns on the walk term yet added $1$ ns to $t_{TLB}$ on every single access. If its search time had risen to, say, $6$ ns, it would lose: $6 + 100 + 1 = 107 > 106$ . Mastery point: every nanosecond added to $t_{TLB}$ is paid unconditionally; walk savings are paid only on the miss fraction. Bigger only wins while $Δ t_{TLB} < (h_{B} - h_{S}) W t_{m}$ .

Exercise 5.2 — Derive the break-even search-time penalty

Generalise 5.1. A bigger TLB improves the hit rate from $h_{S}$ to $h_{B}$ but adds $Δ$ ns to the search time. Derive the largest $Δ$ for which the bigger TLB still helps, in terms of $h_{S}, h_{B}, W, t_{m}$ . Evaluate for $h_{S} = 0.95, h_{B} = 0.99, W = 4, t_{m} = 100$ .

Recall Solution 5.2

Break-even is where both EMATs are equal: $(t_{TLB} + Δ) + t_{m} + (1 - h_{B}) W t_{m} = t_{TLB} + t_{m} + (1 - h_{S}) W t_{m} .$ Cancel the common $t_{TLB} + t_{m}$ : $Δ + (1 - h_{B}) W t_{m} = (1 - h_{S}) W t_{m}$ $Δ_{m a x} = (h_{B} - h_{S}) W t_{m}$ Evaluate: $Δ_{m a x} = (0.99 - 0.95) (4) (100) = (0.04) (400) = 16 ns$ . Interpretation: with a deep 4-level walk, the walk penalty is big, so you can afford up to 16ns of extra search time before the bigger TLB stops paying off. Deeper page tables → more headroom for larger TLBs. This is exactly why real CPUs pair deep page tables with multi-level TLBs.

The trade-off in Exercises 5.1 and 5.2 is easiest to see as a graph. The figure below plots the small-TLB EMAT (a flat line — it never changes) against the big-TLB EMAT (which rises as its extra search time $Δ$ grows). Read off exactly where the rising line crosses the flat one: that crossing is $Δ_{m a x}$ , and the shaded region to its left is where the bigger TLB wins.