Measuring and Improving Cache Performance

Quantifying Cache Performance

To reason about cache performance precisely rather than intuitively, two measurements are essential: the Miss Rate, the fraction of memory accesses that result in a cache miss, and the Miss Penalty, the extra time required to fetch data from a slower level of the memory hierarchy when a miss occurs.

These combine into a single overall metric:

Average Memory Access Time =
Hit Time + (Miss Rate × Miss Penalty)

This formula shows that improving cache performance means reducing one or more of three factors: the time to access the cache itself, how often misses occur, and how costly each miss is when it happens.

The Three Cs: Classifying Why Misses Happen

Cache misses are commonly grouped into three categories, often called the Three Cs.

• Compulsory Misses occur the very first time a block of memory is accessed, since it cannot possibly already be in the cache. These are sometimes called cold-start misses and are largely unavoidable.
• Capacity Misses occur when the cache is simply too small to hold all the data a program needs at once, forcing previously cached blocks to be evicted even though they might be needed again soon.
• Conflict Misses occur specifically in direct-mapped or limited-associativity caches, discussed earlier in this series, when two frequently used memory blocks happen to map to the same cache location, repeatedly evicting each other even though the cache overall has unused space elsewhere.

Strategy: Increasing Associativity

One way to reduce conflict misses is to allow each memory address to map to more than one possible cache location instead of exactly one, an approach called Set-Associative Caching. This reduces the chance that two frequently accessed blocks will collide and repeatedly evict each other, at the cost of needing extra comparison hardware to check multiple possible locations on every access.

Strategy: Increasing Block Size

As discussed earlier regarding spatial locality, increasing the block size can reduce compulsory misses by fetching more useful neighboring data on each miss. However, pushed too far, larger blocks increase the miss penalty, since more data must be transferred on every miss, and can waste cache capacity if the extra data ends up unused.

Strategy: Adding More Cache Levels

Rather than relying on a single cache, most modern processors use a Multi-Level Cache hierarchy, with a very small, extremely fast first-level cache backed by a larger, somewhat slower second-level cache, which is in turn backed by main memory. A miss in the first level often still hits in the second level, substantially reducing the effective average miss penalty compared to going all the way to main memory.

Why These Tradeoffs Require Careful Balancing

Every one of these strategies improves one aspect of cache performance while potentially worsening another — larger caches reduce capacity misses but increase hit time and cost, higher associativity reduces conflict misses but adds hardware complexity, and larger blocks reduce compulsory misses but increase miss penalty. Real processor designs are the result of carefully balancing these competing factors based on the specific workloads they are expected to run.