Skip to content
GATETECH
Official PYQ · 2022Q23Memory Hierarchy: Cache, Main Memory and Secondary StorageNAT1 mark

GATE CS 2022 Q23 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

Explain with AI

A cache memory that has a hit rate of 0.80.8 has an access latency 10  ns10 \; \text{ns} and miss penalty 100  ns.100 \; \text{ns}. An optimization is done on the cache to reduce the miss rate. However, the optimization results in an increase of cache access latency to 15  ns,15 \; \text{ns}, whereas the miss penalty is not affected. The minimum hit rate (rounded off to two decimal places) needed after the optimization such that it should not increase the average memory access time is _______________.

View worked solution

Answer: 0.85

The Average Memory Access Time (AMAT\text{AMAT}) of a cache system is given by the formula:

AMAT=Hit Time+(Miss Rate×Miss Penalty)\text{AMAT} = \text{Hit Time} + (\text{Miss Rate} \times \text{Miss Penalty})

Step 1: Calculate the initial AMAT (Tavg1T_{\text{avg1}})

Given:

  • Initial hit rate (h1h_1) = 0.80.8
  • Initial miss rate (m1m_1) = 1−h1=0.21 - h_1 = 0.2
  • Initial access latency (Hit Time, Tc1T_{c1}) = 10 ns10 \text{ ns}
  • Miss penalty (MM) = 100 ns100 \text{ ns}
Tavg1=Tc1+(1−h1)×MT_{\text{avg1}} = T_{c1} + (1 - h_1) \times M Tavg1=10+0.2×100=10+20=30 nsT_{\text{avg1}} = 10 + 0.2 \times 100 = 10 + 20 = 30 \text{ ns}

Step 2: Set up the inequality for the optimized cache

After optimization:

  • New access latency (Tc2T_{c2}) = 15 ns15 \text{ ns}
  • New hit rate = h2h_2
  • New miss rate = 1−h21 - h_2
  • Miss penalty (MM) remains unchanged = 100 ns100 \text{ ns}

For the average memory access time not to increase, we must have:

Tavg2≤Tavg1T_{\text{avg2}} \le T_{\text{avg1}} Tc2+(1−h2)×M≤30T_{c2} + (1 - h_2) \times M \le 30 15+(1−h2)×100≤3015 + (1 - h_2) \times 100 \le 30

Step 3: Solve for the minimum hit rate (h2h_2)

(1−h2)×100≤15(1 - h_2) \times 100 \le 15 1−h2≤0.151 - h_2 \le 0.15 h2≥0.85h_2 \ge 0.85

Thus, the minimum hit rate needed after the optimization is 0.850.85.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Memory Hierarchy: Cache, Main Memory and Secondary Storage questions