3.1. RECENCY-BASED POLICIES 13
Most recently used
Protected segment
Least recently used
Most recently used
Probationary segment
Least recently used
Hits
Hits
Misses
Discarded lines
Discarded lines
Figure 3.4: e Seg-LRU replacement policy; based on [Karedla et al., 1994].
A variant of the Seg-LRU policy won the First Cache Replacement Championship [Gao
and Wilkerson, 2010].
3.1.2 BEYOND LRU: INSERTION AND PROMOTION POLICIES
Qureshi et al. [2007] observe that variants of Recency-Based policies can be realized by modify-
ing the insertion policy, while keeping the eviction policy unchanged (evict the line in the LRU
position). For example, MRU (Table 3.2) can be emulated by using the LRU Insertion policy
(LIP) [Qureshi et al., 2007], which inserts new lines in the LRU position instead of the MRU
position (see Table 3.5).
Table 3.5: e LRU insertion policy (LIP) emulates MRU
is insight spurred the design of replacement policies with new insertion and promotion
policies. By interpreting recency information in different ways, these policies can address much
broader classes of access patterns than LRU. In this section, we discuss some notable solutions
in this direction. Since applications typically consist of many different access patterns, none of
14 3. COARSE-GRAINED REPLACEMENT POLICIES
these policies is sufficient on its own and is typically used as part of a hybrid solution, which we
discuss in Section 3.3.
Bimodal Insertion Policy (BIP) Since thrash-resistant policies like LIP (and MRU) cannot
adapt to changes in the working set during phase changes, BIP [Qureshi et al., 2007] modifies
LIP such that lines are occasionally (with a low probability) inserted in the MRU position. BIP
maintains the thrash-resistance of LIP because it inserts in the LRU position most of time, but
it can also adapt to phase changes by occasionally retaining newer lines. Table 3.6 shows that
BIP inserts in the MRU position with a probability of , which is set to be 1=32 or 1=64. An
value of 1 inserts in the MRU position (mimicking LRU’s insertion policy), and an value of 0
inserts in the LRU position (mimicking LIP’s insertion policy). us, from an implementation
point of view, BIP’s parameter unifies all insertion policies that lie at different points in the
spectrum between LRU and MRU insertion.
Table 3.6: e bimodal insertion policy (BIP)
Insertion Promotion Aging Victim Selection
MRU position with
probability
MRU position Move 1 position
toward LRU
LRU position
Static Re-Reference Interval Prediction (SRRIP) Jaleel et al. [2010b] observe that cache
replacement can be thought of as a Re-Reference Interval Prediction (RRIP) problem, and the
conventional LRU chain can be instead thought of as an RRIP chain; while a line’s position in
the LRU chain represents the amount of time since its last use, a line’s position in the RRIP
chain represents the order in which it is predicted to be re-referenced [Jaleel et al., 2010b]. In
particular, the line at the head of the RRIP chain is predicted to be re-referenced the soonest
(shortest re-reference interval), while the line at the tail of the RRIP chain is predicted to be
reused furthest in the future (largest re-reference interval). On a cache miss, the line at the tail
of the RRIP chain is replaced.
With this view, we can see that the LRU policy predicts that new lines will have a near-
immediate re-reference interval (insert at the head of the RRIP chain), while the thrash-resistant
LIP policy predicts that new lines will have a distant re-reference interval (insert at the tail of the
RRIP chain). Figure 3.5 illustrates this point with an RRIP chain that is represented using a 2-
bit Re-Reference Prediction Value (RRPV): 00 corresponds to the nearest re-reference interval
prediction, 11 corresponds to a distant re-reference interval prediction.
Jaleel et al. [2010b] show that instead of predicting re-reference intervals that lie at the
extreme ends of the RRIP chain, there is great benefit in predicting an intermediate re-reference
interval, which allows the replacement policy to accommodate a mixture of different access pat-
terns. In particular, scans—a burst of references to data that is not reused—disrupt recency-
3.1. RECENCY-BASED POLICIES 15
0 1 2 3
Promotion
Age
Insertion
Eviction
(SRRIP)
Scan-Resistant
Insertion
( MRU )
Thrash-Resistant
Age
Age
Insertion
( LRU)
Recency-Friendly
Figure 3.5: An example RRIP chain with 2-bit RRPV values.
friendly policies, such as LRU, because they discard the working set of the application without
yielding any cache hits. To accommodate mixes of recency-friendly accesses and scans, Jaleel
et al. [2010b] propose SRRIP, which gives incoming lines an intermediate re-reference interval
and then promotes lines to the head of the chain if they are reused. us, SRRIP adds scan-
resistance to recency-friendly policies, as it prevents lines with a distant re-reference interval
(scans) from evicting lines with a near re-reference interval.
In the most general case, SRRIP associates an M-bit value per cache block to store its
Re-Reference Prediction Value (RRPV), but Jaleel et al. [2010b] find that a 2-bit RRPV value
is sufficient to provide scan-resistance. Table 3.7 summarizes the operations of SRRIP with a
2-bit RRPV value.
Table 3.7: Static re-reference interval prediction policy (SRRIP)
Like LRU, SRRIP thrashes the cache when the re-reference interval of all blocks is larger
than the available cache. To add thrash-resistance to scan-resistant policies, Jaleel et al. [2010b]
propose Bimodal RRIP (BRRIP), a variant of BIP [Qureshi et al., 2007] that inserts a majority of
cache blocks with a distant re-reference interval prediction (i.e., RRPV of 3), and it infrequently
inserts cache blocks with an intermediate re-reference interval prediction (i.e., RRPV of 2).
BRRIP’s operations are summarized in Table 3.8.
16 3. COARSE-GRAINED REPLACEMENT POLICIES
Table 3.8: Bimodal re-reference interval prediction policy (BRRIP)
Insertion Promotion Aging Victim
Selection
RRPV=3 for most insertions,
RRPV=2 with probability
RRPV = 0 Increment all RRPVs
(if no line with RRPV = 3)
RRPV = 3
Since applications can alternate between recency-friendly and thrashing working sets,
neither SRRIP nor BRRIP is sufficient on its own. In Section 3.3, we will discuss hyrbid versions
of SRRIP and BRRIP that can address all three of the common access patterns (recency-friendly,
thrashing and scans), yielding performance improvements for many applications.
Protecting Distance-Based Policy (PDP) e PDP policy [Duong et al., 2012] is a general-
ization of RRIP as it dynamically estimates a Protecting Distance (PD), and all cache lines are
protected for PD accesses before they can be evicted. e PD is a single value that is used for
all lines inserted into the cache, but it is continually updated based on the application’s dynamic
behavior.
To estimate the PD, PDP computes the reuse distance distribution (RDD), which is the
distribution of reuse distances observed within a recent interval of the program’s execution. Using
the RDD, the PD is defined to be the reuse distance that covers a majority of lines in the cache,
such that most lines are reused at the PD or smaller distance. For example, Figure 3.6 shows the
RDD for 436.cactusADM, where the PD is set to be 64. e PD is recomputed infrequently
using a small special-purpose processor.
0 12864 192 256 0 12864 192 256 0 12864 192 256 0 12864 192 256 0 12864 192 256
403.gcc 436.cactusADM 450.soplex 464.h264ref 482.sphinx3
Figure 3.6: Protecting distance covers a majority of lines (for example, 64 for 436.cactusADM);
based on [Duong et al., 2012].
More concretely, on an insertion or promotion, each cache line is assigned a value to rep-
resent its remaining PD (RPD), which is the number of accesses for which it remains protected;
this value is initialized to the PD. After each access to a set, the RPD of each line in the set
is aged by decrementing the RPD value (saturating at 0). A line is protected only if its RPD is
larger than 0. An unprotected line is chosen as the victim.
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset