30 4. FINE-GRAINED REPLACEMENT POLICIES
vs. cache-friendly) using a skewed predictor design, making these predictions at the granular-
ity of PCs; and (3) SDBP bypasses all incoming blocks that are predicted to be cache-averse,
with the remaining lines being managed using the baseline replacement policy, so false positives
(cache-averse blocks that are predicted to be cache-friendly) are aged out using the baseline
replacement policy, and false negatives (cache-friendly blocks that are predicted to be cache-
averse) do not get any opportunity to see reuse.
4.2.2 SIGNATURE BASED HIT PREDICTION (SHIP)
Like SDBP, SHiP [Wu et al., 2011a] learns the eviction behavior of the underlying replacement
policy,
1
but the main insight behind SHiP is that reuse behavior is more strongly correlated with
the PC that inserted the line into the cache rather than with the PC that last accessed the line.
us, on a cache eviction, SHiP’s predictor is trained with the PC that first inserted the line on
a cache miss, and the predictor is only consulted on cache misses (on hits, lines are promoted to
the highest priority without consulting the predictor).
More specifically, SHiP trains a predictor that learns whether a given signature has near
or distant re-reference intervals. A few sets are sampled in the cache to maintain signatures and
train the predictor. On a cache hit in a sampled set, the signature associated with the line is
trained positively to indicate a near re-reference, and on an eviction of a line that was never
reused, the signature is trained negatively to indicate a distant re-reference. When a new line is
inserted, the signature of the incoming line is used to consult the predictor and determine the
re-reference interval of the incoming line (prediction is performed for all accesses, not just the
sampled sets). Once inserted into the cache, lines are managed using a simple RRIP policy (see
Table 4.2).
Table 4.2: Signature based hit prediction (SHiP)
Insertion Promotion Aging Victim Selection
If (prediction) RRPV = 2
else RRPV = 3
RRPV = 0
Increment all RRPV's
(if no line with RRPV = 3)
RRPV = 3
e choice of signature is critical to SHiP’s effectiveness. Jaleel et al. [2010b] evaluate a
program counter signature (PC), a memory region signature, and an instruction sequence history
signature, and they find that the PC signature performs best.
SHiP builds on DRRIP [Jaleel et al., 2010b] to create a Fine-Grained policy. Whereas
DRRIP makes uniform re-reference predictions for all cache lines in an epoch, SHiP makes
finer-grained predictions: it categorizes incoming lines into different groups by associating each
reference with a unique signature. Cache lines with the same signature are assumed to have sim-
1
A minor difference is that SDBP learns the LRU solution, whereas SHiP learns from SRRIP.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.