Trail: Scalable and Low-Cost Temporal TLB Prefetching via Page-Table-Embedded Deltas

Shortcomings of Prior Works

• Spatial prefetchers struggle with irregular patterns, while fixed-capacity temporal-prefetcher tables cannot scale with application memory footprints.The open question is whether a few compact deltas per region can capture most patterns while keeping hardware cost low.Source: §1 · p. 1

Key Observations

• Per-PC transitions are locally structured: the top four (eight) destinations cover about 86% (93%) of transitions, and 18-bit signed deltas represent over 94%.The characterization spans 200 translation-intensive workloads and finds that 2–4 deltas per source region capture most temporal patterns.Source: §1 · p. 2

Key Idea

• A 64-entry PC table tracks the region that last triggered a page-table walk from each instruction; later walks record the source-to-destination delta in that source region’s payload.A frequency-based replacement policy retains frequent deltas and ages out stale ones; Trail uses confident payload deltas to issue pre-walks for destination regions.Source: §1 · p. 2

Key Results

• 5.7% (11.5%) average performance improvement over No-TLB-Prefetcher and 1.7% (2.5%) over Recency in single-core (four-core) systems.Trail also improves performance by 7.6% (14.1%) over No-TLB-Prefetcher when combined with Next-Page.Source: §1 · p. 3

Key Idea

• Trail stores a small set of recurring per-region deltas in unused leaf-PTE bits, scaling metadata capacity with application memory footprint without dedicated SRAM or additional memory capacity.The deltas arrive with the region’s PTEs, so Trail can retrieve multiple predictions without additional memory accesses.Source: §1 · pp. 2–3

2.1. Address Translation Basics

• A TLB miss triggers a page-table walk through a radix-tree page table; leaf PTEs store physical frame numbers and protection bits, and the page table grows with process memory footprint.Eight consecutive leaf PTEs mapping 32 KB of virtual memory share a 64-byte cache block.Source: §2.1 · p. 3

2.2. TLB Prefetching Basics

• A prefetch walk retrieves predicted mappings ahead of demand and places them in the L2 TLB or prefetch buffer while bringing their PTE cache blocks into the cache hierarchy.This can eliminate a later demand walk or make it faster if the PTEs remain cached.Source: §2.2 · p. 3
• TLB-prefetcher effectiveness is measured by coverage, accuracy, and timeliness; timeliness measures how early or late a translation arrives relative to demand.Coverage is the fraction of demand walks eliminated, and accuracy is the fraction of prefetched translations used.Source: §2.2 · pp. 3–4

Prior TLB Prefetchers

• Spatial prefetchers exploit regularity, but mixed regular and irregular accesses in data-intensive workloads limit approaches relying solely on spatial locality.Hybrid ATP combines spatial and temporal components, yet its fixed offsets and short histories limit capture of recurring irregular patterns across many regions.Source: §3 · p. 4

Temporal Prefetchers

• Recency-based prefetching uses L2 TLB eviction order, which does not necessarily reflect the application’s future page-access order.Eviction decisions depend on replacement-policy criteria that are not directly related to actual access patterns.Source: §3 · p. 4
• Distance Prefetching’s fixed-size table may discard learned delta pairs before they recur, missing prefetch opportunities as workloads exhibit more pairs than it can retain.The paper concludes that existing temporal prefetchers face fundamental limits in capturing recurring translation patterns.Source: §3 · p. 4

• The design goal is to capture recurring irregular translation patterns while keeping hardware cost low and history capacity proportional to application memory.Meeting these goals requires avoiding both large dedicated hardware tables and additional main-memory storage.Source: §4 · p. 4
• The characterization examines PTW-triggering virtual addresses, grouping pages into fixed-size regions of eight contiguous 4 KB pages by default.The study asks whether a small number of compact deltas per region can capture temporal correlations.Source: §4 · p. 4
• A transition is a source region and its delta to a destination region; tracking can pair PTWs globally or with the preceding PTW from the same PC.For example, per-PC tracking pairs PC A’s PTWs to regions 4 and 6, yielding delta +2.Source: §4 · p. 4

Per-PC

