A CPU has a 32 KB direct mapped cache with 128 byte block size. Suppose A is a two dimensional array of size 512 x 512 w...

Question

A CPU has a 32 KB direct mapped cache with 128 byte block size. Suppose A is a two dimensional array of size 512 x 512 with elements that occupy 8 bytes each. Consider the following two code segments P1 and P2:

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

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

P1 and P2 are executed independently with the same initial state, namely A is not in the cache and i, j are in registers. Let the number of cache misses experienced by P1 be M1 and that by P2 be M2. The value of M1/M2 is:

A. 0
B. 1/16
C. 1/4
D. 16

Accepted Answer

M1/M2 = 1/16. Answer: B. 1/16 We have a 32KB direct-mapped cache with 128-byte blocks. The array A is 512x512 of 8-byte doubles, totalling 2MB. P1 traverses A row by row (sequential memory order) while P2 traverses column by column (strided memory order). Because a cache block holds 16 elements (128/8), row-major access gets 16 hits after each miss, whereas column-major access strides 4096 bytes between consecutive accesses, causing almost every access to be a cache miss.