Locality

• Spatial Locality: accessing data items that are close together in memory (i.e., consecutive elements in an array)
  • Caches exploit this by loading entire blocks of memory at once
• Temporal Locality: re-accessing the same data items within a short time period
  • Caches exploit this by keeping recently used data readily available

Goal is to write code that has high locality to minimize cache misses

Cache Basics and Array Access Patterns

Factors Influencing Miss Rate

• Elements per Block: how many data items fit into a cache block (i.e., 2 integers per 8B block)
• Data Structure Size: does the entire data structure fit in the cache?
• Access Order: are you accessing data in row-major order (good for spatial locality, or column-major order (bad for spatial locality)

Access Pattern Examples

• Sequential Access (1D Array): 50% miss rate, half the accesses will be to new block
• Row-rise 2D Access: 50% miss rate, good spatial locality as you traverse contiguous memory
• Column-wise 2D Access:
  • If the column fits in the cache, 50% miss rate (after initial load)
  • If the column does not fit in the cache, 100% miss rate
    • Every access is to a different, non-contiguous memory location, causing a constant stream of cache misses
    • This is the worst-case scenario

Loop Reordering (Interchange)

• Problem: the naive code for a 2D operation (like initializing an array) might use a column-major inner loop, leading to a 100% miss rate
• Solution:

Matrix Multiplication

• Problem: the naive i, j, k loop structure has poor locality for matrix B because the inner loop k strides through memory in a non-contiguous way B[k][j] .

Tiling (Blocking)