• 86% of transitions are captured by the four most frequent per-PC deltas per source region, and 93% by the eight most frequent.Per-PC tracking captures 31 to 36 percentage points more transitions than global tracking at every evaluated k.Source: Figure 2 · p. 5, Per-PC · p. 5
• Distributing delta storage across source regions lets history capacity grow with application memory rather than remain bounded by a fixed-size hardware table.A small number of per-PC deltas per source region captures most source-to-destination transitions.Source: Per-PC · p. 5
• A small set of deltas accounts for 90.4%–100% of transitions in each of the selected source regions, and dominant deltas differ across regions.The contrast between regions in one workload supports learning deltas separately for each source region.Source: Figure 3 · p. 5, Per-PC · p. 5
• Repeated traversal by a few load instructions and memory placement of related data create recurring per-PC deltas to a small set of destination regions.In the BFS example, PTWs from region 5 reach region 6 or 15 with per-PC deltas +1 or +10; these deltas identify destination regions, not individual vertices.Source: Per-PC · p. 5
• With four (eight) per-PC deltas, coverage rises from 82.0% (90.0%) at 4 KB granularity to 86.2% (93.0%) at 32 KB, and to 95.2% (98.7%) at 16 MB.Coarser regions can collapse nearby destinations into shared deltas, but their larger predicted regions increase the risk of overfetch.Source: Figure 5 · p. 6, Per-PC · p. 6
• As region size increases, unused prefetched PTEs increase; larger regions can consume TLB capacity with translations evicted before use.Each granularity step increases the number of PTEs prefetched for a destination region eightfold.Source: Figure 6 · p. 6, Per-PC · p. 6
• With 32 KB regions, 18-bit signed values represent 94.9% of per-PC delta occurrences, compared with 68.7% of global occurrences.Four 18-bit delta fields require 72 bits per source region.Source: Figure 7 · p. 6, Per-PC · p. 6

Recording Deltas

• Trail stores each source region’s small set of recorded deltas and confidence counters in unused bits of its leaf PTEs.If available PTE bits are insufficient, Trail can store the payload in an OS-managed external delta table, at the cost of additional storage and a parallel lookup.Source: §5 · p. 7
• A small hardware PC table tracks the last region that triggered a demand page-table walk from each instruction, letting Trail record the transition in the source region’s payload.The payload’s confidence counters reflect how often deltas recur, helping retain frequent deltas and discard stale ones.Source: §5 · p. 7

Prefetching

• A later page-table walk retrieves the PTE block’s embedded payload without an additional memory access, and Trail uses confident deltas to prefetch destination translations.When payloads are stored in the external delta table, Trail looks them up in parallel with the demand page-table walk.Source: §5 · p. 7

Key Benefits

• PTE-embedded delta capacity scales with application memory footprint, while reusing existing unused bits avoids dedicated hardware tables or additional memory.Fetching the payload together with the PTEs also avoids a separate memory access.Source: §5 · p. 7

6.1. Delta Payload Organization

• Each payload block stores k signed prediction-region deltas with confidence counters; the default payload uses four 18-bit deltas and four 2-bit counters, totaling 80 bits.Payload-block size determines metadata grouping, while prediction-region size determines the unit in which deltas are measured; they can differ.Source: §6.1 · p. 7

6.1.1. In-PTE Storage and Capacity.

• PTE embedding is best-effort because usable PTE bits vary by architecture; when embedding is unavailable or insufficient, Trail-External stores the same payload in an OS-managed external delta table.The default x86-64 configuration assumes 10 available bits per leaf PTE across eight PTEs; the external table uses a three-level radix tree and performs payload lookup in parallel with the demand walk.Source: §6.1 · p. 7, §6.1.1 · pp. 7–8, §6.1.2 · p. 8

6.2. Recording Deltas

• For each instruction, a PC table tracks the last VPN to trigger a walk; on a matching instruction, Trail computes the prediction-region delta and updates the payload block containing the preceding VPN.A PC-tag mismatch replaces the entry without recording a delta; matching deltas gain confidence, while new deltas use a free or low-confidence slot and aging prevents stale entries from persisting indefinitely.Source: §6.2 · p. 8, §6.2.1 · p. 8

6.3. Prefetching using Recorded Deltas

• On a demand L2 TLB miss, Trail retrieves the current payload, selects nonzero deltas whose confidence meets the issue threshold, and pre-walks the destination region to fetch its translations.Fetched PTEs enter the L2 TLB or prefetch buffer; even if an entry is later evicted, its PTE may remain in the cache hierarchy and reduce translation latency.Source: §6.3 · pp. 8–9

6.3.1. Chained Prefetching.

• Trail can recursively process payloads from prefetched regions in FIFO order, while a depth limit bounds the chain and visited-region tracking avoids cycles and repeated prefetches.A depth of zero allows direct predictions only; a depth of one permits one additional step.Source: §6.3.1 · p. 9

6.4. Support for Huge Pages

• For 2 MB pages, Trail stores payloads in PMD blocks when sufficient bits are available and otherwise uses the external table, applying the same payload format and confidence rules.PC-table tags include page size so recorded deltas do not cross between 4 KB and 2 MB pages.Source: §6.4 · p. 9

6.5.1. Per-PC Stride Detection.

