Cache Locality Visualizer
A matrix is stored as one long run of memory addresses in row-major order. A CPU cache loads that memory in fixed size blocks called cache lines. Walk the matrix one access at a time and watch the cache fill with green hits and red misses. Compare row-major and column-major traversal to see why reading data the way it is laid out in memory is so much faster.
Guided Experiment: Why is row-major traversal faster, and when does column-major catch up?
Predict how the cache hit rate will differ between row-major and column-major traversal of the same matrix when the cache is small. Then predict what happens to the gap as you make the cache larger.
Write your hypothesis in the Lab Report panel, then click Next.
Full traversal comparison
Cache hit rate for walking the entire matrix the same way it is stored in memory versus across the grain, at the current settings.
Row-major traversal matches how the matrix is laid out in memory, so it reuses each cache line and hits far more often. Column-major traversal strides a full row between accesses, so it keeps loading new lines and a small cache evicts them before they are reused.
Matrix in memory (row-major)
Each cell shows its memory address. Row-major storage lays addresses out left to right, top to bottom, so consecutive addresses are neighbors in a row.
Cache lines (MRU left to right)
Run readout
Press Run to step through the access trace and watch hits and misses accumulate, or use Step to advance one access at a time. The final hit rate and estimated cost appear here when the run completes.
Controls
A larger cache line pulls in more neighboring words on each miss, so sequential access reuses it more. A larger cache holds more lines before it has to evict, which helps strided access stop thrashing.
What to watch
- In row-major mode the green hits cluster along each row because neighboring addresses share a cache line.
- In column-major mode the cache fills with red misses because each step jumps a whole row of N words to a new line.
- Raise the cache size until column-major can keep enough lines resident to start hitting again.
- A larger cache line size raises the row-major hit rate toward (lineSize minus 1) divided by lineSize on a cold walk.
Data Table
(0 rows)| # | N | Line size(words) | Cache lines | Pattern | Hit rate(%) | Misses | Est. cost(cycles) |
|---|
Reference Guide
Caches and Cache Lines
Main memory is slow compared with the processor, so a small fast cache sits between them. When the processor reads an address that is already in the cache it is a hit, which is cheap. When the address is missing it is a miss, which stalls the processor while the data is fetched from main memory.
A cache does not store single words. It stores fixed size blocks called cache lines. When a miss happens the whole line is loaded, so the words sitting next to the one you asked for come along for free.
Spatial and Temporal Locality
Spatial locality means that if a program uses one address it is likely to use nearby addresses soon. Because a miss loads a full line, accessing neighbors turns the next few reads into hits.
Temporal locality means that if a program uses an address it is likely to use that same address again soon. A cache that holds recently used lines serves those repeat reads quickly. This lab focuses on spatial locality through the matrix traversal order.
Row-Major Layout and Traversal Order
In row-major storage the element at row r and column c sits at address r times N plus c. The whole first row comes first, then the second row, and so on. Consecutive addresses are neighbors within a row.
Row-major traversal reads addresses 0, 1, 2 and so on, so it stays inside each cache line and reuses it. Column-major traversal reads addresses that are a full row of N words apart, so every step jumps to a new line and a small cache thrashes, evicting lines before they are reused.
LRU Replacement and Real Performance
When the cache is full and a new line must load, something has to go. A least recently used policy evicts the line that has gone longest without an access, betting that recently used lines will be needed again soonest.
A real cache miss can cost tens to hundreds of processor cycles, while a hit costs about one. The estimated cost in this lab uses one cycle per hit and ten per miss as a simple proxy, which is why the column-major run can be many times slower than the row-major run even though both touch the same data.
