Cache Performance and AMAT Calculations

1. Revisiting Average Memory Access Time (AMAT)

The entire purpose of a cache is to reduce the time it takes to access data from memory. We measure its effectiveness using a metric called Average Memory Access Time (AMAT).

The key variables involved are:

• Hit Time (T_hit): The time required to access data that is found in the cache (a cache hit).
• Miss Rate (R_miss): The fraction of memory accesses that are not found in the cache (a cache miss). The hit rate is simply 1 - R_miss.
• Miss Penalty (P_miss): The extra time required to handle a cache miss. This usually involves fetching the data from the next level of the memory hierarchy (e.g., a lower-level cache or main memory).

The following video provides a concise review of these concepts and derives the fundamental formula for AMAT.

As the video explains, the formula for AMAT in a system with a single-level cache is:

This formula is intuitive: every memory access pays the hit time (since we always check the cache first). On top of that, we pay an additional miss penalty, but only for the fraction of accesses that result in a miss.

Let's put this to use with a quick example.

Example Problem:
A processor has a cache with a hit time of 2 ns. A main memory access takes 50 ns. If the miss rate of the cache is 4% (0.04), what is the AMAT?

Solution:

1. Hit Time = 2 ns
2. Miss Rate = 0.04
3. Miss Penalty: This is the extra time for a miss. It's the time to access main memory after failing to find the data in the cache. So, Miss Penalty = 50 ns.
   (Note: Sometimes the problem states the total miss latency, e.g., "a miss takes 52 ns". In that case, the total miss latency is Hit Time + Miss Penalty. Be sure to read the problem carefully to distinguish between the two).
4. Calculate AMAT: $$\text{AMAT}=2\text{ ns}+(0.04\times 50\text{ ns})=2\text{ ns}+2\text{ ns}=4\text{ ns}$$

2. Cache Performance and Overall CPU Execution Time

AMAT tells us about the memory system's performance, but how does that translate to the overall execution time of a program? To answer this, we need to connect AMAT to the CPU performance equation.

Recall from our earlier lessons that CPU execution time can be defined as:

Where CPI is the average number of clock cycles per instruction. Cache misses directly impact CPI by causing the processor to stall while waiting for data. We can separate the base CPI from the stalls caused by memory access:

The number of memory stall cycles can be calculated as:

The following reading material provides a more formal presentation of these formulas and walks through detailed examples. It also introduces an important related metric, Misses Per Kilo-Instruction (MPKI).

As you saw in the reading, a lower miss rate doesn't always mean better performance. The number of memory accesses per instruction is crucial. A program with a low miss rate but many memory accesses could perform worse than a program with a higher miss rate but fewer memory accesses.

3. Analyzing Multi-Level Caches

Modern processors don't have just one cache; they have a hierarchy (L1, L2, L3). The AMAT calculation extends naturally to this hierarchy.

When a miss occurs in the L1 cache, we don't go directly to main memory. We first check the L2 cache. The "miss penalty" for the L1 cache is therefore the time it takes to access the L2 cache. The AMAT of the L2 cache then becomes the miss penalty for the L1 cache.

This creates a recursive relationship. For a two-level cache system:

And the L1 miss penalty is simply the AMAT of the L2 cache:

where Miss Penalty_L2 is the time to access main memory.

Combining these gives the full formula:

It's important to distinguish between local miss rate (the miss rate for a specific cache level) and global miss rate (the number of misses in a cache level divided by the total number of CPU memory accesses). The formulas above use local miss rates.

The image below summarizes the AMAT formulas for systems with one, two, and three levels of cache.

Now, let's see a complete numerical example for a multi-level cache system.

4. Practice Problem Set

Now it's time to apply what you've learned. The following problems are taken from a set of exercises designed to test these concepts. Try to solve each one on your own before looking at the solution steps. All necessary formulas are in the text above.

Problem 1: Single-Level Cache Performance

A program executes 500 million instructions on a processor with a base CPI of 1.8. The cache has a hit time of 3 cycles and a miss penalty of 80 cycles. The miss rate is 6%, and memory accesses per instruction is 35%. Calculate:
a) The total memory stall cycles.
b) The total CPI including memory stalls.
c) The total CPU execution time, assuming a clock cycle time of 2 ns.

Problem 2: Multi-Level Cache Performance

A processor has an L1 cache with a hit time of 2 cycles and a local miss rate of 5%. The L2 cache has a hit time of 10 cycles and a local miss rate of 20% (this is the rate of misses in L2 for accesses that come from L1). The miss penalty from the L2 cache to main memory is 100 cycles.
a) What is the average memory access time (AMAT) in cycles?
b) If 40% of instructions are memory accesses, what is the number of memory stall cycles per instruction?

These problems are representative of what you might encounter in an exam. If you'd like more practice, the resource LINK in the resource list contains an extensive list of exercises (problems #16-45) with solutions.

Conclusion

In this lesson, we transitioned into our exam preparation by focusing on the quantitative analysis of cache performance. You've reinforced your understanding of the key metrics and practiced applying them to solve numerical problems for both single and multi-level cache systems.

Key Takeaways:

• Average Memory Access Time (AMAT) is the fundamental metric for cache performance, calculated as:
  AMAT = Hit Time + (Miss Rate × Miss Penalty).
• For multi-level caches, the AMAT formula is applied recursively, where the miss penalty of a higher-level cache is the AMAT of the next-lower-level cache.
• Cache performance directly impacts total CPU execution time by introducing memory stall cycles, which increase the effective Cycles Per Instruction (CPI).
• Solving these problems requires careful reading to correctly identify each variable (hit times, miss rates, penalties in cycles vs. seconds) and apply the correct formula for the given scenario.

In our next lesson, we will continue our focus on performance analysis by tackling another crucial topic: calculating the theoretical speedup of parallel algorithms using Amdahl's Law and Gustafson's Law.