Review of Memory Hierarchy - Computer Architecture: A Quantitative Approach - page 570

Hence, we organize six cache optimizations into three categories:
■ Reducing the miss rate —larger block size, larger cache size, and higher associativity
■ Reducing the miss penalty —multilevel caches and giving reads priority over writes
■ Reducing the time to hit in the cache —avoiding address translation when indexing the cache
Figure B.18 on page B-40 concludes this section with a summary of the implementation com-
plexity and the performance benefits of these six techniques.
The classical approach to improving cache behavior is to reduce miss rates, and we present
three techniques to do so. To gain beter insights into the causes of misses, we irst start with a
model that sorts all misses into three simple categories:
■ Compulsory —The very first access to a block cannot be in the cache, so the block must be
brought into the cache. These are also called cold-start misses or first-reference misses .
■ Capacity —If the cache cannot contain all the blocks needed during execution of a program,
capacity misses (in addition to compulsory misses) will occur because of blocks being dis-
carded and later retrieved.
■ Conflict —If the block placement strategy is set associative or direct mapped, conflict misses
(in addition to compulsory and capacity misses) will occur because a block may be dis-
carded and later retrieved if too many blocks map to its set. These misses are also called
collision misses . The idea is that hits in a fully associative cache that become misses in an n
-way set-associative cache are due to more than n requests on some popular sets.
( Chapter 5 adds a fourth C, for coherency misses due to cache flushes to keep multiple caches
coherent in a multiprocessor; we won't consider those here.)
Figure B.8 shows the relative frequency of cache misses, broken down by the three C's.
Compulsory misses are those that occur in an infinite cache. Capacity misses are those that
occur in a fully associative cache. Conflict misses are those that occur going from fully asso-
ciative to eight-way associative, four-way associative, and so on. Figure B.9 presents the same
data graphically. The top graph shows absolute miss rates; the botom graph plots the percent-
age of all the misses by type of miss as a function of cache size.