Exactly Thirty Two Kilobytes

A machine has one 32 KB L1 data cache: 8-way set associative, 64-byte lines, LRU. Nothing else competes for it.

64 sets of 64-byte lines consume the low 12 address bits tag set index (6 bits) offset (6 bits) bits 63..12 bits 11..6 bits 5..0

A double a[64][64] is allocated at a 4096-byte aligned address, so the whole array is exactly 32 KB. It is traversed column by column:

double s = 0.0;
for (int j = 0; j < 64; j++)
    for (int i = 0; i < 64; i++)
        s += a[i][j];

s, i and j live in registers. How many L1d misses does this loop take?

A

64

B

512

C

4096, one per access: a column walk has no spatial locality

D

3584