3
C H A P T E R 2
A Taxonomy of Cache
Replacement Policies
To organize both this book and the many ideas that have been studied over several decades, we
present a taxonomy of solutions to the cache replacement problem. Our taxonomy is built on
the observation that cache replacement policies solve a prediction problem, where the goal is to
predict whether any given line should be allowed to stay in cache. is decision is re-evaluated
at multiple points in a cache line’s lifetime, which begins when the line is inserted into the cache
and ends when the line is evicted from the cache.
erefore, in our taxonomy, we first divide cache replacement policies into two broad
categories based on the granularity of their insertion decisions. Polices in the first category,
which we refer to as Coarse-Grained policies, treat all lines identically when they are inserted into
the cache and only differentiate among lines based on their their behavior while they reside in
the cache. For example, as a line resides in the cache, its priority might be increased each time it
is reused. By contrast, Fine-Grained policies distinguish among lines when they are inserted into
the cache (in addition to observing their behavior while they reside in the cache). To make this
distinction at the time of insertion, Fine-Grained policies typically rely on historical information
about cache access behavior. For example, if a Fine-Grained policy has learned that a particular
instruction loads lines that in the past tend to be evicted without being reused, it can insert that
line with a low priority.
To better understand our taxonomy, it is useful to understand that replacement policies
are typically implemented by associating a small amount of replacement state with each cache line
(Figure 2.1):
Insertion
Policy
Eviction
Policy
Promotion
Policy
Aging Aging
History
Time
Figure 2.1: Operations of a replacement policy during a cache line’s lifetime.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.