• Trail augments its PC table with a per-PC stride predictor that prefetches individual pages after confidence reaches a threshold, covering accesses without useful delta history.While a stride remains stable, Trail stops recording that PC’s region deltas but continues using existing payloads for delta-based prefetching.Source: §6.5 · p. 9, §6.5.1 · pp. 9–10

6.5. Extensions to Trail

• To preserve learning state across frequent PC-table evictions without enlarging the on-chip table, Trail backs evicted entries in memory and restores them when their instruction reappears.The on-chip PC table therefore acts as a cache of per-instruction learning state.Source: §6.5 · p. 9, §6.5.2 · p. 10

Evaluation Framework

• Trail and evaluated systems are modeled in Virtuoso, a full-system simulation framework validated against real systems and built on the Sniper event-based multicore simulator.Trail is open source.Source: §7 · p. 10

Workloads

• The evaluation uses 200 traces spanning datacenter, mobile SoC, graph, CPU, and other memory-intensive workloads, each with address translation consuming more than 3% of execution time.Single-core runs execute 300M instructions per benchmark; four-core evaluation uses 100 mixes of the 50 most translation-intensive benchmarks, each run for 50M instructions.Source: §7 · p. 10, Table 2 · p. 10

Evaluated Systems

• Trail is compared with eight systems, including a no-prefetch baseline and prior TLB prefetchers, under a shared processor, cache hierarchy, data prefetchers, and prefetch buffer.All TLB-prefetching configurations except Trail use the same IP-Stride prefetcher, and demand and prefetch walks share page-table walkers.Source: §7 · p. 10, Table 3 · p. 10

Trail Configurations

• Unless otherwise specified, reported Trail results use Trail-Best; Trail-External uses the same settings but stores payloads in an external delta table and uses four-bit confidence counters.The evaluated system and Trail configurations are listed in Table 3.Source: §7 · p. 10, Table 3 · p. 10

8.1. Single-core Performance

• Trail-Best outperforms prior prefetchers on most workload families with large, irregular translation streams, including Google Server workloads.Google Server workloads comprise 137 of the 200 evaluated workloads; Trail-Best improves performance by 4.0% (4.5%) over No-TLB-Prefetcher and by 1.7% (1.7%) over Recency.Source: §8.1 · p. 11, Figure 12 · p. 12
• Trail-Best improves average performance over No-TLB-Prefetcher by 5.7% single-core and 11.5% four-core, beating Recency by 1.7% and 2.5%, respectively.Trail-Best also improves performance by 5.7% with a 2 MB LLC slice and 5.2% with an 8 MB slice. Combining it with Next-Page raises the gains to 7.6% and 14.1%, respectively.Source: Figure 11 · p. 11, §8.1 · p. 11, Figure 16 · p. 13

8.2. Performance Analysis

• Across the 50 most translation-intensive workloads, Trail-Best reduces total demand PTW latency per kilo instructions from 786 cycles to 316 cycles, a 60% reduction.It reduces demand PTWs from 18.8 to 13.2 per kilo instructions and average latency per demand PTW from 61.9 to 34.6 cycles.Source: Figure 13 · p. 12, §8.2 · p. 12
• 91% of Trail-Best's accurate prefetches complete before demand, and delta updates cause an average of 0.43 PTE cache block writebacks per kilo instructions.Most timely prefetches arrive fewer than 5K cycles before demand; 90% of workloads have fewer than 0.7 writebacks per kilo instructions.Source: §8.2 · pp. 12–13, Figure 14 · p. 13, Figure 15 · p. 13

8.3. Multicore Performance

• In four-core mixes, Trail-Best improves performance by 11.5% over No-TLB-Prefetcher, while a 32× larger L2 TLB improves it by 1.6%.Trail-Best captures 50% of the perfect L2 TLB's improvement; Trail-Best+Next-Page improves performance by 14.1%.Source: Figure 16 · p. 13, §8.3 · p. 13

8.4. Sensitivity to System Configuration

• With 74% of memory backed by 2 MB pages, Trail still improves performance by 1.6% over No-TLB-Prefetcher.As the 2 MB page fraction rises from 19% to 74%, speedup falls from 4.4% to 1.6%, while translation latency reduction falls from 14.3% to 5.7%.Source: Figure 17 · p. 13, §8.4 · p. 13
• Trail-Best improves performance across DRAM bandwidths from 400 to 4800 MTPS and consistently outperforms Recency.At 400 MTPS, Trail's speedup is 1.7% versus Recency's 0.7%; at 1600 MTPS and above, the values are 5.2% and 3.5%.Source: §8.4 · pp. 13–14, Figure 18 · p. 14

8.5. Contribution of Trail’s Components

