3,500 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.

### 1 comment

Sir it is given the question that cache is empty, so how every access of S is a hit there exist a cold start miss right?

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.

No word length is not a redundant information because in the question it is stated that p,q,r,s are words
Can u please explain initially the cache is empty according to the question so when for the first time cpu will access the words it will be definitely a miss.

@dutta18

There's a relationship between P and S. Due to that even first access of S also hit.

You just need to understand what's that relationship.

If P brought S comes along, only 14B  apart and never brought again

If Q brought, it brings stuffs around him/her, but R is more than 64B apart

So, when R is fetched, Q is replaced and this happens on every iteration of Q → R

Ans: A,B,D

by