1
C H A P T E R 1
Introduction
For decades now, the latency of moving data has greatly exceeded the latency of executing an
instruction, so caches, which both reduce memory latency and reduce memory traffic, are im-
portant components of all modern microprocessors. Because there is a general tradeoff between
the size of a cache and its latency, most microprocessors maintain a hierarchy of caches, with
smaller lower-latency caches being fed by larger higher-latency caches, which is eventually fed
by DRAM. For each of these caches, effectiveness can be measured by its hit rate, which we
define to be
s
r
, where s is the number of memory requests serviced by the cache and r is the total
number of memory requests made to the cache.
ere are several methods of improving a cache’s hit rate. One method is to increase the
size of the cache, typically at the expense of increased latency. A second method is to increase
the associativity of the cache, which increases the number of possible cache locations to which
a cache line can be mapped. At one extreme, a direct mapped cache (associativity of 1) maps
each cache line to a single location in the cache. At the other extreme, a fully associative cache
allows a cache line to be placed anywhere in the cache. Unfortunately, power consumption and
hardware complexity both increase as we increase associativity. e third method, which is the
subject of this book, is to choose a good cache replacement policy, which answers the question,
“When a new line is to be inserted into the cache, which line should be evicted to make space
for the new line?”
It may seem strange to write a book on cache replacement, since Lazslo Belady produced a
provably optimal policy over five decades ago. But Belady’s policy is unrealizable because it relies
on future knowledge—it evicts the line that will be re-used furthest in the future. us, over the
years, researchers have explored several different approaches to solving the cache replacement
problem, typically relying on heuristics that consider frequency of access, recency of access, and
more recently, prediction techniques.
Moreover, there is the question of how cache replacement policies relate to dead block
predictors, which attempt to predict lines that will no longer be needed in the cache. We now
know that the life cycle of a cache line has multiple decision points, beginning with the insertion
of the line and progressing over time to the eventual eviction of the line, and we know that there
are different techniques for performing actions at these different decision points. With this view,
we argue that dead block predictors are a special case of cache replacement policies, and we find
that the space of cache replacement policies is quite rich.
2 1. INTRODUCTION
Finally, caches are ubiquitous in software systems as well. In fact, the first replacement
policies were developed for the paging systems of operating systems, and while there are tech-
nological differences between software caches and hardware caches, we hope that some of the
ideas in this book will prove useful for the developers of software caches, as well.
Scope is book focuses on hardware cache replacement policies for CPU data caches. And
while most of the research that we discuss is performed in the context of last-level caches, where
the benefits of intelligent cache replacement are most pronounced, the general ideas often apply
to other levels of the cache hierarchy.
Roadmap We start in Chapter 2 by defining a 2-dimensional taxonomy. e primary dimen-
sion describes the granularity of replacement decisions. A second dimension describes the metric
that is used to make the replacement decisions. Chapters 3 and 4 then use our taxonomy to de-
scribe existing replacement policies. Chapter 5 introduces other considerations that complicate
cache replacement, including data prefetchers, shared caches, variable miss costs, compression,
and new technologies. We conclude in Chapter 6 by using the results of the Cache Replacement
Championship held in 2017 to encapsulate recent trends in cache replacement, before stepping
back and taking stock of larger trends and challenges for future research.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.