Skip to content
GATETECH
Official PYQ · 2024Set 1 · Q46Memory Hierarchy: Cache, Main Memory and Secondary StorageNAT2 marks

GATE CS 2024 Set 1 Q46 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

Explain with AI

A given program has 25%25 \% load/store instructions. Suppose the ideal CPI\text{CPI} (cycles per instruction) without any memory stalls is 22. The program exhibits 2%2 \% miss rate on instruction cache and 8%8 \% miss rate on data cache. The miss penalty is 100100 cycles. The speedup (rounded off to two decimal places) achieved with a perfect cache (i.e., with NO data or instruction cache misses) is __________.

View worked solution

Answer: 3

To find the speedup achieved with a perfect cache, we compare the execution time (or CPI) of the system with cache stalls to the system with a perfect cache.

1. CPI with a Perfect Cache:

With a perfect cache, there are no instruction or data cache misses. Thus, the CPI is simply the ideal CPI:

CPIperfect=2\text{CPI}_{\text{perfect}} = 22. CPI with Cache Stalls:

The actual CPI includes stalls from both instruction cache misses and data cache misses.

  • Instruction Cache Stalls per Instruction:
    Every instruction must be fetched. Therefore, the instruction miss rate applies to all instructions.
    Stallsinstruction=Instruction Miss Rate×Miss Penalty=0.02×100=2 cycles\text{Stalls}_{\text{instruction}} = \text{Instruction Miss Rate} \times \text{Miss Penalty} = 0.02 \times 100 = 2\text{ cycles}
  • Data Cache Stalls per Instruction:
    Only load/store instructions (which constitute 25%25\% of the program) access the data cache.
    Stallsdata=Fraction of Load/Store×Data Miss Rate×Miss Penalty\text{Stalls}_{\text{data}} = \text{Fraction of Load/Store} \times \text{Data Miss Rate} \times \text{Miss Penalty}
    Stallsdata=0.25×0.08×100=2 cycles\text{Stalls}_{\text{data}} = 0.25 \times 0.08 \times 100 = 2\text{ cycles}

Adding these to the ideal CPI gives the total actual CPI:

CPIactual=Ideal CPI+Stallsinstruction+Stallsdata=2+2+2=6 cycles\text{CPI}_{\text{actual}} = \text{Ideal CPI} + \text{Stalls}_{\text{instruction}} + \text{Stalls}_{\text{data}} = 2 + 2 + 2 = 6\text{ cycles}3. Speedup Calculation:

The speedup achieved by using a perfect cache is:

Speedup=CPIactualCPIperfect=62=3\text{Speedup} = \frac{\text{CPI}_{\text{actual}}}{\text{CPI}_{\text{perfect}}} = \frac{6}{2} = 3

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