Real Memory Hierarchies, Cache Blocking, and Chapter Five's Lessons

Real Stuff: Memory Hierarchies in Commercial Processors

Real processors implement the caching and memory concepts covered throughout this chapter with specific, carefully chosen parameters. Both the ARM Cortex-A53 and Intel Core i7, discussed earlier in this series regarding pipeline design, also differ meaningfully in their memory hierarchies: mobile-oriented designs like the Cortex-A53 typically use smaller cache sizes at each level to conserve power and die area, while performance-oriented designs like the Core i7 use larger, multi-level caches, often three levels deep, to minimize average memory access time at the cost of additional power and chip area.

Applying Cache Concepts: Cache Blocking for Matrix Multiply

Matrix multiplication, discussed earlier in this series regarding subword parallelism and instruction-level parallelism, can also be optimized specifically for the memory hierarchy using a technique called Cache Blocking (also called Tiling). Rather than processing an entire large matrix row by row, which can repeatedly evict useful cached data due to capacity misses discussed earlier in this series, the matrix is divided into smaller sub-blocks sized specifically to fit within the cache.

Without blocking:
Large matrix accessed row-by-row,
repeatedly evicting data still needed later,
causing many capacity misses

With blocking:
Matrix divided into smaller sub-blocks
that fit entirely within the cache,
each sub-block fully processed
before moving to the next

By ensuring each sub-block's data remains in the cache throughout its processing, cache blocking significantly reduces the number of capacity misses, directly applying the locality principles introduced earlier in this series to a real, widely used computational workload.

Common Fallacies About Memory Hierarchies

• Assuming a larger cache is always better — as discussed earlier regarding cache performance tradeoffs, a larger cache increases hit time and cost even as it reduces capacity misses.
• Assuming virtual memory and caching are unrelated systems — as shown earlier in the unified framework covering block placement, identification, replacement, and write policy, they answer the exact same underlying questions.
• Assuming a cache miss always costs the same amount of time — as discussed earlier regarding the three types of misses, the actual cost depends heavily on which level of the memory hierarchy must ultimately satisfy the request.

Common Pitfalls in Memory-Sensitive Code

• Writing code with poor spatial locality, such as accessing array elements in a non-sequential pattern, which defeats the benefit of the block-based caching discussed earlier in this series.
• Ignoring the load-use hazard discussed earlier in this series when reasoning about why memory-heavy code sometimes performs worse than expected despite a seemingly efficient algorithm.
• Overlooking multicore cache coherence overhead, discussed earlier in this series, when writing parallel code that frequently modifies shared data across cores.

Chapter Summary: The Full Memory Hierarchy Picture

This chapter traced the path from the smallest and fastest storage to the largest and slowest: SRAM-based caches exploiting locality of reference, virtual memory providing both illusion of abundant memory and process isolation, dependable memory techniques protecting against silent data corruption, cache coherence keeping multicore systems consistent, and RAID protecting persistent storage against physical disk failure. Every one of these mechanisms exists because no single memory technology can be simultaneously fast, large, cheap, and reliable — a theme first introduced at the very start of this chapter and echoed in every technique built on top of it.