Consider a system with 2 KB direct mapped data cache with a block size of 64…
2022
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?
- A.
Every access to S is a hit.
- B.
Once P is brought to the cache it is never evicted.
- C.
At the end of the execution only R and S reside in the cache.
- D.
Every access to R evicts Q from the cache.
Attempted by 168 students.
Show answer & explanation
Correct answer: A, B, D
Key facts: 2 KB direct-mapped cache, block size 64 B ⇒ 2048/64 = 32 lines. Address space 64 KB ⇒ 16-bit addresses. Block offset = 6 bits, index = 5 bits, tag = 5 bits.
Compute block, index, tag (block = address >> 6, index = block mod 32, tag = block >> 5):
P (0xA248) → block 649 → index 9 → tag 20.
Q (0xC28A) → block 778 → index 10 → tag 24.
R (0xCA8A) → block 810 → index 10 → tag 25.
S (0xA262) → block 649 → index 9 → tag 20 (same as P).
Behavior summary and conclusions:
First iteration: P misses and loads block 649 into index 9; Q misses and loads block 778 into index 10; R misses and loads block 810 into index 10, evicting Q; S hits because it is in the same block as P.
Each subsequent iteration repeats the same conflict pattern at index 10 (Q and R alternate and evict each other), while the block at index 9 (P/S) is never touched by other accesses.
Therefore:
• Every access to S is a hit (P and S share the same loaded block).
• Once P is loaded it is never evicted (no other accessed block maps to index 9).
• At the end of execution the cache contains the block for P/S (index 9) and the block for R (index 10), so only R and S (i.e., R and the block containing S/P) reside.
• Every access to R evicts Q because Q and R conflict on index 10 and R always follows Q in the access pattern.
A video solution is available for this question — log in and enroll to watch it.