Module 04 • COSC240

TLB Acceleration & Inverted Page Tables

Examine how hardware engineers defeat the multi-level memory amplification penalty using Translation Lookaside Buffers (TLB), calculate Effective Memory Access Times (EMAT), contrast CISC vs. RISC walk models, and explore Inverted Page Table architectures.

1. The Hardware TLB: Associative Cache Architecture

As established in Module 03, hierarchical paging introduces a severe latency penalty: every memory access requires traversing $3$, $4$, or $5$ levels of page tables in RAM before reading or writing data.

To eliminate this overhead, processor architects integrate a specialized, ultra-fast hardware cache directly into the Memory Management Unit (MMU): the Translation Lookaside Buffer (TLB).

Content-Addressable Memory (CAM) Mechanics

Unlike standard SRAM or DRAM arrays that take a numeric address and return data, the TLB is constructed from Content-Addressable Memory (CAM):

Parallel Tag Matching: Every slot in the CAM contains its own independent comparison logic. When the CPU emits a Virtual Page Number ($p$), the TLB hardware compares $p$ against all cached entries simultaneously in a single clock cycle ($< 1\text{ ns}$).
Associativity: TLBs are typically fully-associative (any virtual page can occupy any TLB slot) or highly set-associative (e.g., 4-way to 8-way associative), containing between 64 and 2048 entries.
Payload: Each TLB entry stores the Virtual Page Number (tag), corresponding Physical Frame Number ($f$), and caching/protection flags (Valid, Read/Write, User/Supervisor, Dirty).

Interactive Walkthrough: Hardware TLB Associative Lookup & Page Walk

Trace step-by-step how the MMU evaluates CAM tags in parallel, achieving single-cycle translation on a TLB Hit, or falling back to a 4-level DRAM page walk on a TLB Miss.

Step 1: Virtual Address Issued. CPU pipeline references virtual address 0x000034B8. The MMU splits off Virtual Page Number $p=3$ and offset $d=\text{0x4B8}$.

Phase: 1/4

Page (p): p = 3

Latency: ~1 ns

Status: Associative Probe

OUTCOME:

Synchronized Visual Canvas — Associative CAM Matching & Fallback

🔍 What Is Happening

CPU issues virtual address 0x000034B8. The MMU presents virtual page number p=3 simultaneously across all TLB CAM tag comparators.

⚙ Why The System Does This

Parallel CAM tag comparison resolves address translation in a fraction of a nanosecond, eliminating physical DRAM table walk latency.

2. Effective Memory Access Time (EMAT)

The performance of a virtual memory architecture is quantified by the Effective Memory Access Time (EMAT). EMAT represents the weighted harmonic average time required to complete a memory reference, factoring in cache hit probability.

Mathematical Formulation of EMAT:

Let:

$h$: The TLB hit ratio ($0 \le h \le 1$).
$t_{\text{TLB}}$: The associative TLB lookup latency (typically $\approx 1\text{ ns}$).
$t_{\text{RAM}}$: The physical DRAM read latency (typically $\approx 50\text{ ns}$).
$L$: The number of hierarchical page table levels ($L = 4$ for standard x86-64).

$$ \text{EMAT} = h \cdot (t_{\text{TLB}} + t_{\text{RAM}}) + (1 - h) \cdot \big(t_{\text{TLB}} + (L + 1) \cdot t_{\text{RAM}}\big) $$

Step-by-Step EMAT Numerical Walkthrough

Consider an x86-64 system with 4-level paging ($L = 4$), a TLB lookup time of $t_{\text{TLB}} = 1\text{ ns}$, and main memory latency of $t_{\text{RAM}} = 50\text{ ns}$:

On a TLB Hit: $$ t_{\text{hit}} = t_{\text{TLB}} + t_{\text{RAM}} = 1\text{ ns} + 50\text{ ns} = \mathbf{51\text{ ns}} $$ (1 TLB lookup to get frame, 1 RAM read to get actual data operand).
On a TLB Miss: $$ t_{\text{miss}} = t_{\text{TLB}} + (4 \times 50\text{ ns}) + 50\text{ ns} = 1 + 200 + 50 = \mathbf{251\text{ ns}} $$ (1 TLB probe + 4 sequential page table DRAM reads + 1 RAM read for data).

Scenario A: 98% TLB Hit Rate (Realistic Workload)

Because of strong temporal and spatial locality (loops accessing adjacent array elements and code instructions), real-world applications routinely achieve $h = 0.98$ (98% hit rate):

$$ \text{EMAT} = 0.98 \times (51\text{ ns}) + 0.02 \times (251\text{ ns}) = 49.98 + 5.02 = \mathbf{55\text{ ns}} $$

Compared to the raw physical RAM speed of $50\text{ ns}$, virtual memory introduces only a $10\%$ slowdown ($55\text{ ns}$ vs $50\text{ ns}$), despite 4 levels of hierarchical tables!

