Sixteen Times The Misses

An int A[4000][4000] (64 MB, far larger than any cache) is summed twice: once row by row, once column by column. Cache lines are 64 bytes, int is 4 bytes, and the hardware prefetcher is disabled.

How many cache misses does each traversal cost?

62,500 row-major and 1,000,000 column-major.

1,000,000 row-major and 16,000,000 column-major.

16,000,000 both ways: the same 16 million elements get read either way.

1,000,000 row-major and 4,000,000 column-major.