4.2. CLASSIFICATION-BASED POLICIES 33
To answer the questions at the beginning of the section: (1) Hawkeye learns from the op-
timal caching solution, instead of learning from LRU or SRRIP; (2) Hawkeye learns the optimal
solution using a PC-based predictor; and (3) Hawkeye also relies on RRIP’s aging mechanism
to age lines that are inserted with high priority. To correct for inaccurate predictions, Hawkeye
also trains the predictor negatively when a line that was predicted to be cache-averse is evicted
without being reused.
Hawkeye makes an interesting conceptual contribution: it phrases cache replacement as
a supervised learning problem,
4
which is surprising because unlike branch prediction, where the
program execution eventually provides the correct outcomes of each branch, hardware caches
do not provide such labeled data. By applying the optimal solution to past events, Hawkeye
provides labeled data, which suggests that the field of cache replacement might benefit from the
vast research in supervised learning.
4.2.4 PERCEPTRON-BASED PREDICTION
Predictive policies depend heavily on the accuracy of their predictors. SDBP, SHiP, and Hawk-
eye all use PC-based predictors that achieve accuracies of around 70–80%. Jiménez and Teran
aim to improve predictor accuracy by using better features and better prediction models [Jiménez
and Teran, 2017, Teran et al., 2016]. For example, the Perceptron Predictor [Teran et al., 2016]
uses simple artificial neurons
5
[Rosenblatt, 1962] to augment the PC with richer features, such
as (1) the history of PCs, (2) bits from the memory address, (3) a compressed representation of
the data, and (4) the number of times a block has been accessed. Each feature is used to index a
distinct table of saturating counters, which are then summed and compared against a threshold
to generate a binary prediction. A small fraction of accesses are sampled to updated the percep-
tron predictor using the perceptron update rule: if the prediction is incorrect, or if the sum fails
to exceed some magnitude, then the counters are decremented on an access and incremented on
an eviction. Figure 4.5 contrasts the perceptron predictor (right) with prior PC-based predictors
(left).
e Multiperspective Reuse Predictor [Jiménez and Teran, 2017] explores an extensive
set of features that captures various properties of the program, producing a predictor that is
informed from multiple perspectives. e features are parameterized with richer information
about the LRU stack position of each training input, the bits of the PC with which each feature
is hashed, and the length of the PC history. Together, these parameters create a large feature
space that leads to higher prediction accuracy.
4.2.5 EVICTED ADDRESS FILTER (EAF)
e EAF policy [Seshadri et al., 2012] predicts the reuse behavior of each missed block individ-
ually, allowing for finer-grained differentiation than PCs. e key observation is that if a block
4
In machine learning, supervised learning is the task of learning a function from a set of labeled input-output pairs.
5
Perceptrons are the building blocks of neural networks.
34 4. FINE-GRAINED REPLACEMENT POLICIES
Table
Feature 1
index
index
index
PC Table 1
Feature 2 PC
Table 2
Feature N PC Table N
PredictionFeature
Prediction
hash
.
.
.
.
.
.
∑
(a) (b)
Figure 4.5: e perceptron predictor considers more features; based on [Teran et al., 2016].
with high reuse is prematurely evicted from the cache, then it will be accessed soon after evic-
tion, while a block with low reuse will not be accessed for a long time after eviction. erefore,
the EAF policy uses a bloom filter [Bloom, 1970] (a probabilistic, space-efficient structure to
determine the presence or absence of an element in a set) to track a small set of recently evicted
addresses. On a cache miss, if the new line is present in the bloom filter—which is also called the
Evicted Address Filter—then the line is predicted to be reuse-friendly and is inserted with high
priority; otherwise, the new line is inserted according to the Bimodal Insertion policy (see Sec-
tion 3.1.2). When the bloom filter is full, it is reset. e EAF is conceptually similar to a small
victim cache that tracks lines that have been recently evicted from the main cache. Table 4.4
summarizes the operations of the EAF policy.
Table 4.4: e evicted address filter policy (EAF)
Insertion Promotion Aging Victim Selection
MRU position (if in EAF),
BIP (otherwise)
MRU position Increment by 1 LRU position
Conceptually, the EAF policy extends the lifetime of cache lines beyond eviction, so that
the lifetime of a line starts with its insertion, but it ends when the line is removed from the
bloom filter. With an extended lifetime, it becomes feasible for EAF to observe reuse for lines
with long reuse intervals, which leads to better scan-resistance and better thrash-resistance, and
thus better performance.
e reuse detector (ReD) [crc, 2017, Albericio et al., 2013] proposes similar ideas as it
bypasses any line that does not hit in the LLC or an Address Reuse Table, which tracks recent
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.