Calculating Average Memory Access Time

Welcome back! In our previous lesson, we confronted the internal challenges to processor speed by dissecting pipeline hazards and the clever techniques used to mitigate them. We saw how forwarding and branch prediction help keep the instruction pipeline flowing smoothly. However, even the most efficient pipeline is useless if it's constantly starved for data. A high-performance processor waiting for slow main memory is like a Formula 1 car stuck in city traffic.

This lesson tackles that exact problem. We will explore the memory hierarchy, the system designed to bridge the massive speed gap between the CPU and main memory. Our specific learning outcome is to calculate the average memory access time (AMAT) in a system with a memory hierarchy, considering cache hit/miss rates. Mastering this calculation is non-negotiable for GATE, as it forms the basis of many numerical questions on system performance.

We will start by defining the core concepts of cache hits and misses, then derive the fundamental formula for AMAT, and finally extend it to the multi-level cache systems found in all modern processors.

The Processor-Memory Performance Gap and Locality

Over the last few decades, processor speeds have increased at a much faster rate than the speed of main memory (DRAM). This growing disparity is known as the processor-memory performance gap. To solve this, computer architects introduced a small, extremely fast memory called a cache, placed right next to the processor.

The reason this works is due to a fundamental property of programs known as the principle of locality.

Temporal Locality: If a program accesses a memory location, it is very likely to access that same location again soon. (e.g., variables in a loop).
Spatial Locality: If a program accesses a memory location, it is very likely to access nearby memory locations soon. (e.g., accessing elements of an array sequentially).

The cache exploits this by storing recently accessed data and its neighbors, betting that the CPU will need them again. When the CPU requests data, it checks the cache first.

Cache Hit: The requested data is found in the cache. This is a fast access.
Cache Miss: The requested data is not in the cache. The data must be fetched from the slower main memory and is usually copied into the cache for future use (exploiting temporal locality). This is a slow access.

Our goal is to quantify the performance of this system. We need a metric that averages out the fast hits and the slow misses. This metric is the Average Memory Access Time (AMAT).

Calculating AMAT for a Single-Level Cache

To calculate AMAT, we need three key parameters:

Hit Time ( $T_{hi t}$ ): The time taken to access data that is present in the cache.
Miss Penalty ( $M_{p}$ ): The additional time required to handle a cache miss. This typically involves fetching the data from the next level of memory (e.g., main memory).
Hit Rate ( $h$ ): The fraction of memory accesses that are hits. The Miss Rate ( $m$ ) is simply $1 - h$ .

The AMAT can be thought of as the weighted average of the time for a hit and the time for a miss. A common way to express the formula is:

AMAT = (Hit Rate \times Hit Time) + (Miss Rate \times Miss Time)

Here, "Miss Time" is the total time on a miss. Be careful with question wording in GATE. Sometimes, you are given the "Miss Penalty" and sometimes the "Main Memory Access Time".
Let's define a very clear and reliable formula:

Every access must first check the cache, which takes $T_{hi t}$ time. If it's a miss (which happens with probability $m$ ), we incur an additional miss penalty.

AMAT = T_{hi t} + (m \times M_{p})

Let's work through a GATE-level problem to see this in action.

GATE 2015- Average Access Time - Cache Hit Miss - Computer Architecture

This video from Ritu Kapur Classes solves a question from GATE 2015 that directly applies this formula. The presenter uses a slightly different but equivalent formulation of the AMAT equation.