• Component ablations show that per-PC tracking and virtualization improve Trail's speedup, stride detection adds further gain, and Next-Page complements the full design.The evaluation also sweeps in-PTE payloads from 2 to 10 bits per PTE and Trail-External payloads from 20 to 176 bits.Source: Figure 19 · p. 14, §8.5 · p. 14, §8.4 · p. 14

TLB Management and Hierarchy

• Larger or smarter TLBs, additional TLB levels, replacement policies, and cache-backed translation storage change translation reach or retention, while Trail predicts future translations.The cited works include,,, and.Source: §9 · p. 15

Speculative Address Translation

• Speculative address translation accelerates individual walks, whereas Trail predicts future demand translations; the approaches are largely orthogonal.Most of the cited speculative techniques also rely on specialized physical-memory or page-table-layout support, which Trail does not require.Source: §9 · p. 15

Repurposing Page-Table Metadata

• Trail embeds translation metadata in unused or available PFN bits, with hardware reading and writing that metadata during normal page-table walks.Other cited uses of PTE or per-page metadata include access tracking, compression, memory safety, and prefetch filtering.Source: §9 · p. 15

Data Prefetching

• Trail is complementary to data prefetching and runahead because it reduces the translation latency of their memory requests.The cited related work notes that virtual-address-based data prefetchers and runahead can trigger translations before demand accesses arrive.Source: §9 · p. 15

10. Conclusion

• Trail stores deltas in source-region PTEs and retrieves them during page table walks without additional memory accesses, scaling metadata capacity with application memory footprint.It requires only a 64-entry processor table and improves average performance by 5.7% single-core and 11.5% four-core, outperforming the best prior prefetcher by 1.7% and 2.5%, respectively.Source: §10 · p. 15
• Trail's reported benefits combine avoiding demand page table walks with shortening the walks it cannot eliminate, while causing negligible metadata writeback traffic.The conclusion also reports benefits when large pages back most memory and when no PTE bits are available, using an external delta table.Source: §10 · p. 15

A.1. Abstract

• The artifact reproduces Trail's comparisons, page-table-walk analysis, payload-budget sweeps, bandwidth sensitivity, component ablation, and four-core study.Evaluation is trace-driven, and the workflow uses three setup steps followed by one command per suite.Source: §A.1 · p. 19

A.2. Artifact check-list (meta-information)

• The artifact includes Virtuoso, Trail, Python analysis and plotting scripts, and a self-contained bash harness; its source and datasets are publicly available.The source is on the trail-artifact-release branch, while traces and page-table-walk dumps are public Hugging Face datasets.Source: §A.2 · p. 19, §A.3.1 · p. 20

A.3.1. How to access.

• The workflow requires an x86-64 machine and about 300 GB of free disk; a SLURM cluster is optional but recommended for the full sweep.The build and sanity check need ≈8 GB of RAM, and each simulation uses a few GB.Source: §A.3.2 · p. 20

A.3.2. Hardware dependencies.

• The software environment uses Linux, a C++17 toolchain, and Python 3.8+; Debian/Ubuntu dependencies are installed by the provided script.Network access is needed to download traces and fetch the decoder during the build; no proprietary tools are required.Source: §A.3.3 · p. 20

A.3. Description

• The workload suite spans datacenter, mobile, graph-analytics, SPEC CPU, HPC, and industrial traces, with a separate ≈3 GB page-table-walk-dump dataset for motivation figures.The traces and trace-lists are packaged together in the public trace dataset.Source: §A.3.4 · p. 20, §A.3.1 · p. 20

A.4. Installation

• Installation clones the repository, installs dependencies, then builds the simulator, downloads traces and dumps, and validates the artifact with short simulations.The build-and-validate step is resumable and reports a pass line with each smoke-test trace’s IPC.Source: §A.4 · p. 20

A.5. Experiment workflow and expected results

• The simulation suites cover prior-prefetcher comparisons, sensitivity studies, component ablation, and multicore evaluation; outputs include figures and tables with Markdown numbers.The trace-free motivation suite produces its figures from downloaded page-table-walk dumps rather than simulation.Source: §A.5 · pp. 20–21
• Expected outcomes include Trail ≈+5.7% over No-TLB-Prefetcher and +1.7% over Recency (single-core), and ≈+11.5% harmonic-mean speedup versus Recency’s ≈+8.7%.Single-core results are geometric means; multicore results are equal-work harmonic means across four cores, and exact values can vary slightly across machines and runs.Source: §A.5 · p. 20

A.6. Notes

• Experiment phases can be rerun without repeating completed work, and the artifact provides separate README files for the full workflow and motivation analyses.The workflow can run on SLURM or a single machine; a reduced instruction-count run provides a short end-to-end smoke test.Source: §A.5 · p. 20, §A.6 · p. 21