3.1. RECENCY-BASED POLICIES 17
Genetic Insertion and Promotion for PseudoLRU Replacement (GIPPR) Taking inspira-
tion from RRIP, Jiménez [2013] observe that there are many degrees of freedom in the choice
of insertion and promotion, so they generalize modifications to insertion and promotion poli-
cies using the concept of an Insertion/Promotion Vector (IPV). e IPV specifies a block’s new
position in the recency stack both when it is inserted into the cache and when it is promoted
from a different position in the recency stack. In particular, for a k-way set-associative cache,
an IPV is a k C 1-entry vector of integers ranging from 0 to k 1, where the value in the i
th
position represents the new position to which a block in position i should be promoted when it
is re-referenced. e k
th
entry in the IPV represents the position where a new incoming block
should be inserted. If the new position in the recency stack is less than the old position, then
blocks are shifted down to make room; otherwise blocks are shifted up to make room.
Figure 3.7 shows two sample IPVs, with the first one representing LRU, and the second
one representing a more sophisticated insertion and promotion strategy.
While the generalized notion of IPVs is quite powerful, the number of possible IPVs
grows exponentially, (k
kC1
possible IPVs for a k-way cache), so Jiménez [2013] use an offline
genetic search to evolve good IPVs for the SPEC 2006 benchmarks. e genetic search yielded
the IPV shown in the bottom part of Figure 3.7.
Just as there is no single insertion policy or RRIP policy that works for all workloads, the
best IPV differs for each workload. erefore, Jiménez [2013] present a hybrid solution that
uses set dueling (described in Section 3.3) to consider multiple IPVs.
3.1.3 EXTENDED LIFETIME RECENCY-BASED POLICIES
Extended Lifetime Policies are a special class of Recency-Based policies that artificially extend
the lifetimes of some cache lines by storing them in an auxiliary buffer or a victim cache. e key
motivation here is to defer eviction decisions to a later time when a more informed decision can
be made. is strategy allows Coarse-Grained policies to slightly expand the reuse window of
cache hits to be larger than the size of the cache.
Shepherd Cache e Shepherd Cache (SC) mimics Belady’s optimal policy [Rajan and
Govindarajan, 2007]. Since Belady’s policy requires knowledge of future accesses, Rajan and
Govindarajan emulate this future lookahead with the help of an auxiliary cache, called the Shep-
herd Cache. In particular, the cache is logically divided into two components, the Main Cache
(MC) which emulates optimal replacement, and the SC which uses a simple FIFO replacement
policy. e SC supports optimal replacement for the MC by providing a lookahead window.
New lines are initially buffered in the SC, and the decision to replace a candidate from the MC
is deferred until the new line leaves the SC. While the new line is in the SC, information is
gathered about the reuse order of replacement candidates in the MC. For example, candidates
that are reused earlier become less likely candidates for eviction since Belady’s policy evicts the
lines that is reused furthest in the future. When the new line is evicted from the SC (due to other
insertions in the SC), a replacement candidate is chosen by either picking a candidate from the
18 3. COARSE-GRAINED REPLACEMENT POLICIES
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
insertion eviction
insertion eviction
(a) Transition Graph for LRU. A solid edge points to the new position for an accessed or inserted
block. A dashed edge shows where a block is shifted when another block is moved to its position.
(b) Transition Graph for Vector [0 0 1 0 3 0 1 2 1 0 5 1 0 0 1 11 13].
Figure 3.7: IPV for LRU (top), and the IPV evolved using genetic algorithm (bottom); based
on [Jiménez, 2013].
MC that hasn’t been reused within the lookahead window, or the candidate that was reused
last; if all lines in the MC were reused before the SC line was reused, then the SC line replaces
itself. Although SC and MC are logically separate, Rajan and Govindarajan [2007] avoid any
movement of data from one component to another by organizing the cache such that the two
logical components can be organized as a single physical structure.
us, the SC emulates a superior replacement scheme for lines in the MC cache by ex-
tending their lifetime with the help of the SC. e tradeoff for SC is that replacement in the
MC approaches true optimality with high lookaheads, and the higher lookahead comes at the
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.