recategorized by
1,278 views
3 votes
3 votes

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

  1. $16384$
  2. $512$
  3. $2048$
  4. $1024$
recategorized by

1 Answer

Best answer
6 votes
6 votes

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

selected by
Answer:

Related questions

7 votes
7 votes
1 answer
3
gatecse asked Dec 17, 2017
2,308 views
A two-way set associative cache memory unit with a capacity of $16\, KB$ is built using a block size of$8\, words.$ The word length is $32-bits.$ The physical address spa...