Question

Consider a system with a processor and a \(4\) KB direct mapped cache with block size of \(16\) bytes. The system has a \(16\) MB physical memory. Four words \(P\), \(Q\), \(R\), and \(S\) are accessed by the processor in the same order \(10\) times. That is, there are a total of \(40\) memory references in the sequence \(P, Q, R, S, P, Q, R, S,\ldots\)

Assume that the cache memory is initially empty. The physical addresses of the words are given below (\(1\) word \(=1\) byte).

\(P: 0x845B32,\ Q: 0x845B26,\ R: 0x845B36,\ S: 0x846B32\)

Which of the following statements is/are true?

Note: \(1K=2^{10}\) and \(1M=2^{20}\)

• A. Every access to \(P\) results in a cache miss
• B. Every access to \(R\) results in a cache hit
• C. Every access to \(Q\) results in a cache miss
• D. Except the first access to \(S\), all subsequent accesses to \(S\) result in cache hits

Hint:

Work out the tag and index for each address and see which of P, Q, R, S share a cache line and which stay isolated on their own line.

Answer 1

The Correct Option is A, B

Step 1: Work out the cache geometry.
The cache is \(4\) KB with a \(16\) byte block, so the number of cache lines is
\[ \frac{4\times1024}{16}=256=2^8 \]
An address splits into a \(4\) bit block offset, since \(16=2^4\) bytes per block, an \(8\) bit line index, since there are \(2^8\) lines, and the remaining higher order bits form the tag. In hexadecimal, since each hex digit is \(4\) bits, the least significant hex digit is the offset, and the next \(2\) hex digits, the second and third digits from the right, together form the index.

Step 2: Split each address into tag, index, and offset.
Writing each address as \(6\) hex digits:
\(P=0x845B32\): offset digit \(=2\), index digits \(=B3\), tag \(=845\).
\(Q=0x845B26\): offset digit \(=6\), index digits \(=B2\), tag \(=845\).
\(R=0x845B36\): offset digit \(=6\), index digits \(=B3\), tag \(=845\).
\(S=0x846B32\): offset digit \(=2\), index digits \(=B3\), tag \(=846\).

Step 3: Notice which words share a cache line.
\(P\) and \(R\) have the exact same tag (\(845\)) and the exact same index (\(B3\)), so they are two different offsets inside the SAME \(16\) byte cache block, offsets \(2\) and \(6\), both well inside a \(16\) byte block. \(Q\) has index \(B2\), a different cache line altogether, so \(Q\) never conflicts with \(P\), \(R\), or \(S\). \(S\) has the same index \(B3\) as \(P\) and \(R\) but a different tag (\(846\) versus \(845\)), so \(S\) fights with \(P\) and \(R\) for the same cache line and evicts whichever block currently sits there.

Step 4: Simulate the first round of accesses, \(P,Q,R,S\), on an empty cache.
\(P\) at line \(B3\): line empty, MISS, and it loads the whole \(16\) byte block with tag \(845\) into line \(B3\), covering both offset \(2\), used by \(P\), and offset \(6\), used by \(R\).
\(Q\) at line \(B2\): line empty, MISS, loading tag \(845\) into line \(B2\).
\(R\) at line \(B3\): line \(B3\) already holds tag \(845\) from the \(P\) access, and \(R\) also has tag \(845\), so this is a HIT.
\(S\) at line \(B3\): line \(B3\) holds tag \(845\), but \(S\) needs tag \(846\), MISS, evicting \(845\) and loading tag \(846\) into line \(B3\) instead.

Step 5: Simulate every later round, \(P,Q,R,S\) again.
\(P\) at line \(B3\): line \(B3\) currently holds tag \(846\), left behind by the previous round's \(S\), but \(P\) needs tag \(845\), so this is again a MISS, evicting \(846\) and reloading \(845\).
\(Q\) at line \(B2\): still holds tag \(845\) from the very first access and nothing else ever touches line \(B2\), so this is a HIT every time from the second round onward.
\(R\) at line \(B3\): now holds tag \(845\), freshly reloaded by the \(P\) access just above in this same round, so this is a HIT.
\(S\) at line \(B3\): holds tag \(845\), but \(S\) needs tag \(846\), so this is a MISS again, evicting \(845\).
Because the state at the start of every round from the second one onward is identical, this same miss, hit, hit, miss pattern for \(P,Q,R,S\) repeats for all \(10\) rounds.

Step 6: Match this against the options.
\(P\) misses in round \(1\), cold, empty cache, and misses in every later round too, evicted by the previous round's \(S\), so EVERY access to \(P\) is a miss, confirming option (A). \(R\) hits in round \(1\), right after \(P\) loaded the shared block, and hits in every later round too, right after \(P\) reloads the shared block earlier in that same round, so EVERY access to \(R\) is a hit, confirming option (B). \(Q\) misses only once, on its very first access, then hits for the remaining \(9\) rounds, so it is false that every access to \(Q\) misses, ruling out option (C). \(S\) misses on every single round, including all rounds after the first, because line \(B3\) always ends up holding tag \(845\) right before \(S\) is accessed, so option (D) is false.

Step 7: Final answer.
\[ \boxed{\text{(A) and (B) are true}} \]