GATE CS 2022 Q.54: Memory Hierarchy: Cache, Main Memory and Secondary Storage

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?

Every access to S is a hit.

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

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

Every access to R evicts Q from the cache.

Official answer and solution

Official answer: A, B and D
From: Official GATE 2022 answer key

Solution

Determine the line and tag fields for each memory address and trace the direct-mapped cache behavior.

Cache parameters:

Cache size = 2 KB = 2048 bytes.
Block size = 64 bytes ( $2^6$ bytes $\implies 6$ offset bits, bits 5..0).
Number of lines = $\frac{2048}{64} = 32$ lines ( $2^5$ lines $\implies 5$ index bits, bits 10..6).
Address size = 16 bits (64 KB space). Tag bits = $16 - 5 - 6 = 5$ bits (bits 15..11).

Mapping addresses:

P (0xA248 = 1010 0010 0100 1000):
- Tag = bits 15..11 = 10100 ( $0x14$ )
- Line = bits 10..6 = 01001 (Line 9)
- Offset = bits 5..0 = 001000 (8)
Q (0xC28A = 1100 0010 1000 1010):
- Tag = bits 15..11 = 11000 ( $0x18$ )
- Line = bits 10..6 = 01010 (Line 10)
- Offset = bits 5..0 = 001010 (10)
R (0xCA8A = 1100 1010 1000 1010):
- Tag = bits 15..11 = 11001 ( $0x19$ )
- Line = bits 10..6 = 01010 (Line 10)
- Offset = bits 5..0 = 001010 (10)
S (0xA262 = 1010 0010 0110 0010):
- Tag = bits 15..11 = 10100 ( $0x14$ )
- Line = bits 10..6 = 01001 (Line 9)
- Offset = bits 5..0 = 100010 (34)

Key observations:

P and S have the same Tag ( $0x14$ ) and map to the same Line (Line 9). In fact, they reside in the exact same 64-byte block (bytes 0xA240 to 0xA27F).
Q and R map to the same Line (Line 10) but have different tags ( $0x18$ vs $0x19$ ). They conflict on Line 10.

Tracing the access sequence $P, Q, R, S$ :

Iteration 1:
- Access P: Miss. Loads block for line 9 (containing both P and S).
- Access Q: Miss. Loads block for line 10.
- Access R: Miss. Evicts Q from line 10 and loads R.
- Access S: Hit! (Block containing S is already in line 9, loaded by P).
Iterations 2 to 10:
- Access P: Hit (line 9 was untouched by Q and R).
- Access Q: Miss. Evicts R from line 10.
- Access R: Miss. Evicts Q from line 10.
- Access S: Hit (line 9 still holds the block).

Evaluating the statements:

(A) TRUE: S is a hit in all 10 iterations.
(B) TRUE: The block containing P and S is loaded on the very first access and is never evicted because no other accessed address maps to line 9.
(C) FALSE: At the end of execution, Line 9 contains the block with both P and S, and Line 10 contains R. So P, S, and R all reside in the cache.
(D) TRUE: In every iteration, Q is accessed just before R, placing Q in Line 10; hence every subsequent access to R evicts Q.

Thus, (A), (B), and (D) are TRUE.

Final answer

Options (A), (B), (D)

Common trap

Thinking P and S conflict on line 9, missing that they have identical tags and reside in the same cache block.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2022 Computer Science and Information Technology (CS)
Question: 54 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source