GATE 2022 CS – Question 54
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?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) Every access to S is a hit.; (B) Once P is brought to the cache it is never evicted.; (D) Every access to R evicts Q from the cache.
Explanation
**Cache geometry.** 2 KB cache, 64-byte blocks gives $2048/64=32$ blocks, so a 6-bit offset and a 5-bit index.
**Block numbers and indices** (block number $=\lfloor\text{addr}/64\rfloor$, index $=$ block number mod 32):
- P `0xA248` $=41544$ gives block 649, index $649\bmod32=9$
- S `0xA262` $=41570$ gives block 649, index 9. **P and S are in the same block.**
- Q `0xC28A` $=49802$ gives block 778, index 10
- R `0xCA8A` $=51850$ gives block 810, index 10, a different tag from Q's block.
**Trace.** P miss (loads the P/S block). Q miss. R miss (evicts Q). S hit (same block as P). Then P hit, Q miss (evicts R), R miss (evicts Q), S hit, and so on.
- (A) Every access to S is a hit: **true**, since S shares P's block and that block is never evicted.
- (B) P's block is never evicted (nothing else maps to index 9): **true**.
- (C) At the end the cache holds the P/S block and R's block (Q has been evicted), so it is not "only R and S": **false**.
- (D) Every R access finds Q's block at index 10 and evicts it: **true**.
Answer: A, B, D.