ISRO-DEC2017-38

Question

A CPU has a $32\, KB$ direct mapped cache with $128-byte$ block size.Suppose A is a $2$-$d$
array of size $512\times 512$ with elements that occupy $8\, bytes$ each.Consider the code segment

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

Assuming that array is stored in order $A[0][0], A[0][1],A[0][2]\ldots,$ the number of cache misses is

• A. $16384$
• B. $512$
• C. $2048$
• D. $1024$

Answer 1

No. of elements in 1 block = 128/8 = 16

Block 0: A[0][0] to A[0][15]

Block 1: A[0][16] to A[0][31] and so on...

Now, 

i=0,

          A[0][0] is not present in the cache. Hence a miss (compulsory miss). For the next 15 elements, there is no miss, (j=1 to j=15). j takes values from 0 to 512 and there is a miss after every 16 elements. Hence the total number of misses when i=0 is (512/16) = 32. 

Hence, for i=0 to i=512, number of misses

=No. of iterations * No. of misses in one iteration

=(2^9 * 2^5) = 16834

Option A

Comments

@Sumaiya23 @srestha I just wanna ask one question:

According to the question: There are total 2^8 = 256 blocks in this cache memory. After 256 blocks it comes back again to the first block and there is no miss. isn't that so.

For i=0 there are total 32 block misses that means 32 blocks are covered.

For i = 0 to 7 total 256 blocks are covered.

isn't that after 256th block it comes back again to the first block and there will be no miss? I just wanna where I am getting it wrong.