PaperlayerView exact revision on arXiv

Source-linked AI summary

CHiRP: Control-Flow History Reuse Prediction

Samira Mirbagher-Ajorpaz, Elba Garza, Gilles Pokam, Daniel A. Jiménez

arXiv:2610.07685v1cs.AR

TL;DR

TLB replacement has received little attention, although limited TLB capacity makes deciding which entries to evict important. The paper adapts predictive policies and introduces CHIRP, a TLB-focused reuse predictor. CHIRP reduces L2 TLB MPKI by 28.21% on average over LRU in the reported evaluation.

  • Problem

    TLB replacement has received little attention, despite insufficient capacity being a fundamental problem the paper targets through replacement policy.

    Source: §I · pp. 2–3

  • Method

    CHIRP uses a signature specially designed to correlate with TLB behavior to guide L2 TLB entry replacement.

    Source: §I · p. 3

  • Results

    28.21% average MPKI reduction over LRU: CHIRP yields 1.08 average MPKI, compared with 1.51 for LRU, 1.35 for SRRIP, 1.50 for SHiP, and 1.37 for GHRP.

    Source: A. MPKI Results · p. 9

  • Takeaways & Limitations

    CHIRP provides the strongest reported miss reduction among the compared policies, while simpler, lower-overhead SRRIP improves on LRU and may be more convenient to deploy.

    Source: A. MPKI Results · p. 9

    CHIRP updates prediction metadata on both hits and insertions, requiring more metadata accesses than SHiP.

    Source: E. Complexity and Efficiency · p. 11

Abstract

from arXiv · show

Translation Lookaside Buffers (TLBs) play a critical role in hardware-supported memory virtualization. To speed up address translation and reduce costly page table walks, TLBs cache a small number of recently-used virtual-to-physical address translations. TLBs must make the best use of their limited capacities. Thus, TLB entries with low potential for reuse should be replaced by more useful entries. This paper contributes to an aspect of TLB management that has received little attention in the literature: replacement policy. We show how predictive replacement policies can be tailored toward TLBs to reduce miss rates and improve overall performance. We begin by applying recently proposed predictive cache replacement policies to the TLB. We show these policies do not work well without considering specific TLB behavior. Next, we introduce a novel TLB-focused predictive policy, Control-flow History Reuse Prediction (CHiRP). This policy uses a history signature and replacement algorithm that correlates to known TLB behavior, outperforming other policies. For a 1024-entry 8-way set-associative L2 TLB with a 4KB page size, we show that CHiRP reduces misses per 1000 instructions (MPKI) by an average 28.21% over the least-recently-used (LRU) policy, outperforming Static Re-reference Interval Prediction (SRRIP), Global History Reuse Policy (GHRP) and SHiP, which reduce MPKI by an average of 10.36%, 9.03% and 0.88%, respectively.

I. INTRODUCTION

TLB misses are costly, but expanding TLB capacity is constrained by access latency and physical limits. This paper studies predictive replacement for TLBs and introduces CHIRP, a policy tailored to TLB reuse behavior.

I. INTRODUCTION

  • TLBs cache recently retrieved virtual-to-physical mappings to reduce costly page-table walks, while their limited size reflects power, timing, and area constraints.Larger L2 TLBs can incur higher access latencies because the TLB lies on the memory-access critical path.Source: §I · p. 2
  • TLB replacement policy has received little attention; prior work often uses LRU, reduces page-walk cost, or increases TLB size.The paper instead targets insufficient capacity by improving replacement policy.Source: §I · p. 3
  • CHIRP uses a TLB-oriented signature to guide replacement and outperforms the adapted predictive policies in prediction accuracy and performance.The study focuses on the L2 TLB because its misses account for most cycles spent in the TLB miss handler.Source: §I · p. 3
  • The paper adapts predictive policies developed for last-level caches and finds their features do not correlate well with TLB reuse, producing negligible gains.TLBs have tighter access timing requirements than LLC-focused predictors designed to tolerate several prediction-table accesses.Source: §I · p. 3
  • CHIRP reduces L2 TLB misses by 28.21% on average over LRU, yielding a 4.8% geometric mean speedup at a 150-cycle page-walk latency.The reported speedup is for the stated page-walk latency.Source: §I · p. 3

II. BACKGROUND

