4.3. OTHER PREDICTION METRICS 35
cache misses. As a result, ReD only inserts lines in the cache on their second reuse. To avoid
bypassing all lines when they are first seen, ReD also uses a PC-based predictor to predict lines
that are likely to be reused after their first access.
4.3 OTHER PREDICTION METRICS
Not all Fine-Grained policies predict reuse distances or binary labels, and it is certainly pos-
sible to capture past behavior using different prediction targets. For example, one component
of Kharbutli and Solihin [2005] dead block predictor predicts the maximum number of times
that a line is expected to be reused in the cache. As an example of this class of solutions, we
now discuss in detail the EVA policy [Beckmann and Sanchez, 2017], which introduces a novel
prediction target, called the EVA, and which is one of the few Fine-Grained solutions to use
historical information to guide the aging process.
4.3.1 ECONOMIC VALUE ADDED (EVA)
Beckmann and Sanchez argue that it is optimal to replace the candidate with the longest ex-
pected time to reuse only when we possess perfect knowledge of the future [Belady, 1966], but
this strategy is inadequate for practical solutions which face inherent uncertainty about the fu-
ture [Beckmann and Sanchez, 2017]. us, practical solutions need to balance two competing
objectives: (1) maximize the probability that a given line will hit in the cache, and (2) limit
the duration for which the line consumes cache space. Solutions that are based solely on reuse
distance account for only one side of the tradeoff.
To address this limitation, Beckmann and Sanchez [2017] propose a new metric called
the economic value added (EVA), which combines these two factors into a single metric. EVA is
defined to be the number of hits the candidate is likely to yield compared to its average occupancy
in the cache. Equation (4.1) shows EVA is computed for a given line. We see that there are two
components to a line’s EVA. First, the line is rewarded for its expected number of future hits
(a line that has a higher reuse probability will have a higher EVA value). Second, the line is
penalized for the cache space that it will consume. is penalty is computed by charging each
candidate for the time it will spend in the cache at the rate of a single line’s average hit rate (the
cache’s hit rate divided by its size), which is the long-term opportunity cost of consuming cache
space. us, the EVA metric captures the cost-benefit tradeoff of caching a line by computing
whether its odds of hitting are worth the cache space that it will consume.
EVA D Expected_hits .Cache_hit_rate=Cache_size/ Expected_time: (4.1)
e EVA of candidates is inferred from their ages, and it is revised as the candidates age.
For example, the left side of Figure 4.6 shows how the EVA changes with respect to a candidate’s
age for an application that iterates over a small and a big array (the reuse distance distribution
for the same application is shown on the right side). At first, the EVA is high because there is
36 4. FINE-GRAINED REPLACEMENT POLICIES
1.0
0.5
0.0
-0.5
-1.0
0.5
0.4
0.3
0.2
0.1
0.0
0 50 100 150 200 250 0 50 100 150 200 250
EVA ⇒
Access Probability
Age Reuse Distance
Cache small array
Cache big array eventually
Small array Big array
Evict after small array
Cache small array
Cache big array eventually
Evict after small array
Small array
Big array
Figure 4.6: EVA learns about the candidates as they age; based on [Beckmann and Sanchez,
2017].
1.0
0.5
0.0
-0.5
-1.0
-1.5
0 50 100 150 200 250
EVA ⇒
Age
Cache small array
Small array
Big array
Cache big array
eventually
Evict
immediately
Figure 4.7: EVA with classification; based on [Beckmann and Sanchez, 2017].
a good chance that the access is from a small array, which means that the replacement policy
can afford to gamble that candidates will hit quickly. But the EVA drops sharply when the age
exceeds the length of the short array because the penalty of caching lines from the big array is
much higher. At this point, the low EVA makes it very likely that lines from the big array are
evicted. e penalty of caching lines from the big array decreases as the lines age and approach
the reuse distance of the big array. is penalty is reflected in the gradual increase in the EVA
from age 50 to age 250, at which point the EVA replacement policy protects lines from the big
array even though they are old. us, in the face of uncertainty, the EVA replacement policy
learns more about candidates as they age.
Of course, another way to reduce uncertainty is to classify lines into different categories.
For example, Figure 4.7 shows the EVA with respect to age if we were to classify the small array
and big array into distinct classes, and we see that the per-class EVA curves are much simpler.
eoretically, EVA can be extended to support classification, but the implementation complexity
limits this extension to a few classes. In the next section, we will discuss replacement policies
4.3. OTHER PREDICTION METRICS 37
that rely on many fine-grained classes but learn much simpler metrics for each class. By contrast,
EVA ranks ages at a fine granularity, but this restricts EVA to use fewer classes.
e EVA replacement policy computes the EVA curves by recording the age distribution
of hits and evictions and by processing information about these evictions using a lightweight
software runtime. To predict the EVA of a line, its age is used to index into an eviction priority
array, which conceptually represents the EVA curves.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.