Control-flow history prediction cuts memory lookup misses nearly one third
CHiRP: Control-Flow History Reuse Prediction
Hardware Architecture
Summary
Memory in computers often needs to be translated from one form to another, and this translation uses a small, fast-memory cache called a TLB. When the TLB runs out of space, it must decide which entries to keep or remove to work best. The authors found that existing methods for predicting which entries will be reused don't work well for TLBs without changes. They created a new prediction method called CHiRP that uses the history of control flow to guess which entries will be reused, significantly reducing errors when looking up memory.
What this means in practice
- •For processor architects: Integrate CHiRP into TLB design to reduce miss rates and improve processor memory management efficiency.
- •For operating system developers: Use insights from CHiRP to optimize virtualization support by improving TLB replacement policies, thus speeding up virtual memory.
Authors
Samira Mirbagher-Ajorpaz, Elba Garza, Gilles Pokam, Daniel A. Jiménez
Abstract
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.