First, watch the problem statement from the beginning. Note down the given values: Time for a cache miss = 50 ns Time for a cache hit = 5 ns Hit ratio = 80% = 0.8 Now, watch the solution from the formula application. The formula used is: Average access time = (hit_ratio * time_hit) + (miss_ratio * time_miss) Using the given values: AMAT = (0.8 * 5 ns) + (0.2 * 50 ns) AMAT = 4 ns + 10 ns = 14 ns This approach is perfectly valid because the problem gives the total time for a miss (50 ns), not the miss penalty. If it had given a miss penalty of 45 ns, the calculation using our formula would be: AMAT = 5 ns + (0.2 * 45 ns) = 5 ns + 9 ns = 14 ns. The result is the same, so it's vital to understand what the terms in the question mean. Extending AMAT to Multi-Level Caches To further bridge the processor-memory gap, modern systems use a hierarchy of caches. A typical setup is: L1 Cache: Smallest and fastest, closest to the CPU. L2 Cache: Larger and slower than L1, but still much faster than main memory. L3 Cache: Even larger and slower, shared among multiple CPU cores. When the CPU requests data, it first checks L1. If it's an L1 miss, it checks L2. If it's an L2 miss, it checks L3 (if present), and finally goes to main memory. This is called hierarchical access. To calculate AMAT for a multi-level system, we can extend our formula. The "miss penalty" for one level becomes the average time to access the next level. Let's consider a system with L1 and L2 caches, and Main Memory. T_{L1}: Hit time of L1 cache. m_{L1}: Miss rate of L1 cache. The miss penalty for L1 (M_{p, L1}) is the time it takes to get the data from the L2/Memory system. This is the AMAT of the L2 cache. So, the top-level formula is: \text{AMAT} = T_{L1} + (m_{L1} \times \text{AMAT}_{L2}) Now, we need to find \text{AMAT}_{L2}. The same logic applies: \text{AMAT}_{L2} = T_{L2} + (m_{L2} \times M_{p, L2}) Where T_{L2} is the L2 hit time, m_{L2} is the local miss rate of L2 (i.e., the percentage of accesses that reach L2 and miss), and M_{p, L2} is the L2 miss penalty, which is the time to access Main Memory (T_{Mem}). Substituting back, we get the full formula for a two-level cache system: \text{AMAT} = T_{L1} + m_{L1} \times (T_{L2} + m_{L2} \times T_{Mem}) This nested structure is the key. Each level of the hierarchy adds a term to the AMAT calculation, weighted by the miss rates of all the levels above it. Example: Two-Level Cache Calculation Let's imagine a processor with the following characteristics: L1 cache hit time (T_{L1}): 1 ns L1 miss rate (m_{L1}): 10% or 0.1 L2 cache hit time (T_{L2}): 10 ns L2 local miss rate (m_{L2}): 20% or 0.2 Main memory access time (T_{Mem}): 100 ns (This is the final miss penalty for L2) Let's apply the formula: \text{AMAT} = T_{L1} + m_{L1} \times (T_{L2} + m_{L2} \times T_{Mem}) \text{AMAT} = 1 + 0.1 \times (10 + 0.2 \times 100) \text{AMAT} = 1 + 0.1 \times (10 + 20) \text{AMAT} = 1 + 0.1 \times (30) \text{AMAT} = 1 + 3 = 4 \text{ ns} Notice how the effective performance is much closer to the L1 hit time than the main memory time. This demonstrates the power of the memory hierarchy. Without any cache, the access time would always be 100 ns. With just an L1 cache, the AMAT would be 1 + 0.1 \times 100 = 11 ns. The addition of the L2 cache brings it down to 4 ns.

This approach is perfectly valid because the problem gives the total time for a miss (50 ns), not the miss penalty. If it had given a miss penalty of 45 ns, the calculation using our formula would be: AMAT = 5 ns + (0.2 * 45 ns) = 5 ns + 9 ns = 14 ns. The result is the same, so it's vital to understand what the terms in the question mean.

Extending AMAT to Multi-Level Caches

To further bridge the processor-memory gap, modern systems use a hierarchy of caches. A typical setup is:

L1 Cache: Smallest and fastest, closest to the CPU.
L2 Cache: Larger and slower than L1, but still much faster than main memory.
L3 Cache: Even larger and slower, shared among multiple CPU cores.

When the CPU requests data, it first checks L1. If it's an L1 miss, it checks L2. If it's an L2 miss, it checks L3 (if present), and finally goes to main memory. This is called hierarchical access.

To calculate AMAT for a multi-level system, we can extend our formula. The "miss penalty" for one level becomes the average time to access the next level.

Let's consider a system with L1 and L2 caches, and Main Memory.

$T_{L 1}$ : Hit time of L1 cache.
$m_{L 1}$ : Miss rate of L1 cache.

The miss penalty for L1 ( $M_{p, L 1}$ ) is the time it takes to get the data from the L2/Memory system. This is the AMAT of the L2 cache.

