Consider a system with 2 level cache. Access times of Level 1, Level 2 cache and main memory are 0.5 ns, 5 ns and 100 ns respectively. The hit rates of Level 1 and Level 2 caches are 0.7 and 0.8 respectively. What is the average access time of the system ignoring the search time within cache?

Question

Prepp Team · Accepted Answer

Understanding Cache Memory Access Time

This question asks us to calculate the average memory access time for a system equipped with a two-level cache hierarchy. The system includes a Level 1 (L1) cache, a Level 2 (L2) cache, and main memory. We are given the access time and hit rate for each level of the cache, as well as the access time for the main memory. We need to find the average time it takes to access data, considering the probability of finding the data at each level.

Calculating Average Access Time in a 2-Level Cache System

The average access time in a multi-level cache system depends on the access time and hit rate of each level. Data is first sought in the L1 cache. If it's found (a hit), the access is completed quickly using the L1 access time. If not found in L1 (a miss), the system then looks in the L2 cache. If found in L2 (an L2 hit after an L1 miss), the access takes the L1 miss penalty plus the L2 access time. If not found in L2 either (an L2 miss after an L1 miss), the system must access the main memory, incurring the L1 miss penalty, the L2 miss penalty, and the main memory access time.

The formula for the average memory access time (AAT) in a two-level cache system is:

$$ \text{AAT} = H_1 \times T_1 + (1 - H_1) \times H_2 \times T_2 + (1 - H_1) \times (1 - H_2) \times T_M $$

Where:

$H_1$ is the hit rate of the L1 cache.
$T_1$ is the access time of the L1 cache.
$H_2$ is the hit rate of the L2 cache.
$T_2$ is the access time of the L2 cache.
$T_M$ is the access time of the main memory.

Applying Given Values for Cache Access Time Calculation

From the question, we are given the following values:

Access time of Level 1 cache ($T_1$): 0.5 ns
Access time of Level 2 cache ($T_2$): 5 ns
Access time of Main Memory ($T_M$): 100 ns
Hit rate of Level 1 cache ($H_1$): 0.7
Hit rate of Level 2 cache ($H_2$): 0.8

Step-by-Step Calculation of Average Access Time

Now, we substitute these values into the average access time formula:

$$ \text{AAT} = (0.7 \times 0.5) + ((1 - 0.7) \times 0.8 \times 5) + ((1 - 0.7) \times (1 - 0.8) \times 100) $$

First, calculate the terms within the parentheses:

Term 1 (L1 hit): $0.7 \times 0.5 = 0.35$ ns
Term 2 (L1 miss, L2 hit): $(1 - 0.7) = 0.3$ (L1 miss rate)
$(1 - 0.8) = 0.2$ (L2 miss rate)

Substitute these intermediate results back into the formula:

$$ \text{AAT} = 0.35 + (0.3 \times 0.8 \times 5) + (0.3 \times 0.2 \times 100) $$

Calculate the products in the second and third terms:

Term 2: $0.3 \times 0.8 \times 5 = 0.24 \times 5 = 1.2$ ns
Term 3: $0.3 \times 0.2 \times 100 = 0.06 \times 100 = 6$ ns

Finally, add the three terms together:

$$ \text{AAT} = 0.35 + 1.2 + 6 $$

$$ \text{AAT} = 1.55 + 6 $$

$$ \text{AAT} = 7.55 \text{ ns} $$

Therefore, the average access time of the system is 7.55 ns.

Revision Table: Key Concepts for Cache Memory

Concept	Definition	Impact on Performance
Cache Memory	Small, fast memory storing frequently accessed data from main memory.	Reduces average memory access time by serving data requests faster than main memory.
Hit Rate ($H$)	The fraction of memory accesses found in the cache level.	Higher hit rate means more requests are served quickly by the cache, decreasing average access time.
Miss Rate ($1-H$)	The fraction of memory accesses not found in the cache level.	Higher miss rate means more requests go to the next level or main memory, increasing average access time.
Access Time ($T$)	The time taken to retrieve data from a memory level if it's present.	Lower access time for higher cache levels leads to faster overall access times when hits occur.
Multi-Level Cache	Using more than one level of cache (e.g., L1, L2, L3), typically with increasing size and latency.	Provides a hierarchy to balance speed (small, fast L1) and capacity (larger, slower L2/L3).

Additional Information: Understanding Cache Hierarchy

Modern computer systems use a cache hierarchy to bridge the performance gap between the fast CPU and the slower main memory. A typical hierarchy might include:

L1 Cache: Smallest, fastest cache, usually on the CPU chip, often split into instruction and data caches. Access time is very low (a few clock cycles).
L2 Cache: Larger and slightly slower than L1, often shared between CPU cores or dedicated per core. Access time is moderate.
L3 Cache: Largest and slowest cache level, often shared by all CPU cores on a chip. Access time is higher than L2 but still much lower than main memory.

When the CPU needs data, it checks L1 first. If it's a miss, it checks L2. If it's still a miss, it checks L3 (if present). Only if the data is not found in any cache level is the request sent to main memory. The average access time calculation reflects this tiered approach, weighting the access time of each level by the probability of finding the data at that level. The probabilities are determined by the hit rates at each level.

The formula used in the solution assumes that the access time to the next level of memory starts only after it is determined that the data is not in the current level. This is a common model for calculating average access time.