GATE CSE 2006 | Question: 80

Question

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:

• A. $0$
• B. $2048$
• C. $16384$
• D. $262144$

Comments

store array in row major order

---

Those who missed that 8B elements , you are not alone !!

---

Option C is correct

In row major order

Answer 1

 

so Option C 

Comment below if u get anything wrong about it

Answer 2

 

2^14=16384 ...................…..........….

Answer 3

1. First understand the given cache structure:

Cache size: 32KB

Block size: 128B

 

2. Now understand the program:

A 2D array of 512*512 elements meaning 262144 elements

The elements are accessed in a row major order.

Each element is of 8 Bytes.
 

Now size of each block is 128 B

Therefore at a time 16 elements in the array can be accessed.

But why 16 needed at a time?

Because to exploit spatial locality. (Spatial locality is major factor for faster computation)

Now when we put all these 16 non decreasing indexed element at a time then there will not be a single chance to exploit the spatial locality as every element is new no use of all the previous elements to be used.

 

So we can say every element will result in a miss.

But elements are accessed as a group of 16 and when 1 group of 16 elements is fetched they will contribute to 1 memory miss.

So 262144/16 = 16384 memory misses will be there.

 

Answer 4

we need to have understanding on paging, page replacement technique and memory management. Similar question asked in gate 2023 

Operating System: GATE CSE 2023 | Question: 47 

https://share.google/VqIE19IGHluCvTJHZ

Answer 5

Does anyone know good lectures to study comparator and mux working in cache

@GOClasses @Arjun 

Answer 6

HEY!! CHECK OUT MY SOLUTION IN PDF.