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

To find the total number of cache misses, we first determine how the array is mapped to the cache blocks.

1. Memory Blocks Spanned by the Array:

• Array start address: $1100 ext{H} = 4352$
• Array size: $50 \times 50 = 2500$ bytes
• Array end address: $4352 + 2500 - 1 = 6851$
• Cache block size: $64$ bytes
• Starting memory block: $\lfloor 4352 / 64 \rfloor = 68$
• Ending memory block: $\lfloor 6851 / 64 \rfloor = 107$
• Total blocks spanned: $107 - 68 + 1 = 40$ blocks (from block 68 to 107)

2. First Access Pass:

Since the cache is initially empty, accessing these $40$ blocks sequentially results in $40$ compulsory misses.

The cache has $32$ lines (indexed $0$ to $31$). The blocks map to cache lines using $\text{Line} = \text{Block} \pmod{32}$:

• Blocks $68$ to $75$ map to lines $4$ to $11$.
• Blocks $76$ to $95$ map to lines $12$ to $31$.
• Blocks $96$ to $99$ map to lines $0$ to $3$.
• Blocks $100$ to $107$ map to lines $4$ to $11$ (overwriting blocks $68$ to $75$).

3. Second Access Pass:

• Blocks $68$ to $75$: Map to lines $4$ to $11$ (which currently hold blocks $100$ to $107$) $\rightarrow$ $8$ misses.
• Blocks $76$ to $95$: Map to lines $12$ to $31$ (which still hold blocks $76$ to $95$) $\rightarrow$ $0$ misses.
• Blocks $96$ to $99$: Map to lines $0$ to $3$ (which still hold blocks $96$ to $99$) $\rightarrow$ $0$ misses.
• Blocks $100$ to $107$: Map to lines $4$ to $11$ (which now hold blocks $68$ to $75$ loaded earlier in this pass) $\rightarrow$ $8$ misses.

Total misses in the second pass = $8 + 8 = 16$.

Total Misses:

$$\text{Total Misses} = 40 \text{ (First Pass)} + 16 \text{ (Second Pass)} = 56$$