TLB reuse is coarser than cache reuse
A translation lookaside buffer caches virtual-to-physical address mappings so that most memory accesses avoid a page table walk. When the TLB is full, a replacement policy chooses which mapping to discard. The paper argues that this choice has received little attention: prior TLB work mostly uses LRU or Random, or attacks miss penalty and TLB size instead.
The authors start from predictive replacement policies built for the last-level cache, where a block predicted to be dead — not reused before eviction — is a good eviction candidate. They apply SRRIP, SHiP and GHRP to the TLB and find the gains are small. The reason is granularity: many program counters map to the same TLB entry, roughly 64 times more than to a cache block, and each of those PCs may cause either a reuse or an eviction depending on context. A signature that works for cache lines therefore does not automatically identify dead TLB entries.
A signature built from control flow, not just the PC
CHiRP combines four features into one signature: a 64-bit global path history of PCs, a 64-bit conditional branch address history, a 64-bit unconditional indirect branch address history, and the current PC shifted right by two bits. The signature is formed by XOR-ing these components, then hashed with Robert Jenkins' 64-bit mix function and reduced modulo the table size to index a single prediction table.
Two design choices follow from measurements in the paper. First, the global path history shifts in only the two lower-order PC bits (bits 2 and 3) plus two zero bits, because an offline-trained ADALINE weight analysis showed those bits correlate most strongly with TLB reuse. Second, the branch histories record branch PCs rather than branch outcomes or targets. The authors report that global PC history alone stops helping beyond a length of about 15, while adding branch path history lets CHiRP benefit from histories longer than 30.
Counters learn which signatures precede eviction
Each TLB entry carries a 16-bit signature, a one-bit prediction of whether it is dead, a first-hit bit and three bits of LRU position. The prediction table holds two-bit counters indexed by the hashed signature. When an entry is evicted without having been reused, the counter for its signature is incremented; when an entry is reused, the counter is decremented. A counter above a threshold marks the entry dead, and dead entries are chosen as victims before falling back to LRU.
The training is deliberately sparse. The table is updated only on the first hit to an entry and on a miss in a set with no dead entry. The paper reports this reduces prediction-table accesses to 10.14% of all TLB accesses, about 90% fewer than SHiP and GHRP, which must consult their tables on every access. Selective Hit Update, which limits updates to hits of a TLB set different from the last one accessed, is credited with a further 5.85% average MPKI reduction by slowing counter saturation.
The measured gap over LRU and cache policies
The headline comparison is misses per 1000 instructions on a 1024-entry, 8-way set-associative L2 TLB with 4KB pages. Relative to LRU, CHiRP reduces MPKI by an average 28.21%. SRRIP reaches 10.36%, GHRP 9.03% and SHiP only 0.88%. These are averages over 870 Qualcomm-supplied traces spanning SPEC, database, crypto, scientific, web and big-data categories, simulated with a timing-approximate model.
MPKI is not the same as speed. The paper also reports a geometric-mean speedup of 4.8% at a 150-cycle page walk latency, and measures speedup across a 20-to-340-cycle range of L2 TLB miss penalties. Readers comparing policies should keep the two measures separate: a miss-rate reduction of 28.21% and a 4.8% speedup answer different questions, and the speedup depends on the assumed miss penalty.
Shifting and scaling bits keeps a small table accurate
Aliasing is harder to control in the TLB than in a cache because so many PCs share one entry. If a counter flips direction often, a small table becomes useless. CHiRP addresses this by injecting and shifting leading zeros into specific bit positions of the signature components, following shifting and scaling techniques the authors attribute to LeCun and Hinton. This makes less salient history bits less visible to the learning process.
The paper quantifies one step of this: adding conditional branch path history to the signature reduces MPKI by 23.88%, and adding two leading zeros in the path history raises that to 26.98%. The authors state the resulting table converges with three times fewer entries than GHRP. Storage for the 1024-entry configuration totals 2.775KB to 8.265KB depending on counter count, including 2KB of signatures and 128B each for prediction bits and first-hit bits.
Where the result does not yet transfer
All reported numbers come from simulation, not silicon. The traces are industry-sourced and the performance model is timing-approximate, so the 28.21% MPKI reduction and 4.8% speedup are model results under the stated configuration.
The study fixes page size at 4KB. The authors explicitly defer mixed page sizes, noting that when one entry covers 4KB and another 2MB, replacement is no longer a pure Bélády-style problem and must weigh the different costs of evicting different-sized entries. They also note that sampling, used for larger cache structures, does not work in the L2 TLB, which is why CHiRP generalizes learning at the granularity of TLB entries instead.
The priority is signature design, not table size
The paper's most decision-relevant claim is a comparison, not a single number: on the same 1024-entry L2 TLB, a signature built around control-flow history and TLB-specific bit weighting buys far more than porting a cache policy. CHiRP's 28.21% average MPKI reduction over LRU is roughly 2.7 times SRRIP's 10.36% and more than three times GHRP's 9.03%, while SHiP's 0.88% shows that a cache-proven PC-based signature barely transfers.
For a designer weighing TLB replacement options, that ordering suggests the leverage lies in which features the signature captures and how aliasing is suppressed, since CHiRP reaches its result with a single prediction table accessed on only 10.14% of TLB accesses. The open question the authors leave is whether the same advantage survives mixed page sizes, where eviction cost depends on entry size.
Sources used in this answer
CHiRP: Control-Flow History Reuse Prediction
On a simulated 1024-entry 8-way L2 TLB with 4KB pages, CHiRP reduced misses per 1000 instructions by an average 28.21% over LRU across 870 traces, versus 10.36% for SRRIP, 9.03% for GHRP and 0.88% for SHiP.