IAE Academy

GATE 2025 CS2 Q.55: solution and answer

GATE 2025 · CS2Q.55 · 2 marks · NAT

Given a computing system with two levels of cache (L1 and L2) and a main memory. The first level (L1) cache access time is 1 nanosecond (ns) and the "hit rate" for L1 cache is 90% while the processor is accessing the data from L1 cache. Whereas, for the second level (L2) cache, the "hit rate" is 80% and the "miss penalty" for transferring data from L2 cache to L1 cache is 10 ns. The "miss penalty" for the data to be transferred from main memory to L2 cache is 100 ns.

Then the average memory access time in this system in nanoseconds is __________ . (rounded off to one decimal place)

See the question in the paper
GATE 2025 CS2 question 55Tap to open full size

Answer and solution

ANSWER

The average memory access time (AMAT) for this two-level cache system is 4.0 ns.

Official answer: 4.0Source: Official answer key, GATE 2025 CS2 (IIT Roorkee)

  1. Write AMAT for a two-level cache hierarchy as a recursive expression: AMAT = L1 access time + (L1 miss rate) × (penalty on an L1 miss), where the L1-miss penalty is itself the cost of consulting L2.

  2. L1 access time = 1 ns. L1 hit rate = 90% ⇒ L1 miss rate = 1 − 0.9 = 0.1.

  3. On an L1 miss, the data is sought in L2. If L2 hits, the cost charged is the stated "miss penalty for transferring data from L2 cache to L1 cache" = 10 ns. L2 hit rate = 80% ⇒ L2 miss rate = 1 − 0.8 = 0.2.

  4. If L2 also misses (probability 0.2, given an L1 miss), an additional "miss penalty for the data to be transferred from main memory to L2 cache" = 100 ns is incurred on top of the 10 ns.

  5. So the expected extra time on an L1 miss = 10 + (L2 miss rate) × 100 = 10 + 0.2 × 100 = 10 + 20 = 30 ns.

  6. AMAT = L1 access time + (L1 miss rate) × (extra time on L1 miss) = 1 + 0.1 × 30 = 1 + 3 = 4.0 ns.

KEY IDEA

In a multi-level cache, AMAT is built recursively from the innermost level outward: AMAT = (access time of level ) + (miss rate of level ) × (penalty incurred on a miss at level ), where that miss penalty is itself the access/transfer cost to the next level plus (that level's own miss rate × the penalty of going further down).

WATCH OUT FOR

Treating the 10 ns and 100 ns figures as independent, unconditional penalties and simply adding them (e.g., , using the L2 miss rate against the overall access count rather than conditioning it on an L1 miss first), or forgetting that the L2 miss penalty (100 ns) is only incurred on the fraction of accesses that miss in both L1 and L2, not on every L1 miss.

From the GATE 2025 CS2 paper. Every question of this paper · Download the full paper · All 22 Memory & cache questions, with notes

More Memory & cache questions