14. Caching and Cache-Efficient Algorithms

What this lecture covers

Building on an earlier introduction to caching, this lecture asks how to design algorithms that use the cache hierarchy well rather than fighting it. It covers how real caches are organized (fully associative, direct-mapped, and set-associative), the different kinds of cache misses, and a theoretical tool called the ideal-cache model that lets you analyze an algorithm's cache complexity independently of any particular machine.

The lecture then applies that model to matrix multiplication: it shows why the naive triple-loop version wastes locality, how loop reordering and tiling fix that at the cost of a machine-specific tuning parameter, and how a cache-oblivious divide-and-conquer algorithm gets the same asymptotic cache performance without any tuning at all, in both the serial and parallel settings.

Key ideas

• Cache associativity: fully associative caches let a block go anywhere (slow to search, no conflict misses); direct-mapped caches give each block exactly one slot (fast, but prone to conflict misses); set-associative caches are the practical middle ground used on real hardware.
• Taxonomy of misses: cold misses (first access), capacity misses (cache too small), conflict misses (too many blocks map to the same set), and sharing misses (true or false sharing between processors' caches).
• Ideal-cache model: a two-level, fully-associative cache with optimal offline replacement, used to bound an algorithm's work and cache misses independent of real hardware quirks.
• LRU lemma: an algorithm's cache-miss count under LRU on a cache of size 2M is within a constant factor of its miss count under the optimal policy on a cache of size M, so analysis can assume whichever policy is convenient.
• Tall-cache assumption: real caches satisfy B^2 <= cM, meaning a cache holds more lines than a line is wide; this rules out pathological "short cache" cases when reasoning about sub-matrices.
• Cache-aware vs. cache-oblivious: tiled matrix multiply is cache-aware, tuned to a "voodoo parameter" sized to the cache; the recursive divide-and-conquer version is cache-oblivious, achieving the same Theta(n^3 / (B * sqrt(M))) miss bound automatically, at any cache size and level.
• Parallel cache bound: for a Cilk computation, parallel cache misses equal the serial miss count plus O(steals * M/B), so minimizing span (which bounds the number of steals) keeps parallel cache performance close to serial.

Walkthrough

Cache hardware and associativity (0:01)

The lecture surveys the multicore cache hierarchy (private L1/L2, shared L3, DRAM) with real latency and size numbers, then works through fully associative, direct-mapped, and set-associative cache designs, showing how a virtual address splits into tag, set, and offset bits under each scheme and what each design trades off in search cost versus conflict misses.

Types of cache misses and a conflict-miss example (14:17)

The lecture defines cold, capacity, conflict, and (true/false) sharing misses, then walks a concrete example: accessing a column of a 32x32 sub-matrix inside a much larger row-major matrix produces addresses that all land in the same cache set, evicting each other on a 4-way associative cache. Padding rows by a small constant, or copying the sub-matrix into temporary contiguous storage, avoids this.

The ideal-cache model and key lemmas (26:41)

The lecture introduces the ideal-cache model (size M, line size B, optimal replacement), the LRU lemma, a general cache-miss lemma bounding misses on R variable-length data segments, and the tall-cache assumption, culminating in the sub-matrix caching lemma: an n x n sub-matrix that fits in a tall cache costs at most 3n^2/B misses to read.

Analyzing naive matrix multiply (42:10)

Working through the standard triple-loop i, j, k matrix multiply, the lecture derives cache-miss counts for matrix B in three regimes of n relative to M and B, showing the naive loop order incurs Theta(n^3) misses, on par with the total work, because it gets no reuse. Swapping the two inner loops (an optimization from the very first lecture of the course) improves this to Theta(n^3/B) by exploiting row-major spatial locality.

Tiled matrix multiply (53:31)

Splitting the computation into s x s tiles sized so three tiles fit in cache (s = Theta(sqrt(M))) preserves the Theta(n^3) work while cutting cache misses to Theta(n^3 / (B * sqrt(M))), a factor-of-sqrt(M) improvement, at the cost of a hardware-specific tuning parameter that hurts portability and multi-level, multi-program tuning.

Cache-oblivious recursive matrix multiply (1:01:42)

The lecture returns to the divide-and-conquer matrix multiply from earlier in the course (eight recursive sub-problems, or four with sub-computations summed), derives its Theta(n^3) work via a recursion tree, and then derives its cache complexity with a base case defined by fitting in cache rather than by constant size. The result matches the tiled version's Theta(n^3 / (B * sqrt(M))) bound with no explicit tuning, at any cache size or level, which is what makes it "cache-oblivious."

Parallel cache complexity (1:13:55)

Using a theorem relating parallel and serial cache misses through the number of successful steals (Q_P = Q_1 + O(steals * M/B)), and the bound that steals are O(P * span), the lecture shows the parallel recursive matrix multiply retains essentially the same cache bound as the serial version, provided the algorithm's span stays low.

Before you watch

• Review the earlier lecture's introduction to caching, cache coherence, and the recursive (divide-and-conquer) matrix multiplication code.
• Be comfortable with the master theorem and recursion-tree analysis for solving work recurrences.
• Recall Cilk's work-stealing model, work, and span from prior lectures, since the parallel section builds directly on them.

Check your understanding

1. Why does a direct-mapped cache suffer conflict misses that a fully associative cache of the same size would not?
2. Using the sub-matrix caching lemma, explain why an n x n matrix that fits in a tall cache costs Theta(n^2/B) misses to read.
3. Why does swapping the two inner loops of the naive matrix multiply reduce its cache misses from Theta(n^3) to Theta(n^3/B)?
4. What is a "voodoo parameter," and why does the cache-oblivious algorithm avoid needing one?
5. How does the number of successful steals bound the extra cache misses incurred when a Cilk computation runs in parallel rather than serially?