2.2. FINE-GRAINED POLICIES 5
longer reuse distance a second chance to receive cache hits. We say that such policies have an
extended lifetime.
Frequency-Based Policies Frequency-Based Policies maintain frequency counters to order lines
based on the frequency with which they are referenced. Different replacement policies use dif-
ferent strategies to update and interpret these frequency counters. For example, some policies
increase the counters monotonically, while others age the counters (decrease their values) as time
passes by. As another example, some policies evict lines with the lowest frequency, while oth-
ers evict lines whose frequency satisfies some pre-defined criterion. We discuss representative
solutions in Section 3.2.
Hybrid Policies Since different Coarse-Grained policies work well for different cache access
patterns, hybrid policies dynamically choose among a few pre-determined Coarse-Grained poli-
cies to adapt to phase changes in a program’s execution. In particular, hybrid policies observe
the hit rate of a few candidate Coarse-Grained policies during an evaluation period and use this
feedback to choose the best Coarse-Grained policy for future accesses. Adaptive policies are ad-
vantageous because they help overcome pathologies of individual Coarse-Grained policies. In
Chapter 3, we will see that state-of-the-art hybrid policies modulate between Coarse-Grained
policies that use different insertion priorities, and we note that despite the change in insertion
priority over time, such policies are still coarse-grained because within a time period, all lines
are treated identically.
2.2 FINE-GRAINED POLICIES
Fine-Grained policies distinguish among lines when they are inserted into the cache. ey make
these distinctions by using information from a cache line’s previous lifetimes. For example, if a
line has in the past receive no hits, then it can be inserted with low priority. Since remember-
ing the past behavior of all cache lines is infeasible, Fine-Grained policies typically remember
caching behavior for groups of lines. For example, many policies combine into one group of cache
lines that were last accessed by the same load instruction.
Of course, one consideration for all Fine-Grained policies is the metric that is used to
distinguish these groups at the time of insertion. We divide Fine-Grained policies into two
broad categories based on the metric used: (1) Classification-Based Policies associate with each
group one of two possible predictions, namely, cache-friendly and cache-averse; and (2) Reuse
Distance-Based Policies try to predict detailed reuse distance information for each group of cache
lines. ese two categories define extreme ends of a spectrum, where policies on one end of the
spectrum have just two possible predicted values, and policies on the other end of the spectrum
have many possible predicted values; many policies will lie in the middle by predicting one of, say,
four or eight possible values. Finally, Beckmann and Sanchez propose novel metrics [Beckmann
and Sanchez, 2017], which we discuss under a third category.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.