23. Cache-Oblivious Algorithms: Medians & Matrices

What this lecture covers

This lecture opens a two-part unit on cache-oblivious algorithms by asking why counting operations alone, as earlier lectures did, ignores an important real-world cost: not all memory accesses are equally fast. It builds up the two-level "external memory" model (cache versus disk, with block size B and cache size M), then introduces the cache-oblivious variant, where the algorithm doesn't know B or M but is still analyzed with respect to them. It then applies this model to three algorithms: array scanning, the linear-time median-finding algorithm from earlier in the course, and divide-and-conquer matrix multiplication.

The lecture sits at the start of the course's final unit. After watching, you should be able to explain why block size matters for algorithm performance, analyze an algorithm's number of memory transfers as a function of B and M, and understand why a cache-oblivious divide-and-conquer layout for matrix multiplication beats the standard triple-loop algorithm by a large factor.

Key ideas

• Memory hierarchy: real computers have several progressively larger and slower levels (CPU registers, multiple cache levels, RAM, flash, disk), unlike the earlier assumption that every memory access costs the same.
• Latency vs. bandwidth: latency (time to start a transfer) can't be reduced, but bandwidth (data rate) can be scaled up; blocking amortizes latency across many words by fetching a whole block at once.
• External memory model: analyzes two levels at a time (a small fast "cache" of size M, divided into blocks of size B, and a huge slow "disk"), counting only the number of block transfers between them.
• Cache-oblivious model: the same two-level accounting, but the algorithm itself is not allowed to know B or M; it must work well for all possible values simultaneously, which (per Frigo, Leiserson, Prokop, and Ramachandran's 1999 result) implicitly optimizes across the entire memory hierarchy at once.
• Spatial and temporal locality: cache efficiency requires that a fetched block's other elements get used (spatial locality) and that cached blocks get reused before eviction (temporal locality).
• Scanning: reading an array in order costs about O(n/B) memory transfers, since each block, once fetched, serves several consecutive accesses for free; a constant number of parallel scans (e.g. reversing an array with two pointers) costs the same.
• Cache-oblivious divide and conquer: the algorithm recurses all the way to constant size as usual, but the analysis picks a convenient base case - either "fits in O(1) blocks" or "fits in cache" - to bound memory transfers, and requires that recursive subarrays be stored contiguously in memory.
• Divide-and-conquer matrix multiplication: recursively splitting matrices into quadrants (as in Strassen's algorithm) and laying each submatrix out contiguously in memory reduces memory transfers from Theta(n^3/B) for the standard algorithm to Theta(n^3/(B*sqrt(M))), a large improvement once M is large.

Walkthrough

Why memory access isn't free (1:00)

The lecture motivates the whole unit by pointing out that every algorithm covered so far assumed uniform-cost memory access, which is unrealistic: real computers have a memory hierarchy from on-chip caches through RAM, flash, and disk, each level bigger and slower than the last. It distinguishes latency (fixed, can't be reduced) from bandwidth (can be scaled by adding more parallel channels), and explains that blocking - fetching a whole chunk of nearby data on each access - amortizes latency, provided algorithms are structured to actually use the extra data they fetch.

The external memory model (13:16)

The lecture formalizes a two-level model: a cache of total size M, divided into blocks of B words, connected by a slow link to an effectively infinite disk, also divided into B-word blocks. The cost measure is the number of block transfers ("memory transfers") between the two levels; ordinary CPU computation within the cache is treated as free. In this model, algorithms explicitly choose which blocks to read and evict.

The cache-oblivious model (21:29)

The lecture introduces the twist that gives the unit its name: the algorithm is not told B or M, so block reads and evictions happen automatically (as they do on real hardware), and the algorithm must perform well for every possible B and M simultaneously. This is harder to design for but has real advantages - ordinary pseudocode works without explicit block management, the same code adapts to any machine's actual cache sizes, and, by a cited 1999 result, an algorithm optimal in this two-level model is provably near-optimal across the entire real memory hierarchy at once. The lecture also notes that eviction strategy (LRU, FIFO, or random) doesn't much matter for the bounds that follow.

Scanning and parallel scanning (32:36)

As a first, easy example, scanning a contiguous array to accumulate a sum costs about n/B memory transfers, since only the first access into each block is expensive. A constant number of simultaneous scans, illustrated with an in-place array-reversal algorithm using two pointers moving toward each other, costs the same O(n/B) as long as the cache holds at least that many blocks.

Cache-oblivious median finding (40:02)

The lecture revisits the linear-time worst-case median-finding algorithm (partition into groups of five, recursively find the median of medians, partition around it, recurse on one side) and reanalyzes it for memory transfers. The key change needed is ensuring that the array of column medians is written out contiguously, so the recursive call operates on a contiguous subarray rather than a strided one. Solving the resulting recurrence with the naive constant-size base case gives a disappointing sublinear-but-not-good-enough bound; switching to a stronger base case - stopping the analysis once a subproblem fits in O(1) blocks - gives the desired O(n/B + 1) bound, matching the cost of simply reading the input once.

Divide-and-conquer matrix multiplication (1:01:38)

For the standard triple-loop matrix multiplication (storing one matrix row-major and the other column-major), the lecture shows a cost of Theta(n^3/B) memory transfers, since a new column has to be re-fetched for nearly every cell computed, unless the cache can hold an entire matrix. The lecture then applies divide-and-conquer: split each matrix into quadrants, recursively multiply and add eight submatrix products (as in the standard recursive formula, not yet Strassen's faster variant), and crucially store each submatrix recursively as a contiguous block in memory. Using the base case "stop recursing once three submatrices fit in cache," the recurrence solves to Theta(n^3/(B*sqrt(M))), a substantial improvement over the standard algorithm whenever the cache is reasonably large - because the algorithm reuses rows and columns many times instead of re-reading them.

Before you watch

• Review the linear-time median-finding (median of medians) algorithm from earlier in the course, since this lecture directly reanalyzes it rather than re-deriving it from scratch.
• Recall how Strassen's algorithm applies divide and conquer to matrix multiplication, since this lecture reuses that recursive block structure.
• Basic comfort solving recurrences (as with the master method) helps follow the derivation of the memory-transfer bounds.

Check your understanding

1. Why does an algorithm need to guarantee spatial and temporal locality for blocking to actually reduce cost?
2. What is the key difference between the external memory model and the cache-oblivious model, and why does the cache-oblivious version need automatic block management?
3. Why did the naive constant-size base case give a poor bound for cache-oblivious median finding, and how did switching the base case fix it?
4. Why does storing matrix quadrants contiguously in memory matter for the divide-and-conquer matrix multiplication algorithm's memory-transfer bound?