IAE Academy

GATE 2022 CS Q.54: solution and answer

GATE 2022 · CSQ.54 · 2 marks · MSQ

Consider a system with 2 KB direct mapped data cache with a block size of 64 bytes. The system has a physical address space of 64 KB and a word length of 16 bits. During the execution of a program, four data words P, Q, R, and S are accessed in that order 10 times (i.e., PQRSPQRS…). Hence, there are 40 accesses to data cache altogether. Assume that the data cache is initially empty and no other data words are accessed by the program. The addresses of the first bytes of P, Q, R, and S are 0xA248, 0xC28A, 0xCA8A, and 0xA262, respectively. For the execution of the above program, which of the following statements is/are TRUE with respect to the data cache?

  1. (A)

    Every access to S is a hit.

  2. (B)

    Once P is brought to the cache it is never evicted.

  3. (C)

    At the end of the execution only R and S reside in the cache.

  4. (D)

    Every access to R evicts Q from the cache.

See the question in the paper
GATE 2022 CS question 54Tap to open full size

Answer and solution

ANSWER

The TRUE statements are (A) Every access to S is a hit, (B) Once P is brought to the cache it is never evicted, and (D) Every access to R evicts Q from the cache. (C) is false.

Official answer: A, B, DSource: Official answer key, GATE 2022 CS (IIT Kharagpur)

  1. Cache size = 2 KB, block size = 64 bytes ⇒ number of blocks = 2048/64 = 32 ⇒ index needs bits and offset needs bits. Physical address space = 64 KB ⇒ address width = 16 bits ⇒ tag = 16 − 5 − 6 = 5 bits. So a 16-bit address splits as tag(5) | index(5) | offset(6).

  2. Write each byte address as 16-bit binary and split into tag/index/offset:

  3. P and S have the SAME (tag, index) = (20, 9). Since the block size is 64 bytes, offsets 8 and 34 both lie inside the same 64-byte block, so P and S are always brought into the cache together as one line: whichever of P, S is accessed first loads a block that already contains the other's data.

  4. Q and R have the SAME index = 10 but DIFFERENT tags (24 vs 25), so they occupy the same cache set and permanently conflict with each other every time both are accessed in a period.

  5. Trace period 1 (P, Q, R, S): P → compulsory miss, loads the tag-20 block into set 9 (this block covers offset 8 for P and offset 34 for S). Q → compulsory miss, loads tag-24 block into set 10. R → tag mismatch in set 10 (holds tag 24, needs tag 25) → miss, evicts Q, loads R's block. S → set 9 already holds tag 20 (loaded for P) → HIT, even on this very first access to S.

  6. Trace every subsequent period (2nd through 10th), P, Q, R, S: P → set 9 was never touched by Q/R traffic (different index) → HIT. Q → set 10 currently holds R (tag 25) → miss, evicts R, loads Q (tag 24). R → set 10 currently holds Q (tag 24) → miss, evicts Q, loads R (tag 25). S → set 9 still holds the tag-20 block from P → HIT.

  7. (A) Every one of the 10 accesses to S is a HIT (true even in period 1, since P's load already brought in S's block first) → TRUE.

  8. (B) Set 9 (holding P's/S's block) is never disturbed by any Q or R access (they only ever touch set 10), so once P's block is loaded it is never evicted → TRUE.

  9. (C) At the end of execution, set 9 holds the tag-20 block, which contains BOTH P's and S's data (same 64-byte line), and set 10 holds R (the last one loaded in the final period). So the resident data is P, R and S together, not 'only R and S' — the claim that P is absent is false → FALSE.

  10. (D) In every one of the 10 periods, Q is loaded into set 10 immediately before R is accessed, and R always misses (tag 25 ≠ tag 24) and evicts whatever is in set 10 at that moment, which is always Q → TRUE for all 10 accesses to R.

KEY IDEA

In a direct-mapped cache, only the (tag, index) pair of an address matters for placement — the offset just locates the byte within a fixed-size block. Here P and S land in the same (tag, index), so they always share one cache line, while Q and R share an index but differ in tag, so they permanently thrash each other's line every time both are accessed in a period.

WATCH OUT FOR

Treating P and S as independent cache entries because their offsets (8 vs 34) look far apart, instead of checking that both offsets fit inside the same 64-byte block once (tag, index) match — this leads students to wrongly mark S's first access as a miss and to wrongly believe P gets evicted, when in fact P and S occupy one shared, never-touched cache line while only Q and R's shared index thrashes.

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

More Memory & cache questions