Scenario B: 80% TLB Hit Rate (Thrashing Workload)

If an algorithm accesses memory in massive, non-local strides that thrash the TLB ($h = 0.80$):

$$ \text{EMAT} = 0.80 \times (51\text{ ns}) + 0.20 \times (251\text{ ns}) = 40.8 + 50.2 = \mathbf{91\text{ ns}} $$

Memory latency nearly doubles ($91\text{ ns}$ vs $50\text{ ns}$), illustrating why optimizing algorithms for TLB cache locality is paramount in high-performance computing.

3. Hardware vs. Software Managed TLBs

Operating system architectures diverge sharply in how TLB misses are serviced:

Architectural Feature	Hardware-Walked TLBs (x86, ARMv8)	Software-Walked TLBs (MIPS, SPARC, Alpha)
Miss Handling Entity	Hardware MMU (Finite State Machine in silicon)	Operating System Kernel (Trap Handler Routine)
Page Table Format	Rigidly dictated by processor hardware (e.g., x86 CR3 hierarchy).	Completely flexible; OS can choose inverted tables, radix trees, or hashes.
Miss Latency Penalty	Fast ($\approx 50\text{–}200\text{ ns}$): no pipeline flush or ring transition.	Slower ($\approx 100\text{–}500\text{ ns}$): CPU raises trap, saves registers, switches to Ring 0.
Hardware Complexity	High: silicon contains complex multi-level walking logic.	Minimal: simple CAM cache; keeps RISC CPU core clean and fast.

4. Context Switching & Address Space Identifiers (ASID)

Because virtual addresses are private to each process, Virtual Page Number $p = 5$ in Process $A$ maps to a completely different physical frame than $p = 5$ in Process $B$.

The Naive Approach (TLB Invalidation): On every context switch, the OS flushes the entire TLB (e.g., reloading register CR3 on early x86 chips). When the new process begins executing, every single memory access suffers a TLB miss until the cache warms up, causing massive context switch latency spikes.
The Modern Solution (ASID / PCID): Modern processors tag each TLB entry with an Address Space Identifier (ASID) (or Process-Context Identifier, PCID, in Intel x86). When matching a tag, the CAM hardware checks both $p$ and the active process's ASID: $$ \text{Hit Condition: } (\text{VirtualPage} == \text{Tag}) \ \land \ (\text{ASID} == \text{ActiveASID}) $$ This allows entries from multiple distinct processes to coexist simultaneously in the TLB across context switches without cache flushes.

5. Inverted Page Tables (IPT) & Hash Anchors

In traditional forward-mapped paging, the table is indexed by virtual page number. In 64-bit systems, forward multi-level tables still consume significant memory for deeply nested structures.

An alternative architectural approach pioneered on IBM RS/6000 and PowerPC systems is the Inverted Page Table (IPT):

The Inverted Principle:

Instead of indexing by Virtual Page, the Inverted Page Table is indexed strictly by Physical Frame Number ($f$). $$ \text{Total IPT Entries} = \text{Total Physical Frames in RAM} = \frac{\text{Physical RAM Size}}{\text{Page Size}} $$

Each entry in the IPT stores the tuple: $\big(\text{Process ID}, \text{Virtual Page Number } p, \text{Flags}\big)$.

Scaling Superiority

Under an IPT, the memory occupied by the page table depends strictly on physical RAM size, completely independent of how massive the 64-bit virtual address space is:

For an 8 GB physical RAM system with 4 KB pages: $$ \text{Total Frames} = \frac{8\text{ GB}}{4\text{ KB}} = 2{,}097{,}152\text{ frames} $$ At 16 bytes per IPT entry, the single global table consumes exactly 32 MB of RAM, serving all concurrent processes in the entire operating system!

Hash Anchor Tables (HAT) for $\mathcal{O}(1)$ Lookup

The drawback of an inverted table is that when the CPU issues a virtual address $(PID, p)$, the MMU cannot simply index into the table directly (since the table is indexed by physical frame $f$). Searching the IPT linearly would take $\mathcal{O}(\text{Frames})$ time—millions of comparisons per instruction.

To solve this, hardware and OS designers place a Hash Anchor Table (HAT) in front of the Inverted Page Table:

The MMU hashes the tuple $(PID, p)$ using a hardware hash function: $h = \text{Hash}(PID, p)$.
The hash value $h$ indexes directly into the Hash Anchor Table to retrieve a pointer to the head of a collision chain in the IPT.
The MMU follows the short collision chain (typically 1 to 2 entries) until it finds a matching $(PID, p)$ tag. The index of the matching node in the IPT is the Physical Frame Number ($f$)!

The Primary Limitation of Inverted Page Tables: IPTs make shared memory (multiple processes mapping distinct virtual pages to the exact same physical frame) extremely difficult. Because each physical frame has exactly one entry in the IPT, mapping multiple $(PID, p)$ aliases to one frame requires complex software alias tracking and reverse lookup chains.