So, the top-level formula is:

AMAT = T_{L 1} + (m_{L 1} \times AMAT_{L 2})

Now, we need to find $AMAT_{L 2}$ . The same logic applies:

AMAT_{L 2} = T_{L 2} + (m_{L 2} \times M_{p, L 2})

Where $T_{L 2}$ is the L2 hit time, $m_{L 2}$ is the local miss rate of L2 (i.e., the percentage of accesses that reach L2 and miss), and $M_{p, L 2}$ is the L2 miss penalty, which is the time to access Main Memory ( $T_{M e m}$ ).

Substituting back, we get the full formula for a two-level cache system:

AMAT = T_{L 1} + m_{L 1} \times (T_{L 2} + m_{L 2} \times T_{M e m})

This nested structure is the key. Each level of the hierarchy adds a term to the AMAT calculation, weighted by the miss rates of all the levels above it.

Example: Two-Level Cache Calculation

Let's imagine a processor with the following characteristics:

L1 cache hit time ( $T_{L 1}$ ): 1 ns
L1 miss rate ( $m_{L 1}$ ): 10% or 0.1
L2 cache hit time ( $T_{L 2}$ ): 10 ns
L2 local miss rate ( $m_{L 2}$ ): 20% or 0.2
Main memory access time ( $T_{M e m}$ ): 100 ns (This is the final miss penalty for L2)

Let's apply the formula:

AMAT = T_{L 1} + m_{L 1} \times (T_{L 2} + m_{L 2} \times T_{M e m})

AMAT = 1 + 0.1 \times (10 + 0.2 \times 100)

AMAT = 1 + 0.1 \times (10 + 20)

AMAT = 1 + 0.1 \times (30)

AMAT = 1 + 3 = 4 ns

Notice how the effective performance is much closer to the L1 hit time than the main memory time. This demonstrates the power of the memory hierarchy. Without any cache, the access time would always be 100 ns. With just an L1 cache, the AMAT would be $1 + 0.1 \times 100 = 11$ ns. The addition of the L2 cache brings it down to 4 ns.

Avg Memory Access Time with Multi level cache

For a detailed walkthrough of another multi-level cache problem, this video from GATEBOOK VIDEO LECTURES is a great resource. It will reinforce the formula and its application.

The video breaks down the calculation for a system with multiple cache levels. Watch it to see the formula applied to a concrete example with different hit rates and access times. This will help solidify your understanding of how to layer the miss penalties correctly.

A Note on Access Policies

The formulas we've discussed assume a hierarchical (or sequential) access policy: we only access L2 after we know we've missed in L1. This is the most common model and the one you should assume for GATE unless a problem explicitly states otherwise.

Another theoretical policy is simultaneous access, where the CPU might search L1 and L2 at the same time. If the data is found in L1, the L2 search is aborted. The AMAT formula for this is different, but it's rarely tested. For your GATE preparation, focusing on mastering the hierarchical model is the priority.

Conclusion

Today, we've quantified the performance of the crucial bridge between the processor and main memory. By understanding the memory hierarchy and how to calculate its effective performance, you've gained a vital tool for analyzing computer systems.

Key Takeaways:

The memory hierarchy uses multiple levels of memory with different speeds and sizes to mitigate the processor-memory performance gap, exploiting the principle of locality.
Average Memory Access Time (AMAT) is the key performance metric for the memory system.
For a single-level cache, the formula is: $AMAT = T_{hi t} + (m \times M_{p})$ .
For a multi-level cache system (hierarchical access), the formula is nested: $AMAT = T_{L 1} + m_{L 1} \times (T_{L 2} + m_{L 2} \times (\dots T_{M e m}))$ .
Carefully read GATE questions to distinguish between miss penalty (additional time) and miss time (total time for that level, e.g., main memory access time).

We've learned how to measure the performance of a cache system based on its hit rate. But what determines that hit rate? The answer lies in how the cache is organized. In our next lesson, we will dive into the internal architecture of caches, exploring cache mapping techniques (direct, set-associative, fully-associative) and replacement policies (LRU, FIFO). These design choices directly influence the hit and miss rates that we used in our formulas today.