Official PYQ · 2006Q80Memory Hierarchy: Cache, Main Memory and Secondary StorageMCQ1 mark

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

A CPU has a $32 KB$ direct mapped cache with $128$ byte-block size. Suppose A is two dimensional array of size $512 \times512$ with elements that occupy $8$ -bytes each. Consider the following two C code segments, $P1$ and $P2$ .

P1:

for (i=0; i<512; i++)
{ 
    for (j=0; j<512; j++)
    { 
        x +=A[i] [j]; 
    } 
}

P2:

for (i=0; i<512; i++)
{ 
    for (j=0; j<512; j++)
    { 
        x +=A[j] [i]; 
    } 
}

$P1$ and $P2$ are executed independently with the same initial state, namely, the array $A$ is not in the cache and $i$ , $j$ , $x$ are in registers. Let the number of cache misses experienced by $P1$ be $M_{1}$ and that for $P2$ be $M_{2}$ .

The value of $M_{1}$ is:

View worked solution

Answer: C

To find the number of cache misses $M_1$ experienced by the program $P1$ , we analyze the cache configuration and the array access pattern.

1. Cache and Array Parameters

Cache block size: $128\text{ bytes}$
Array element size: $8\text{ bytes}$
Number of elements per cache block: $\frac{128\text{ bytes}}{8\text{ bytes}} = 16\text{ elements}$
Total elements in array $A$ : $512 \times 512 = 262,144\text{ elements}$

2. Access Pattern in $P1$

In C, multi-dimensional arrays are stored in row-major order. The nested loops in $P1$ access the elements as follows:

A[0][0], A[0][1], A[0][2], ..., A[0][511], A[1][0], ...

This represents a strictly sequential memory access pattern.

3. Cache Miss Calculation ( $M_1$ )

The first access $A[0][0]$ results in a cache miss. This miss brings a block of $16$ consecutive elements ( $A[0][0]$ to $A[0][15]$ ) into the cache.
The next $15$ accesses ( $A[0][1]$ to $A[0][15]$ ) are cache hits.
The $17^{\text{th}}$ access $A[0][16]$ results in another cache miss, loading the next $16$ elements.

Since the access is purely sequential and each element is accessed exactly once, there are no conflict misses affecting the active block. Thus, we experience exactly $1$ miss for every $16$ elements accessed.