Question

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.

Hint:

In a direct-mapped cache, each address maps to exactly one cache block. If multiple addresses map to the same block, the most recent one accessed will evict the previous one.

Answer 1

The Correct Option is A, B, D

Step 1: Determine Cache Parameters

• Block Size: 64 bytes ($2^6$), so the Offset is the lower 6 bits (bits 0–5).
• Number of Blocks: Total Size / Block Size = 2 KB / 64 B = 32 blocks ($2^5$).
• Index: The next 5 bits (bits 6–10) determine the cache block index.

---

Step 2: Map Addresses to Cache Indices

We convert the hexadecimal addresses to binary to extract the index bits (bits 10 to 6): 

Variable	Hex Address	Binary (relevant bits)	Index (Decimal)
P	0xA248	...010 01001 001000	9
Q	0xC28A	...010 01010 001010	10
R	0xCA8A	...010 10100 001010	20
S	0xA262	...010 01001 100010	9

Note: P and S map to Index 9. Q maps to Index 10, and R maps to Index 20.

---

Step 3: Evaluate the Statements

• Statement (A) & (B): P and S map to the same cache block (Index 9). Because the block size is 64 bytes, and the distance between P (0xA248) and S (0xA262) is only 26 bytes, they actually reside within the same memory block. When P is accessed, the entire 64-byte block containing both P and S is brought into the cache. Therefore, once P is cached, S will result in a hit.
• Statement (D): This is Incorrect based on our mapping. R (Index 20) and Q (Index 10) map to different cache blocks. In a direct-mapped cache, R will not evict Q because they do not compete for the same slot.

---

Final Answer:

The correct statements regarding the cache behavior are:(A) and (B)