Cache

Question

Q)My doubt is how to find where A[3][0] will be in which cache line?

Consider a direct-mapped data cache with a 16 blocks of 32 bytes each. How many cache misses will result from the following C code to sum together all of the elements of a two-dimensional array of 32-bit integers? void sum (int A[256][256]) { int i, j, sum = 0; for (j=0; j<256; j++) for (i=0; i<256; i++) sum += A[i][j]; return sum; }

(a) 65536 misses. (b) 8192 misses. (c) 4096 misses. (d) 256 misse

Comments

In case of row major order answer will 256*256 = 65536

In case of column major order 1 column will cause 256/8 = 32 misses

So 256 column will cause = 32*256 = 8192 misses

Answer 1

number of blocks present in cache = 16

size of each block =32 bytes

size of integer = 32 bits = 32/8 = 4 bytes

So 1 block can have 32/4 = 8 integers

Now the answer depends according to arrangement of array in memory

1) Row major order

The addition is done column wise as a result there will be miss for every element

So total number of misses = 256*256 = 65536

2) Column major order

each block can accomodate 8 integers. So we can do addition of 8 integers using one block

So to add 256*256 integers, the number of blocks needed = 256*256/8 = 8192

So number of misses = 8192

Comments

No A[1][0] will map to 0th block not 1st block

---

how? and what is the answer given ?

---

A[0][0] A[0][1].....A[0][7]....Map to block 0

A[0][8]A[0][9]......A[0][15]...block 1

:

:

A[0][120].........A[0][127].......block 15

similarly

A[0][128].........A[0][135] .....block 0

A[0][248].......A[0][255]......block 15

and so

A[1][0].......................A[1][7]......block 0.So how to calculate formula for this?