Predictive replacement estimates whether an entry will be reused and evicts entries predicted to be dead. Its success depends on choosing features and prediction mechanisms suited to the structure, particularly when access timing is tight.

II. BACKGROUND

  • Predictive replacement predicts whether a cached item will be used again and makes entries predicted not to be reused candidates for eviction.Unlike LRU, a dead block need not move down the recency stack before replacement.Source: §II · p. 3
  • Features that correlate with reuse differ across structures and applications, so cache or BTB predictors may not transfer effectively to TLBs.PC-based SDBP and SHiP reduce dead blocks in LLCs but can be detrimental to instruction caches and BTBs; the authors report the same applies to TLBs.Source: §II · pp. 3–4
  • A predictor must combine correlating features into an efficient signature and use a fast, low-cost algorithm, especially for a TLB on the memory-access critical path.The paper explores predictive cache policies and proposes CHIRP to guide TLB entry replacement.Source: §II · p. 4
  • For L2 TLB reuse prediction, the authors combine multiple features in one signature and use a single prediction table to reduce access latency.This contrasts with LLC approaches that combine predictions from multiple indices or signatures.Source: §II · p. 4

A. Static Re-Reference Interval Prediction

This background describes predictive replacement approaches adapted to TLBs, including reuse prediction, PC-based sampling, branch-history signatures, and offline learning. Their mechanisms illustrate how prediction inputs and update rules differ.

A. Static Re-Reference Interval Prediction

  • SRRIP assigns each TLB entry a 2-bit re-reference prediction value, revises it on reuse or replacement, and evicts entries predicted to be distant from reuse.If no distant-reuse entry exists, the set's values are incremented until an eviction candidate appears.Source: A. Static Re-Reference Interval… · p. 4

B. PC-Based Dead Block Predictors

  • Sampling generalizes poorly for L2 TLBs because a PC accesses far fewer TLB entries than cache blocks, limiting cross-entry reuse generalization.The authors therefore evaluate SHiP with PC bits stored as metadata in each TLB entry rather than relying on a smaller sampler.Source: B. PC-Based Dead Block Predictors · p. 4

C. Global History Reuse Prediction

  • GHRP indexes reuse counters using conditional-branch global history and lower-order branch-address bits, adapting an instruction-stream signature to replacement prediction.The paper adapts this BTB and instruction-cache policy for TLB replacement.Source: C. Global History Reuse Prediction · p. 4

D. Offline Learning

  • The authors use offline ADALINE learning to identify handcrafted control-flow features for a simpler linear model used in online prediction.ADALINE weights represent correlations between input vectors and target values, and are updated after the desired outcome is known.Source: D. Offline Learning · p. 4

E. CHIRP

The paper argues that TLB reuse prediction needs features suited to its coarser access granularity and combines them into CHIRP's signature. Its experiments identify shortcomings in PC-based prediction and show how history composition and selective updates address them.

E. CHIRP

  • TLB accesses are coarser than cache accesses: multiple PCs can map to one TLB entry, and their contexts may lead to either reuse or eviction.The authors combine multiple features into one signature to improve prediction accuracy while reducing overhead.Source: E. CHIRP · p. 5

III. THE REUSE PREDICTION PROBLEM IN TLB & OUR SOLUTION

  • 0.88% MPKI reduction: PC-based SHiP performs only slightly better than LRU when applied to TLB reuse prediction.SHiP uses only the most recent instruction's PC as its signature.Source: §III · p. 5
  • Prediction errors persist without table aliasing: unlimited-size SHiP reduces MPKI by only 0.63%, and the authors attribute prior-policy inaccuracy to conflicts within sets rather than among sets.Restricting prediction to a subset of TLB sets and using LRU elsewhere yields only a 1.28% MPKI reduction.Source: §III · p. 5
  • Coarse TLB granularity lets many PCs access the same entry, increasing aliasing and causing prediction counters to saturate too quickly.The paper notes that a 4KB page is nearly two orders of magnitude larger than a 64B cache block.Source: §III · p. 5
  • 5.85% average MPKI reduction: Selective Hit Update limits counter updates to hits from a TLB set different from the last accessed set.The method is introduced to slow counter updates and reduce noise.Source: §III · p. 5
  • Global PC history provides no additional speedup beyond length 15, whereas adding branch-path history lets CHIRP benefit from histories longer than 30.The authors attribute the difference to the coarse-grained nature of TLB accesses limiting the information captured by global PC history.Source: §III · p. 5, Figure 2 · p. 5
  • Branch history can reflect data accesses when global path history does not and can expose program semantics relevant to TLB misses.Source: §III · p. 5

