Cache Performance Metrics

Defining the Core Performance Metrics

To quantify cache performance, we need a standard set of metrics. Let's start by formally defining the terms we'll be using throughout this lesson and the rest of the course.

Let's summarize and solidify those key definitions:

• Hit / Miss:

  • A cache hit occurs when the CPU finds the requested data in the cache.
  • A cache miss occurs when the data is not in the cache, forcing an access to a slower level of memory (like RAM).

• Hit Rate / Miss Rate: These are fractions representing the frequency of hits and misses.

  • Hit Rate (H): The fraction of memory accesses that are hits.
    $H=\frac{\text{Number of Hits}}{\text{Total Memory Accesses}}$
  • Miss Rate (M): The fraction of memory accesses that are misses.
    $M=\frac{\text{Number of Misses}}{\text{Total Memory Accesses}}=1-H$

• Hit Time / Miss Penalty: These metrics deal with the time cost of an access.

  • Hit Time ($T_{hit}$): The time required to access data that is present in the cache. This includes the time to determine if it's a hit or miss.
  • Miss Penalty ($T_{penalty}$): The additional time required to service a miss. This is the time to fetch the required block from the next lower level in the memory hierarchy and load it into the cache.

It's important to remember that the Miss Penalty is a significant cost. Accessing main memory can be 100 times slower than accessing the L1 cache.

Calculating Average Memory Access Time (AMAT)

The most important performance metric is the Average Memory Access Time (AMAT). It provides a single number that represents the expected time for any given memory access, accounting for both hits and misses. It's essentially a weighted average.

The formula for a system with a single level of cache is:
$\text{AMAT}=T_{hit}+(M\times T_{penalty})$

Let's break this down:

• You always pay the Hit Time because the CPU first checks the cache.
• You sometimes pay the Miss Penalty, and the probability of this is the Miss Rate.

To see how this works in practice, let's turn to a clear explanation and example.

As the example on the slide shows, even a seemingly low miss rate of 10% can increase the AMAT from 1 cycle to 31 cycles! This demonstrates how crucial high hit rates are for performance.

A Worked Example

Let's solidify this with another example. Consider a system with the following characteristics:

• L1 Cache Hit Time: 2 nanoseconds (ns)
• Main Memory Access Time: 150 ns
• Hit Rate: 96%

1. Calculate the Miss Rate:
   M = 1 - H = 1 - 0.96 = 0.04 \text{ (or 4%)}

2. Determine the Miss Penalty: The penalty for missing in the cache is the time it takes to get the data from main memory.
   $T_{penalty}=150\text{ ns}$

3. Calculate AMAT:
   $\text{AMAT}=T_{hit}+(M\times T_{penalty})$
   $\text{AMAT}=2\text{ ns}+(0.04\times 150\text{ ns})$
   $\text{AMAT}=2\text{ ns}+6\text{ ns}=8\text{ ns}$

Without a cache, every access would take 150 ns. With the cache, the average time is just 8 ns. The cache makes the memory system appear almost 19 times faster on average.

AMAT in Multi-Level Caches

Modern systems don't have just one cache; they have a hierarchy (L1, L2, L3). How do we calculate AMAT then? The logic is recursive.

A miss in the L1 cache triggers an access to the L2 cache. Therefore, the "miss penalty" for L1 is the average memory access time of the L2 cache.

The formula expands like this:
${\text{AMAT}}_{L1}=T_{hit,L1}+(M_{L1}\times {\text{AMAT}}_{L2})$
Where:
${\text{AMAT}}_{L2}=T_{hit,L2}+(M_{L2}\times {\text{AMAT}}_{L3})$
And so on. The final miss penalty is the time to access main memory.

Let's see this in action.

The example on slide 25 is powerful. It shows that adding more cache levels reduces the AMAT from 31 cycles (with only L1) to just 2.115 cycles (with L1, L2, and L3). Each level absorbs some of the misses from the level above it, shielding the CPU from the massive latency of main memory.

Practice Problem

Now it's your turn to apply these formulas. The following image presents a problem with a clear diagram of a multi-level memory hierarchy.

Using the formulas and values provided in the image, calculate the AMAT for each of the three scenarios:

1. With only an L1 cache.
2. With L1 and L2 caches.
3. With L1, L2, and L3 caches.

Take a few minutes to work through the calculations.

Conclusion

In this lesson, we moved from observing cache behavior to measuring it. You now have the tools to analyze the performance of a memory hierarchy and understand the trade-offs involved.

Key Takeaways:

• Hit Rate and Miss Rate are the fundamental probabilities that govern cache performance.
• Miss Penalty represents the steep time cost of fetching data from a slower memory level.
• Average Memory Access Time (AMAT) is the ultimate metric for a memory system's performance, providing a weighted average access time. Its formula is:
  $\text{AMAT}=T_{hit}+(M\times T_{penalty})$
• For multi-level caches, this formula is applied recursively, where the miss penalty of one level is the AMAT of the level below it. Adding more levels of cache can dramatically reduce the AMAT.

Preview of the Next Lesson

We have now explored the structure of caches, the principles of locality, and the metrics for performance. In our next lesson, we will focus on identifying cache-unfriendly memory access patterns in C++ code. We will go beyond the simple matrix traversal example to analyze more subtle patterns that can degrade performance, setting the stage for the optimization techniques we will cover in Module 3.