5.4. PREFETCH-AWARE CACHE REPLACEMENT 49
forms a significant portion of the cache, so, interaction with the prefetcher is an important
consideration for cache replacement policies.
ere are two primary goals in designing a prefetch-aware cache replacement policy. First,
the replacement policy should avoid cache pollution caused by inaccurate prefetches. Second, the
replacement policy should preferentially discard lines that can be prefetched over those that are
difficult to prefetch [Jain and Lin, 2018, Srinath et al., 2007, Wu et al., 2011b].
In this section, we first summarize the vast majority of work in cache replacement which
focuses on the first design goal of eliminating useless prefetches. We then show that Belady’s
MIN algorithm, which is provably optimal in the absence of prefetches, is incomplete in the
presence of a prefetcher because it ignores the second design goal of deprioritizing prefetchable
lines. Finally, we summarize recent work that addresses these limitations of MIN by simultane-
ously considering both of the above design goals.
5.4.1 CACHE POLLUTION
Most prefetch-aware cache replacement policies focus on reducing cache pollution by identifying
and evicting inaccurate prefetches. Such solutions can be divided into two broad categories.
e first category takes feedback from the prefetcher to identify potentially inaccurate
prefetch requests; such policies typically require explicitly co-designed prefetchers or modifica-
tions to existing prefetchers. For example, Ishii et al. use the internal state of the AMPM [Ishii
et al., 2011] prefetcher to inform the insertion priority of prefetched blocks [Ishii et al., 2012].
As another example, Kill-the-PC (KPC) [Kim et al., 2017] is a cooperative prefetching and
caching scheme that co-designs the prefetcher to provide feedback on confidence and estimated
time to reuse. is information is then used to determine whether the prefetch is inserted into
the L2 or the L3, and this information is used to determine the inserted line’s RRPV insertion
position.
e second category works independently of the prefetcher and monitors cache behavior
to adapt replacement decisions; such policies can work with any prefetcher but may lack pre-
cise prefetcher-specific information. For example, Feedback Directed Prefetching (FDP) [Sri-
nath et al., 2007] and Informed Caching policies for Prefetched blocks (ICP) [Seshadri et al.,
2015] introduce methods to dynamically estimate prefetch accuracy, and they insert inaccu-
rate prefetches at positions with low priority. In particular, FDP estimates accuracy at a coarse
granularity by counting the ratio of useful prefetches and total prefetches within a time epoch.
ICP augments FDP by accounting for recently evicted prefetched blocks that would have been
deemed accurate if they had been cached for some additional amount of time. Prefetch-Aware
Cache Management (PACMan) [Wu et al., 2011b] instead identifies for each time epoch the
best insertion and promotion policies for prefetch requests. As shown in Figure 5.6, PACMan
defines three variants of RRIP (PACMan-M, PACMan-H, and PACMan-HM), and it uses
set dueling to find the best insertion policy for a given epoch.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.