GATE CS 2025 Set 1 Q.53: Memory Hierarchy: Cache, Main Memory and Secondary Storage

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)

Memory hierarchy diagram showing Processor at the top, followed by L1 cache (Hit rate = 95%, Access time = 10 ns), followed by L2 cache (Hit rate = 85%, Access time including L1 cache miss penalty = 20 ns), followed by Main Memory (Access time including L1 and L2 cache miss penalty = 200 ns).

Your answer

Official answer and solution

Accepted answers: 11.83 to 11.87
From: Official GATE 2025 answer key

Solution

Compute the weighted average of the three mutually exclusive outcomes (L1 hit, L1 miss & L2 hit, L1 miss & L2 miss), noting that the given L2 and Main Memory times already include the prior miss penalties.

From the figure, the cumulative access times for the three cases are already given directly:

L1 hit (probability $h_1 = 0.95$ ): takes $T_1 = 10\text{ ns}$ .
L1 miss, L2 hit (probability $(1 - h_1) h_2 = 0.05 \times 0.85 = 0.0425$ ): takes $T_2 = 20\text{ ns}$ (including L1 miss penalty).
L1 miss, L2 miss (probability $(1 - h_1)(1 - h_2) = 0.05 \times 0.15 = 0.0075$ ): takes $T_m = 200\text{ ns}$ (including L1 and L2 miss penalty).

Therefore, the Average Memory Access Time (AMAT) is:

\text{AMAT} = (0.95 \times 10) + (0.0425 \times 20) + (0.0075 \times 200) = 9.5 + 0.85 + 1.5 = 11.85\text{ ns}

Final answer

11.85

Common trap

Adding $10\text{ ns}$ again to the L2 and Main Memory times despite the diagram explicitly stating 'including L1 (and L2) cache miss penalty'.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 1 (CS1)
Question: 53 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source