Loop Optimization for Cache Memory
1. Why Cache Matters
CPU is 10-100× faster than RAM; cache misses stall. Loops over arrays dominate misses. Compiler restructures loops to maximize temporal (reuse soon) and spatial (use neighbours) locality.
2. Techniques (exam list)
| Opt | Idea | Example |
|---|---|---|
| Blocking/tiling | chunk loops to fit cache | i,j,k → ii,jj,kk tiles of 32 for matmul |
| Interchange | swap nest for stride-1 access | a[i][j] row-major: j-inner (C), i-inner is 8× slower |
| Fusion | merge loops same range | two passes over a → one (halves misses) |
| Unrolling + scalar replacement | keep reused in regs | s+=a[i] unrolled ×4 keeps 4 in regs |
3. Worked — interchange (C row-major)
slow (stride N): for i for j sum += a[j][i] // jumps rows, miss per access
fast (stride 1): for i for j sum += a[i][j] // sequential, 1 miss per 8-16 elems
Tiling matmul C=AxB 512³: naive 100M misses → tiled 32³ ≈ 10× fewer.
4. Safety
Needs dependence check (interchange legal only if no carried dependence reversed); profitability via cache model / profiling.
5. Exam Points
- List tiling/interchange/fusion with example — 7 marks, very frequent.
- Row-major stride trap — 5 marks, frequent.
- Temporal vs spatial locality — 3 marks, frequent.