993 views

Consider a system with $2 \;\text{KB}$ direct mapped data cache with a block size of $64 \; \text{bytes}.$ The system has a physical address space of $64 \; \text{KB}$ and a word length of $16 \; \text{bits.}$ During the execution of a program, four data words $\text{P, Q, R,}$ and $\text{S}$ are accessed in that order $10$ times $\text{(i.e., PQRSPQRS}\dots).$ 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 $\text{P, Q, R,}$ and $\text{S}$ are $\text{0xA248, 0xC28A, 0xCA8A,}$ and $\text{0xA262},$ respectively. For the execution of the above program, which of the following statements is/are $\text{TRUE}$ with respect to the data cache?

1. Every access to $\text{S}$ is a hit.
2. Once  $\text{P}$ is brought to the cache it is never evicted.
3. At the end of the execution only $\text{R}$ and $\text{S}$ reside in the cache.
4. Every access to $\text{R}$ evicts $\text{Q}$ from the cache.

Subscribe to GO Classes for GATE CSE 2022

Physical memory = 64KB ===> 16 bits required to represent Physical memory

Cache memory = 2KB ===> 11 bits for cache memory

Block size = 64 B = 32 words ===> 6 bits because of system is Byte addressable.

Tag = 16-11 = 5 bits

Cache index = 11-6 = 5 bits

Block offset = 6 bits

P = 0XA248 = 1010 0010 0100 1000 = $10100\; \color{red}{01001}\; 001000$ ( Tag – cache index – Block offset )

Q = 0XC28A = 1100 0010 1000 1010 = $11000\; \color{red}{01010}\; 001010$

R = 0XCA8A = 1100 1010 1000 1010 = $11001\; \color{red}{01010} \;001010$

S=0XA262 = 1010 0010 0110 0010 = $10100\; \color{red}{01001} \;100010$

Given that, Direct mapped cache,

If we observe, P and S are belongs to same Block ( Tag and cache bits are same ). Therefore every access of S should result in a hit due to neither Q nor R competing for the same cache block and once P brought to the cache, it is never evicted.

If we observe Q and R, those are competing for same cache block. So at the end R only present in the cache due to R is accessed at last. ( compaing to Q ) and every access to R evicts Q from the Cache.

Therefore at the end, P,R and S in the Cache.

Options A,B and D are true.
by
35 104 555

Is the very first access to S is a hit?
I think it’s miss because initially data cache is empty. So the first access is a miss and now the data item is added to the cache. Can you explain if I am wrong?
P and S words are belongs to same block. So first access of S leads to hit.
Ok. Got it. Thanks for help
Word Length is 16 bits.Then how memory is still byte addressable
word addressable - every word has unique number/address.

Byte addressable - every byte has unique number/address.

in the question, it is mentioned that - " The address of the first byte of " - from that, we can conclude that, given is byte addressable.
Thanks Understood. So the word length is given just to confuse us?