GATE CSE 2006 | Question: 81

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 $M1$ and that for $P2$ be $M2$.

The value of the ratio $\frac{M_{1}}{M_{2}}$:

• A. $0$ 
• B. $\frac{1}{16}$
• C. $\frac{1}{8}$
• D. $16$ 

Comments

another good source- 

---

Nice:)

---

We can think 512* 512 2d array like 512 1d array each of size 512 element

It is given that element size is 8 byte so each 1d array size is 512 * 8 byte so 4KB

cache size given 32kb and 128 byte block size so,

total line in cache is 2^15/2^7 is 2^8

so we find out that their are 2^8 line in cache so at a time max 2^8 cache misses can happen then cache will filled up

we already find out that one 1d array size is 4KB and we know cache size is 32kb so number of 1d array we can load into cache at a time is 32kb/4kb = 8.

so 8 1d array at a time then total how many round needed to finish up all the 1d array ?

so their are 512 1d array and we can load 8 at a time so total round is 512/8 = 64 round

lets count now cache miss for this 64 round

ok so how many misses in 1 round?

so in our case in 1st  round we are feeling the cache total then in 2nd round we are overriding all the cache data. so for every round 2^8 misses so

64 round 64*2^8 = 2^14 misses so M1 = 16384

---

 

Lets move to column major access( i.e. M2) and data store in raw major order by default is C language

so for M2 we have to know when we store the 1d array how many element store per block and how many block it can take to store only one 1d array and their are 512 such 1d array keeping in mind.

---

Mistake i did when i was solving the question

---

 

i think like their are 2^14 misses for 64 round means for here we done with 2^14 cause what we load we access them all and we got to next

 

but due to column major order we unnecessarily load a whole row and access one element and load one more raw. so their are 512 element are their in a raw so we have to do 512*2^14 that is M2 but this is wrong

---

Their are 512 element in one 1d array it is correct but at a time all 512 not loaded because we load one block and 512 element we can’t fit into one block so how many element we can fit into one block?

element size is 8 byte block size is 128 byte so number of element is 2^7/2^3 = 2^4

so only 16 element we will load up for misses that is not 512* 2^14 that is 2^4*2^14

so M2 is 2^18

 

then M1/M2 = 2^14/2^18 = 1/2^4 = 1/16

 

so answer is option B

 

 

 

 

 

Answer 1

(1) Cache size $=32 KB=2^{15}$

(2) Virtual address size > 15 bits (lets denote it as {TagBits + 15 bits} ) 

(3) Block size $=128 B=2^7$

(4) $512=2^9$

(5) Array element size $=8B=2^3$

(6) $\frac{(3)}{(5)}=\frac{128B}{8B}=2^4=16$ elements per block

(7) Word offset = 7 bits …from (3)

(8) Bits required to index word in cache =15   …from (1)

(9) Bits to index cache line $=(8)-(7)=15-7=9$

(10) Assume A[0][0] is stored at 0th memory location = {TagBits + 15 zeroes}

15 zeroes mod $2^7$ = most significant 8 zeroes, which are used to index cache lines:



So A[0][0] will go in line 0.

(11) Bytes/row = (4) × (5) = $2^{12}$

(12) Address of last byte in first row, i.e. of A[0][511] = {00..00 + twelve 1’s} 

(13) Address of first byte in 2nd row = next address of (12) = {00..00 + 1 + twelve 0’s}



(14) Address of first byte in 3rd row = next address of (12) = {00..00 + 10 + twelve 0’s}

(15) So, CACHE_LINE occupied by row is incremented $32=2^5$ for each row.

There are $2^9=512$ rows  … from (9)

$\frac{2^9}{2^5}=2^4=16$

Every 16th row will occupy same line. Cache line of block containing A[0][0] will be replaced by block of A[16][0], far before accessing A[0][1]. Same for other elements. Thus there will be no hits at all while accessing any array element.

Comments

I think bits to index cache line is 8 bits. Correct me if I'm wrong.

Answer 2

…………………………………………….…………………………….………………………………………