22 3. COARSE-GRAINED REPLACEMENT POLICIES
e two main challenges for hybrid policies are (1) accurately identifying the policy that
will be the most beneficial and (2) managing multiple policies at a low hardware cost. We now
discuss two solutions that address these challenges.
3.3.1 ADAPTIVE REPLACEMENT CACHE (ARC)
e Adaptive Replacement Cache (ARC) [Megiddo and Modha, 2003] combines the strengths
of recency and frequency by dynamically balancing recency- and frequency-based evictions. In
particular, ARC keeps track of two additional tag directories, L1 and L2, which together remem-
ber twice as many elements as the baseline cache can accommodate. e L1 directory maintains
recently used pages that have been seen only once, and the L2 directory maintains recently ac-
cessed pages that have been accessed at least twice. e goal of ARC is to dynamically choose
the appropriate amount of cache to dedicate to L1 and L2 (see Figure 3.10).
More concretely, ARC splits the baseline cache directory into two lists, T1 and T2, for
recently and frequently referenced entries, respectively. T1 and T2 are extended with ghost
lists (B1 and B2, respectively), which track recently evicted cache entries from T1 and T2, re-
spectively. Ghost lists only contain tag metadata, not the actual data, and entries are added to
ghost lists when the corresponding data is evicted from the cache. T1 and B1 together form the
Recency-Based L1 directory, and T2 and B2 together form the Frequency-Based L2 directory.
ARC dynamically modulates the cache space dedicated to T1 and T2. In general, hits in
B1 increase the size of T1 (proportion of cache dedicated to recently-accessed elements), and
hits in B2 increase the size of T2 (proportion of cache dedicated to elements accessed at least
twice). Evictions from T1 and T2 get added to B1 and B2, respectively.
3.3.2 SET DUELING
An issue with hybrid policies, such as ARC, is the large overhead of maintaining additional
tag directories. Qureshi et al. [2006] introduce Set Dueling, which is an accurate mechanism
for sampling the behavior of different policies at low hardware cost. Set Dueling builds on the
observation that a few randomly chosen sets can accurately represent the behavior of different
replacement policies on the entire cache. Qureshi et al. [2006] mathematically show that for
caches with 1–4 MB (1024–4096 sets), 64 sets are enough to capture the behavior of the entire
cache. We now discuss Set Dueling in more detail by discussing two representative policies.
Dynamic Insertion Policy (DIP) e dynamic insertion policy (DIP) combines the benefit of
recency-friendly policies and thrash-resistant policies by dynamically modulating the insertion
positions of incoming lines [Qureshi et al., 2007]. In particular, DIP alternates between the
recency-friendly LRU (Table 3.1) and the thrash-resistant Bimodal Insertion Policy (Table 3.6).
To choose between the two policies, DIP uses Set Dueling to dynamically track the hit
rate of each policy. Figure 3.11 shows that DIP dedicates a few sets to LRU (sets 0, 5, 10, and
15 in Figure 3.11) and a few sets to BIP (sets 3, 6, 9, and 12 in Figure 3.11). ese dedicated
3.3. HYBRID POLICIES 23
LRU
LRU
L
2
L
1
2cDBL
MRU
MRU
.
.
.
.
.
.
Figure 3.10: Adaptive replacement cache (ARC) maintains two tag directories; based
on [Megiddo and Modha, 2003].
sets are called set dueling monitors (SDMs), while the remaining sets are called the follower sets.
e policy selection (PSEL) saturating counter determines the winning policy by identifying
the SDM that receives more cache hits. In particular, the PSEL is incremented when the SDM
dedicated to LRU receives a hit, and it is decremented when the SDM dedicated to BIP receives
a hit (a k-bit PSEL counter is initialized to 2
k1
). e winning policy is identified by the MSB
of the PSEL. If the MSB of PSEL is 0, the follower sets use the LRU policy; otherwise the
follower sets use BIP. us, Set Dueling does not require any separate storage structure other
than the PSEL counter.
Dynamic Re-Reference Interval Policy (DRRIP) DRRIP builds on DIP to add scan-
resistance. In particular, DRRIP uses set dueling to create a hybrid of SRRIP, which is the
24 3. COARSE-GRAINED REPLACEMENT POLICIES
Sets dedicated to LRU
Sets dedicated to BIP
Miss in a Set
Dedicated to LRU
Miss in a Set
Dedicated to BIP
Decides Policy for
Follower Sets
Follower Sets
Policy decided by PSEL
MTD
Set 0
Set 1
Set 2
Set 3
Set 4
Set 5
Set 6
Set 7
Set 8
Set 9
Set 10
Set 11
Set 12
Set 13
Set 14
Set 15
+ –
PSEL
Figure 3.11: Set Dueling; based on [Qureshi et al., 2007].
scan-resistant version of LRU (Table 3.7), and BRRIP, which is the scan-resistant version of
BIP (Table 3.8).
As we will see in Chapter 4, the insight behind Set Dueling has had a large impact on
many subsequent Fine-Grained policies, which use the notion of set sampling to efficiently track
metadata to determine fine-grained caching behavior.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.