3.2. FREQUENCY-BASED POLICIES 19
cost of a diminished MC capacity. Unfortunately, subsequent work by Jain and Lin [2016] has
shown that to approach the behavior of Belady’s optimal policy, the policy needs a lookahead of
8 the size of the cache.
3.2 FREQUENCY-BASED POLICIES
Instead of relying on recency, Frequency-Based policies use access frequency to identify victims,
so lines that are accessed more frequently are preferentially cached over lines that are accessed
less frequently. is approach is less susceptible to interference from scans and has the benefit
of accounting for reuse behavior over a longer period of time, as opposed to just the last use.
e simplest Frequency-Based policy is the Least Frequently Used (LFU) policy [Coff-
man and Denning, 1973], which associates a frequency counter with each cache line. e fre-
quency counter is initialized to 0 when the line is inserted into the cache, and it is incremented
each time the line is accessed. On a cache miss, the candidate with the lowest frequency is
evicted. Table 3.9 summarizes these operations.
Table 3.9: Least frequently used (LFU) policy
Insertion Promotion Aging Victim Selection
Frequency = 0 Increment Frequency n/a Least Frequency
Unfortunately, Frequency-Based policies adapt poorly to changes in the application’s
phases because lines with high frequency counts from a previous phase remain cached in new
phases even when they are no longer being accessed. To address this issue, several solutions [Lee
et al., 2001, O’Neil et al., 1993, Robinson and Devarakonda, 1990, Shasha and Johnson, 1994]
augment frequency information with recency information to allow old lines to age gracefully.
Here we discuss two such solutions.
Frequency-Based Replacement (FBR) FBR [Robinson and Devarakonda, 1990] notes that
Frequency-Based methods are susceptible to misleadingly high counter values from short bursts
of temporal locality. erefore, FBR factors out locality from frequency counts by selectively
incrementing frequency counters. In particular, FBR does not increment frequency counters
for the top portion of the LRU stack, which is known as the new section. us, short bursts of
temporal locality do not affect the frequency counters. Figure 3.8 illustrates this strategy.
Unfortunately, this strategy has the disadvantage that once lines age out of the new section,
even frequently used lines are evicted quickly because they do not have enough time to build up
their frequency counts. erefore, FBR further restricts replacement to the least frequently used
line in an old section, which consists of lines that have not been recently accessed (bottom of the
LRU stack). e remaining part of the stack is called the middle section, which gives frequently
used lines sufficient time to build up their frequency values.
20 3. COARSE-GRAINED REPLACEMENT POLICIES
count : = 1
boundary
MISS
MRU … … LRU
(count
unchanged)
new section
count : = count + 1
Figure 3.8: FBR does not increment frequency counters in the new section; based on [Robinson
and Devarakonda, 1990].
Table 3.10 summarizes the operation of FBR policy.
Table 3.10: e frequency-based replacement (FBR) policy
Insertion Promotion Aging Victim Selection
MRU position
Frequency = 0
MRU position
Frequency++ if not in new section
Increment by 1
LFU line in old
section
Least Recently/Frequently Used (LRFU) e LRFU policy [Lee et al., 2001] builds on the
observation that the LRU and LFU policies represent extreme points of a spectrum of policies
that combine recency and frequency information (see Figure 3.9). Using a new metric called
Combined Recency and Frequency (CRF), LRFU explores this spectrum by allowing a flexible
tradeoff between recency and frequency.
Like Frequency-Based policies, LRFU accounts for each past reference to the block, but
unlike Frequency-Based policies, LRFU weighs the relative contribution of each reference by a
weighing function. In particular, LRFU computes for each block a CRF value, which is the sum
of the weighing function F .x/ for each past reference, where x is the distance of the past refer-
ence from the current time. us, for emulating purely Frequency-Based policies, the weighing
function can give equal priority to all past references, and for emulating Recency-Based policies,
the weighing function can give high priority to the last reference of the line.
LRFU uses the weighing function in Equation 3.1, where is an empirically chosen
parameter. e weighing function gives exponentially lower priority to older lines, which allows
LRFU to retain the benefits of FBR, while supporting graceful aging.
F
x
D
1
p
x
: (3.1)
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.