GATE2025_CS1_Q53

A computer has a memory hierarchy consisting of two-level cache (L1 and L2) and a main memory. If the processor needs to access data from memory, it first looks into L1 cache. If the data is not found in L1 cache, it goes to L2 cache. If it fails to get the data from L2 cache, it goes to main memory, where the data is definitely available. Hit rates and access times of various memory units are shown in the figure. The average memory access time in nanoseconds (ns) is _______. (rounded off to two decimal places)

✅ Final Answer:

The correct answer is 11.85.

🔹 Short Answer:

The Average Memory Access Time (AMAT) is calculated by summing the time taken for each possible scenario, weighted by its probability. The access times given are total times for each scenario (L1 hit, L2 hit, MM hit).
AMAT = P(L1 Hit) × T(L1 Hit) + P(L1 Miss, L2 Hit) × T(L2 Hit) + P(L1 Miss, L2 Miss) × T(MM Hit)
AMAT = (0.95 × 10) + (0.05 × 0.85 × 20) + (0.05 × 0.15 × 200) = 9.5 + 0.85 + 1.5 = 11.85 ns.

🔸 Long Answer:

To calculate the Average Memory Access Time (AMAT) for a hierarchical memory system, we need to consider all possible outcomes of a memory access request and their associated probabilities and time costs.

Step 1: Understand the Data and Scenarios

The wording in the diagram is key. "Access time (including L1 cache miss penalty) = 20 ns" implies that 20 ns is the total time from the processor's request to data retrieval if the data is found in L2. Similarly, 200 ns is the total time if the data is only found in Main Memory. This is a common way to phrase problems for a global hit rate model.

We have three mutually exclusive scenarios:

1. Hit in L1 Cache: The data is found in L1.
2. Miss in L1, Hit in L2: The data is not in L1 but is found in L2.
3. Miss in L1, Miss in L2: The data is found only in Main Memory.

Step 2: Calculate Probability and Cost for Each Scenario

Scenario 1: Hit in L1 Cache

• Probability: This is the L1 hit rate, H₁.
  P(L1 Hit) = 0.95
• Time Cost: This is the L1 access time.
  T(L1 Hit) = 10 ns
• Contribution to AMAT:
  0.95 × 10 ns = 9.5 ns

Scenario 2: Miss in L1, Hit in L2

• Probability: This occurs if we miss L1 AND hit L2. The L2 hit rate (H₂) is a *local* hit rate, meaning it's the probability of a hit given an L1 miss.
  P(L1 Miss, L2 Hit) = P(L1 Miss) × P(L2 Hit | L1 Miss) = (1 - H₁) × H₂
= (1 - 0.95) × 0.85 = 0.05 × 0.85 = 0.0425
• Time Cost: This is the total time given for an L2 access.
  T(L2 Hit) = 20 ns
• Contribution to AMAT:
  0.0425 × 20 ns = 0.85 ns

Scenario 3: Miss in L1, Miss in L2

• Probability: This occurs if we miss L1 AND miss L2.
  P(L1 Miss, L2 Miss) = P(L1 Miss) × P(L2 Miss | L1 Miss) = (1 - H₁) × (1 - H₂)
= (1 - 0.95) × (1 - 0.85) = 0.05 × 0.15 = 0.0075
• Time Cost: This is the total time given for a Main Memory access.
  T(MM Hit) = 200 ns
• Contribution to AMAT:
  0.0075 × 200 ns = 1.5 ns

Step 3: Sum the Contributions to Find AMAT

The final AMAT is the sum of the weighted costs of all possible scenarios.

AMAT = (Contribution from L1 Hit) + (Contribution from L2 Hit) + (Contribution from MM Hit)
AMAT = 9.5 ns + 0.85 ns + 1.5 ns
AMAT = 11.85 ns

The question asks to round the answer to two decimal places. The calculated value, 11.85, is already in the correct format.

Bibliography:
- Patterson, D. A., & Hennessy, J. L. (2017). Computer Organization and Design: The Hardware/Software Interface. Morgan Kaufmann. (Chapter 5: Large and Fast: Exploiting Memory Hierarchy).
- Stallings, W. (2016). Computer Organization and Architecture: Designing for Performance. Pearson. (Chapter 4: Cache Memory).

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.