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

Code being C implies array layout is row-major.

http://en.wikipedia.org/wiki/Row-major_order

When $A[0][0]$ is fetched, $128$ consecutive bytes are moved to cache. So, for the next $\dfrac{128}{8} -1=15$ memory references there won't be a cache miss.
For the next iteration of $i$ loop also the same thing happens as there is no temporal locality in the code. So, number of cache misses for $P1$ is

$= \dfrac{512}{16} \times 512$

$ = 32 \times 512 $

$=2^{14} = 16384$

Correct Answer: $C$

Comments

If there wouldn’t have been any cache memory here, then the answer would have been option D , right?

511 + (512*511)/2 + 1 = 262144.

Please correct me if I am wrong.

---

Easy approach:-

FOR $P1:-$

Size of Array A = $2^9 * 2^9 * 2^3 B$  = $2^{21}B$

Block Size given = $2^7B = 128B$

Therefore no. of blocks required to store all the elements = $2^{21} / 2^7 = 2^{14} = 16384 $

Since it is row wise accessing of elements and from @Arjun Sir’s answer : 

When A[0][0] is fetched, 128 consecutive bytes are moved to cache. So, for the next 128/8−1=15 memory references there won't be a cache miss.

It's $(128/8)-1$ because $1$ block has size = $128B$ and $1$ element has size $= 8 B$. Therefore in $1$ block there are $128/8 = 16$ elements. Out of these $16$ elements, only the first element will be a cache miss and the rest $15$ elements in the block are hits  (because after we bring the block, the next $15$ elements will be present in the block) . Therefore, for every block we have $1$ cache miss. Thus, compiling everything: - 

We can say that for every block, there will be a cache miss. Hence total number of cache misses = no. of blocks required to store all the elements = $16384 $. Option $C$.

FOR $P2 :-$ 

The storage is row major order(by default). But we are accessing the elements column wise. Hence for every element there is a miss. 

Therefore total no. of cache misses = no. of elements = $2^9 * 2^9 = 2^{18}$ 

---

@Abhrajyoti00 small typo i think 128/8 it would be rather than 128/7

Answer 2

$\text{Number of Cache Lines} = \dfrac{2^{15}B}{128B} = 256$
$\text{In 1 Cache Line} = \dfrac{128B}{8B} = 16\ elements$

$P_1 = \dfrac{\text{total elements in array}}{\text{elements in a cache line}}$

$=\dfrac{512 \times 512}{16}$

$= 2^{14}$

$= 16384.$

It is so because for $P_1$ for every line there is a miss, and once a miss is processed
we get $16$ elements in memory. So another miss happens after $16$ elements.

Hence, answer is option C.

Comments

this should be best answer

---

think it the same way one page in paging.

---

@Arnabvasudev23 cache lines is basically number of cache blocks 

Answer 3

Right answer is option C. 

Comments

Best answer , thanks

---

How are the number of references 512×512 in method 1?

Please help.

---

That is the total number of elements we are talking about here.

Answer 4

If you aren't getting clear idea about this question..Then please watch it.

Answer 5

Hence Option C is correct.

Comments

Ye sabse easy explanation tha!... thankyou

Answer 6

First we talk about P1::

Cache size=32KB

Block Size=128Byte

Number of Block=256

Since array element are stored in row major fashion and number of element in each block=16(128(Block size)/8(array element size));

Suppose are are stored like below ways as::

A[0][0] A[0][1]..................A[0][15]

So whenever P1 will fetch A[0][0] it will be fetch all 15 so Miss ratio==1/16

Since array size=2^18

Since out of 16 reference only one miss happen ,then out of 2^18 number of misses will be=2^18*1/16=2^14=16384

M1=16384;

Now for P2::;

Number of Misses will be=2^18 bcz of column major order along with all 2^18 references will be Miss.

So M2=2^18

Therefor;

M1/M2=1/16