A. PC Bits Carry Uneven Weights

The section identifies PC bits 2 and 3 as important reuse predictors, then describes shifting and scaling signature bits to reduce aliasing and improve prediction. These techniques support a smaller prediction table and reduce TLB MPKI.

A. PC Bits Carry Uneven Weights

B. Modeling Efficient Signatures

IV. CONTROL-FLOW HISTORY REUSE PREDICTION ALGORITHM

CHiRP combines control-flow history and the current PC into a signature that tracks each TLB entry’s reuse. The signature indexes a prediction table whose status informs replacement.

A. Overview

  • The signature identifies each TLB entry and indexes a prediction table that tracks reuse and supplies status for a later replacement decision.Source: A. Overview · p. 6

B. CHIRP Signature

  • Global path history records the last 16 accesses; conditional and unconditional indirect branch histories each record the last 8 branch accesses of their type.Source: B. CHIRP Signature · p. 6
  • CHiRP combines global path history, conditional and indirect branch histories, and the shifted current PC into a signature.Source: B. CHIRP Signature · p. 6

C. CHIRP Prediction Table

CHiRP uses a signature-indexed saturating-counter table to predict whether L2 TLB entries are dead or live. On a miss it prefers predicted-dead entries, falling back to LRU, while limiting predictor-table updates.

C. CHIRP Prediction Table

  • Each L2 TLB entry stores a 16-bit signature and prediction bit alongside LRU position bits and validity; a thresholded saturating counter predicts deadness.Source: C. CHIRP Prediction Table · p. 7

D. CHIRP Operations

  • A miss selects a predicted-dead entry when available; otherwise CHiRP evicts the LRU entry and increments the victim signature’s counter.Source: D. CHIRP Operations · pp. 7–8
  • CHiRP updates the prediction table on only 10.14% of TLB accesses, limiting predictor accesses while improving performance and energy.Source: D. CHIRP Operations · p. 8
  • On a hit, CHiRP consults the table on the entry’s first hit, updates the old signature’s counter, then uses the new signature’s counter to set prediction metadata.Source: D. CHIRP Operations · p. 8

E. Adapting Training Algorithm for TLB

CHiRP limits prediction-table training to two events to keep reuse prediction fast and energy efficient. This reduces prediction-table accesses relative to SHiP and GHRP.

V. METHODOLOGY

The evaluation uses 870 industry-sourced traces and a timing-approximate performance model to compare TLB replacement policies. It focuses on a 4KB page size, leaving replacement across mixed page sizes for future work.

V. METHODOLOGY

  • 870 industry-sourced traces from varied workload categories drive the simulations; short traces run completely and long traces run for 100 million instructions.The traces include instruction types, register values, effective addresses, and load/store data values.Source: §V · p. 8
  • The timing-approximate model measures MPKI and IPC across page-table-walk latencies, including a 20-to-340-cycle range.It models L1 TLBs, caches, DRAM, branch prediction, and an in-order pipeline.Source: §V · pp. 8–9
  • The study models SRRIP, SHiP, GHRP, and CHIRP; CHIRP tracks per-entry metadata and uses a prediction table with two-bit counters.For the stated 1024-entry, 8-way L2 TLB, each entry adds a prediction bit, three LRU-position bits, and a 16-bit signature.Source: §V · p. 9
  • The evaluation assumes 4KB pages, a common page size, and does not address replacement among mixed page sizes.Mixed-size replacement and its interaction with memory fragmentation are left for future work.Source: §V · p. 9

VI. RESULTS

CHIRP achieves the largest reported average MPKI reduction over LRU, and its advantage also appears in speedup measurements as TLB miss penalties rise. It accesses its prediction table less often than competing predictive policies.

A. MPKI Results

  • LRU’s case as a TLB replacement policy is weak because Random slightly outperforms it; lower-overhead SRRIP is easier to deploy, while CHIRP is more complex.The results section describes CHIRP as providing more than double SRRIP’s improvement.Source: A. MPKI Results · p. 9

