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

To find the ratio $\frac{M_1}{M_2}$, we analyze the cache behavior for both programs $P1$ and $P2$.

Cache Parameters:

• Cache Size = $32\text{ KB}$
• Block Size = $128\text{ bytes}$
• Number of Cache Blocks = $\frac{32\text{ KB}}{128\text{ B}} = 256$ blocks
• Array Element Size = $8\text{ bytes}$
• Number of elements per cache block = $\frac{128}{8} = 16$ elements
• Size of one row of array $A$ = $512 \times 8\text{ bytes} = 4096\text{ bytes}$ ($32$ cache blocks)

1. Analysis of $P1$ (Row-Major Access):

In $P1$, elements are accessed sequentially: $A[0][0], A[0][1], A[0][2], \dots$

• The first access $A[0][0]$ is a miss and brings a block of $16$ elements ($A[0][0]$ to $A[0][15]$) into the cache.
• The next $15$ accesses are hits.
• This pattern of $1$ miss followed by $15$ hits repeats throughout the execution.
• Total misses: $M_1 = \frac{512 \times 512}{16}$

2. Analysis of $P2$ (Column-Major Access):

In $P2$, elements are accessed column-wise: $A[0][0], A[1][0], A[2][0], \dots$

• The stride between consecutive accesses is one row ($4096\text{ bytes}$ or $32$ cache blocks).
• Since the cache has $256$ blocks, elements $A[i][j]$ and $A[i+8][j]$ map to the same cache block index because $(i \times 32) \pmod{256} = ((i+8) \times 32) \pmod{256}$.
• Due to this conflict, blocks are repeatedly evicted before their other elements can be reused. Consequently, every single access results in a cache miss.
• Total misses: $M_2 = 512 \times 512$

Ratio: