10 / 17 Caching

Sixteen Times The Traffic

a is a 4096 by 4096 array of 4-byte ints, so 64 MiB, far larger than the 8 MB L3. Lines are 64 bytes and the array is row-major.

/* A */                          /* B */
for (int i = 0; i < N; i++)      for (int j = 0; j < N; j++)
  for (int j = 0; j < N; j++)      for (int i = 0; i < N; i++)
    sum += a[i][j];                  sum += a[i][j];

Which statement is correct?

A

They differ only in temporal locality on sum, which both hit on every iteration, so the miss counts are within a few percent.

B

Both read the same 64 MiB, so both fetch the same number of lines; only the order changes.

C

A fetches about 1.05 million lines and uses all 16 ints in each. B touches a new line on nearly every access, about 16 times the traffic, because a column walk has no spatial locality in a row-major array.

D

B is faster: holding i in the inner loop keeps the row index in a register and removes a multiply from the address computation.