A common mistake is treating a cache as one undivided pool. Cache partitioning divides a cache into sets, and each memory block can occupy only the set selected by its address. This makes placement faster than searching every cache line, but repeated addresses mapping to one set can evict one another. section 12.1.5
A reduced cache model makes the placement rule concrete:
- Use a 512-byte cache with eight cache lines and a two-way set-associative policy; each set therefore contains two lines. section 12.1.5
- Treat each 64-byte memory block as containing eight int64 values, so the cache fetches blocks rather than individual words. section 12.1.5 section 12.11
- Derive the destination set from the memory address; addresses 0x0000000000000 and 0100000000000 both map to set 0 in the illustrated execution. section 12.1.5
- Recognize the conflict when a third block maps to that same two-line set: address 1000000000000 replaces an existing cache line. section 12.1.5
When a stride wastes the cache
A matrix example reads the first eight columns while skipping the remaining columns. If successive accesses repeatedly select a small number of cache sets, the program uses only a fraction of the cache and can suffer from a critical stride. Organizing accesses for spatial locality helps use each fetched cache line more effectively. section 12.1.5 section 12.11
func calculateSum512(s [][512]int64) int64 { #1
var sum int64
for i := 0; i < len(s); i++ {
for j := 0; j < 8; j++ {
sum += s[i][j]
}
}
return sum
}
func calculateSum513(s [][513]int64) int64 { #2
// Same implementation as calculateSum512
}
Compare the 512-element and 513-element array layouts while tracing the same summation loop; the listing provides the concrete Go setup for investigating stride and cache placement. section 12.1.5
