GATE CS 2007 Q81 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

To determine which cache lines are replaced during the second access, we first identify the memory blocks occupied by the array.

1. Cache and Array Parameters:

• Cache line size: $64$ bytes
• Number of cache lines: $32$
• Array starting address: $1100 ext{H} = 1 imes 16^3 + 1 imes 16^2 = 4352$
• Array size: $50 imes 50 = 2500$ bytes
• Array ending address: $4352 + 2500 - 1 = 6851$

2. Memory Blocks Occupied:

• Starting Block: $\lfloor 4352 / 64 \rfloor = 68$
• Ending Block: $\lfloor 6851 / 64 \rfloor = 107$

The array spans $40$ memory blocks, from Block $68$ to Block $107$.

3. Cache Mapping ($L = B \pmod{32}$):

• Blocks $68$ to $99$ map to cache lines $4$ to $31$, and then $0$ to $3$.
• Blocks $100$ to $107$ map to cache lines $4$ to $11$.

4. First Access Pass:

• Blocks $68$ to $99$ are loaded into cache lines $4$ to $31$ and $0$ to $3$.
• Blocks $100$ to $107$ are then loaded, overwriting lines $4$ to $11$.
• At the end of the first pass, lines $4$ to $11$ contain Blocks $100$ to $107$, while lines $12$ to $31$ and $0$ to $3$ contain Blocks $76$ to $99$.

5. Second Access Pass:

• Accessing Blocks $68$ to $75$ (mapping to lines $4$ to $11$) results in misses, replacing Blocks $100$ to $107$ with Blocks $68$ to $75$.
• Accessing Blocks $76$ to $99$ results in cache hits.
• Accessing Blocks $100$ to $107$ results in misses, replacing Blocks $68$ to $75$ with Blocks $100$ to $107$.

Thus, only line 4 to line 11 are replaced during the second pass.