B. Accesses to Prediction Table

  • Figure 6 compares feature correlation, input transformation, bit shifting and scaling, signature formulas, and prediction-table update policies by MPKI reduction over LRU across 870 traces.Its caption reports an advantage for CHIRP.Source: Figure 6 · p. 10

A. MPKI Results

  • CHIRP yields an average 1.08 MPKI, a 28.21% improvement over LRU; SRRIP, GHRP, and SHiP reduce misses over LRU by 10.36%, 9.03%, and 0.88%, respectively.Figure 7 orders benchmarks on the horizontal axis by sorted LRU MPKI.Source: A. MPKI Results · p. 9, Figure 7 · p. 10

B. Accesses to Prediction Table

  • CHIRP accesses the prediction table for 10.14% of L2 TLB accesses on average, while SHiP and GHRP show high variance and can exceed 100%.The rate can exceed 100% when a TLB access triggers both a prediction-table read and a training update.Source: B. Accesses to Prediction Table · p. 10

C. Speedup

  • At a 320-cycle TLB miss penalty, CHIRP provides over 10% speedup; at 150 cycles, it improves performance by 4.80%.At 150 cycles, the reported improvements are 0.42% for Random, 1.65% for SRRIP, 0.13% for SHiP, and 0.94% for GHRP.Source: C. Speedup · p. 10, Figure 8 · p. 11

D. TLB Efficiency

Across 870 traces, CHiRP improves L2 TLB efficiency over LRU and removes most dead entries. Its gains persist across predictor sizes, while predictor updates and hardware budgets shape the cost.

D. TLB Efficiency

  • 8.07% average cache-efficiency improvement over LRU across 870 traces; CHiRP also removes most dead TLB entries.GHRP improves average cache efficiency by 2.92%, SHiP by 1.85%, SRRIP by 2.84%, and Random by 3.10%.Source: D. TLB Efficiency · p. 11

E. Complexity and Efficiency

  • CHiRP reduces prediction-table accesses by 90% versus SHiP and GHRP, but updates TLB metadata on hits as well as insertions, unlike SHiP.CHiRP is more complex than LRU and RRIP, though the authors consider its complexity manageable given the benefits.Source: E. Complexity and Efficiency · p. 11

F. Impact of Predictor Size

  • At 1KB and 2KB predictor-table sizes, CHiRP yields about 28% MPKI reduction; the reported main results use a 1KB budget.A 128B table yields up to 7% MPKI improvement, while 256B and 512B yield up to 20% and 22%, respectively; larger tables bring greater area overhead.Source: F. Impact of Predictor Size · p. 11, Figure 9 · p. 11

G. Performance Gain

  • 4.8% speedup over LRU is statistically significant across 870 workloads at a 150-cycle TLB miss penalty.The study focuses on single-core performance.Source: G. Performance Gain · p. 11

H. Area Overhead vs. Performance

With 1KB of hardware overhead, CHiRP delivers 4.80% speedup and is 13× more efficient in speedup per KB overhead than the cited branch-prediction technique. The paper situates this design among prior reuse-prediction work and concludes that its signature addresses TLB-specific prediction constraints.

H. Area Overhead vs. Performance

  • With 1KB hardware overhead, CHiRP achieves 4.80% speedup and 13× greater speedup-per-KB overhead efficiency than the cited 64KB branch-prediction technique.The signature formula lets CHiRP use one prediction table instead of GHRP's three, reducing hardware overhead by two-thirds.Source: H. Area Overhead vs. Performance · p. 12

A. Reuse Prediction

  • Earlier dead-block prediction work addressed caches and other structures, but no prior replacement policy applied dead-block prediction to TLBs.The paper also reviews prior work on reuse prediction, including counter-based prediction, burst-based prediction, and perceptron learning.Source: A. Reuse Prediction · p. 12

B. Translation Lookaside Buffers

  • Superpages can reduce TLB misses, but may increase memory footprint and paging traffic, while multiple page sizes add OS complexity.Mapping smaller pages into a superpage TLB entry can reduce splintering but requires deep OS-hardware co-design.Source: B. Translation Lookaside Buffers · p. 12

VIII. CONCLUSIONS AND FUTURE WORK

  • CHiRP's control-flow-informed signature tracks dead-block traces at large granularity, enabling a small table with fast convergence for L2 TLB constraints.The authors identify extending CHiRP to mixed-page-size TLBs as future work.Source: §VIII · p. 13

Related papers

Loading 2610.07685v1…