mediumCS:APP Cache Lab#spatial-locality#cache-simulation

Measure Cache Locality in a Matrix Walk

Compare row-wise and column-wise matrix traversal and connect address order to cache-line reuse and measured misses.

The Runtime Theory TeamSeptember 25, 20261 min read

Solve it

Solving happens on the judge — come back and mark it done

Sample cases

inrow-major 1024x1024 traversal; visit each element once

outSequential inner-loop addresses; compare measured misses with column traversal

incolumn-major traversal over the same row-major matrix

outLarge strides; explain cache-line underuse and verify with a simulator or counters

Write two loops that sum every element in the same row-major matrix: one with columns in the inner loop and one with rows in the inner loop. Keep the work and data identical so the access order is the main variable.

Predict which version reuses each fetched cache line more effectively. Then measure both with repeated runs and, if available, cache counters or the linked CS:APP Cache Lab. Record the machine, compiler, optimization flags, matrix size, and measurement method. Do not present one result as a universal speed ratio.

As a follow-up, tile the matrix so a small block stays in cache while both dimensions are traversed. Explain why the best tile size depends on the cache hierarchy and other active data.

One dispatch a week

The trace behind each problem, the tradeoff that explains it, and one technical dispatch per week — no noise.

One technical dispatch per week. No noise.

Not started