Cache Memory

GATE CS previous year questions · 6 questions

GATE CS 2025 Set 1 | Question 36

MCQ · 2 marks · −0.66

Consider a memory system with 1M bytes of main memory and 16K bytes of cache memory. Assume that the processor generates 20-bit memory address, and the cache block size is 16 bytes. If the cache uses direct mapping, how many bits will be required to store all the tag values? [Assume memory is byte addressable, 1K=\(2^{10}\), 1M=\(2^{20}\).]

Options for GATE CS 2025 Set 1 | Question 36

Explanation

Answer: (A)

Split the 20-bit address into tag, line index and block offset.

  • Offset: a block has \(16 = 2^4\) bytes, so 4 bits.
  • Index: the cache has \(2^{14} / 2^4 = 2^{10}\) lines, so 10 bits.
  • Tag: \(20 - 10 - 4 = 6\) bits.

Each of the \(2^{10}\) cache lines stores its own 6-bit tag, so the tag storage is \(6 \times 2^{10}\) bits.

Answer: A

GATE CS 2025 Set 1 | Question 53

NAT · 2 marks

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)

Processor, then L1 cache (hit rate 95%, access time 10 ns), then L2 cache (hit rate 85%, access time including L1 cache miss penalty 20 ns), then main memory (access time including L1 and L2 cache miss penalty 200 ns)

Explanation

Answer: 11.83 to 11.87

The L2 and main-memory times already include the time lost on the earlier misses, so each path is simply weighted by its probability.

  • L1 hit: probability \(0.95\), time 10 ns.
  • L1 miss, L2 hit: probability \(0.05 \times 0.85 = 0.0425\), time 20 ns.
  • Both miss: probability \(0.05 \times 0.15 = 0.0075\), time 200 ns.

\[T_{\text{avg}} = 0.95(10) + 0.0425(20) + 0.0075(200) = 9.5 + 0.85 + 1.5 = 11.85 \text{ ns}\]

Answer: 11.85

GATE CS 2025 Set 2 | Question 39

MCQ · 2 marks · −0.66

For a direct-mapped cache, 4 bits are used for the tag field and 12 bits are used to index into a cache block. The size of each cache block is one byte. Assume that there is no other information stored for each cache block.

Which ONE of the following is the CORRECT option for the sizes of the main memory and the cache memory in this system (byte addressable), respectively?

Options for GATE CS 2025 Set 2 | Question 39

Explanation

Answer: (A)

Each block holds one byte, so the address has no offset field: it is just tag plus index, \(4 + 12 = 16\) bits.

  • Main memory: \(2^{16}\) bytes = 64 KB.
  • Cache: the index picks one of \(2^{12}\) blocks of 1 byte each, so the cache holds \(2^{12}\) bytes = 4 KB.

Option D’s 6 KB would add the 4-bit tags to the data (12 bits per block), and its 128 KB would need a 17-bit address, so it does not fit.

Answer: A

GATE CS 2025 Set 2 | Question 55

NAT · 2 marks

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)

Explanation

Answer: 4

Every access pays the L1 time of 1 ns. The 10% of accesses that miss in L1 pay 10 ns to fetch from L2, and the 20% of those that also miss in L2 pay a further 100 ns to bring the data from main memory:

\[\text{AMAT} = 1 + 0.1 \times (10 + 0.2 \times 100) = 1 + 0.1 \times 30 = 4.0\ \text{ns}\]

A common slip is to charge the 100 ns to 20% of all accesses (giving 22 ns). It applies only to the \(0.1 \times 0.2 = 2\%\) of accesses that miss in both caches.

Answer: 4.0

GATE CS 2024 Set 1 | Question 53

MSQ · 2 marks

Consider two set-associative cache memory architectures: WBC, which uses the write back policy, and WTC, which uses the write through policy. Both of them use the LRU (Least Recently Used) block replacement policy. The cache memory is connected to the main memory. Which of the following statements is/are TRUE?

Options for GATE CS 2024 Set 1 | Question 53

Explanation

Answer: (B), (C)

  • (A) False: on a read miss in a full set, LRU picks the victim without looking at its dirty bit. In a write back cache that block may be dirty, and it is then written back before the new block is brought in.
  • (B) True: write through updates main memory on every write, so no cache block is ever newer than memory and evicting one needs no write back.
  • (C) True: a write hit in a write back cache updates only the cache and sets the dirty bit, which changes it from 0 to 1 if the block was clean.
  • (D) False: in a write through cache the victim already matches main memory, so it is simply overwritten. Nothing is written back first (and with no-write-allocate the missed block is not loaded at all).

Answer: B, C

GATE CS 2024 Set 1 | Question 56

NAT · 2 marks

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

Explanation

Answer: 3

Every instruction is fetched, so each one accesses the instruction cache once, while only the 25% load/store instructions also access the data cache. Memory stall cycles per instruction:

\[1 \times 0.02 \times 100 + 0.25 \times 0.08 \times 100 = 2 + 2 = 4\]

The real CPI is therefore \(2 + 4 = 6\), while a perfect cache gives the ideal CPI of 2. The instruction count and clock are the same in both cases, so the speedup is \(6 / 2 = 3.00\).

Applying the 8% data miss rate to every instruction gives a CPI of 12 and a speedup of 6, which overcounts the data accesses.

Answer: 3.00