Skip to content
GATETECH
Official PYQ · 2017Set 2 · Q29Memory Hierarchy: Cache, Main Memory and Secondary StorageMCQ1 mark

GATE CS 2017 Set 2 Q29 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

Explain with AI

In a two-level cache system, the access times of L1L_1 and L2L_2 caches are 11 and 88 clock cycles, respectively. The miss penalty from the L2L_2 cache to main memory is 1818 clock cycles. The miss rate of L1L_1 cache is twice that of L2L_2. The average memory access time (AMAT) of this cache system is 22 cycles. The miss rates of L1L_1 and L2L_2 respectively are

Choose one option
View worked solution

Answer: A

To find the miss rates of the L1L_1 and L2L_2 caches, we can use the formula for the Average Memory Access Time (AMAT\text{AMAT}) of a two-level hierarchical cache system:

AMAT=T1+m1×(T2+m2×M2)\text{AMAT} = T_1 + m_1 \times (T_2 + m_2 \times M_2)

Where:

  • T1=1T_1 = 1 cycle (access time of L1L_1 cache)
  • T2=8T_2 = 8 cycles (access time of L2L_2 cache)
  • M2=18M_2 = 18 cycles (miss penalty from L2L_2 to main memory)
  • AMAT=2\text{AMAT} = 2 cycles
  • m1m_1 is the miss rate of L1L_1
  • m2m_2 is the miss rate of L2L_2

We are given that the miss rate of L1L_1 is twice that of L2L_2:

m1=2⋅m2m_1 = 2 \cdot m_2

Substituting these values into the AMAT\text{AMAT} equation:

2=1+(2⋅m2)×(8+m2×18)2 = 1 + (2 \cdot m_2) \times (8 + m_2 \times 18)

Subtract 11 from both sides:

1=2⋅m2⋅(8+18⋅m2)1 = 2 \cdot m_2 \cdot (8 + 18 \cdot m_2) 1=16⋅m2+36⋅m221 = 16 \cdot m_2 + 36 \cdot m_2^2

This gives us the quadratic equation:

36⋅m22+16⋅m2−1=036 \cdot m_2^2 + 16 \cdot m_2 - 1 = 0

Solving for m2m_2 using the quadratic formula m2=−b±b2−4ac2am_2 = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}:

m2=−16±162−4×36×(−1)2×36m_2 = \frac{-16 \pm \sqrt{16^2 - 4 \times 36 \times (-1)}}{2 \times 36} m2=−16±256+14472m_2 = \frac{-16 \pm \sqrt{256 + 144}}{72} m2=−16±40072m_2 = \frac{-16 \pm \sqrt{400}}{72} m2=−16±2072m_2 = \frac{-16 \pm 20}{72}

Since the miss rate must be positive:

m2=472=118≈0.0556m_2 = \frac{4}{72} = \frac{1}{18} \approx 0.0556

Now, calculate m1m_1:

m1=2⋅m2=2×118=19≈0.111m_1 = 2 \cdot m_2 = 2 \times \frac{1}{18} = \frac{1}{9} \approx 0.111

Thus, the miss rates of L1L_1 and L2L_2 are approximately 0.1110.111 and 0.0560.056, respectively.

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