Cache-Oblivious Algorithms: Optimal I/O Without Knowing the Cache

Every blocked matrix multiply, every B-tree, every tile size in every tuned BLAS library is making a quiet bet: the programmer knows two numbers, the cache size and the cache-line length, and hard-codes them into the algorithm. In 1999 Frigo, Leiserson, Prokop, and Ramachandran asked what happens if the algorithm is forbidden to know either number, and answered with a series of results that still look slightly unreasonable: sorting, matrix multiplication, matrix transpose, FFT, and static search can all be made I/O-optimal on every cache size and line length simultaneously, by algorithms whose code contains no hardware parameters at all [1]. They called such algorithms cache-oblivious, and the ideal-cache model they introduced is the two-level, cache-aware half of the external-memory story told in the Ch 159 chapter - same I/O accounting, but with the tuning knobs deliberately removed.

The payoff is portability with a proof attached. A cache-oblivious algorithm is written once and is asymptotically optimal on whatever hierarchy it meets: an L1 with 32-byte lines, an L3 shared with noisy co-tenants, a VM whose effective cache size depends on the neighbor’s workload, a database buffer pool with an arbitrary page size. This page walks the model and its two simulation theorems (LRU replacement and multi-level hierarchies), the elementary miss bounds for scanning and binary search, the van Emde Boas layout that lets a static tree match B-tree search without knowing the block size, funnelsort’s recursive merge, the recursive matrix algorithms that match tuned blocking, a block-level simulation comparing in-order and vEB layouts, and the honest limits - because cache-obliviousness is a trade-off with known boundaries, not magic.

Cache-aware vs cache-oblivious: what the code may ask about the machine

The definition is about tunable parameters, not awareness in a colloquial sense. The Frigo et al. paper defines an algorithm as cache aware if it contains parameters, set at compile time or runtime, that can be tuned to optimize the cache complexity for the particular cache size and line length; otherwise it is cache oblivious [1]. Three consequences follow immediately. First, a plain iterative mergesort written in 1950 is cache-oblivious under this definition - obliviousness is a property of the code’s interface to the machine, and it takes analysis to know whether an oblivious algorithm is also good. Second, cache-awareness is a spectrum: a blocked multiply with one tile parameter s is aware, and one with separate s, t, u per cache level is more aware still, which is exactly why three-level tuning needs three “voodoo” parameters and twelve nested loops in the MIT lecture version of the same story [10]. Third, the definition makes optimality claims comparable: for each problem we can ask whether the oblivious bound matches the tuned bound, and for the algorithms below it does.

The practical stake is that the two numbers every cache-aware algorithm needs are exactly the two numbers a modern runtime is least willing to reveal. A shared L3 is depleted by co-tenant jobs; a virtual machine migrates; a NumPy array may be traversed through a buffer pool whose page size is a database setting; an embedded part ships into three SKUs with different L2s. A cache-aware kernel tuned on the benchmark machine mistunes silently on all of these, while an oblivious algorithm degrades the way its asymptotic bound degrades. The theorems in the next section are what turn that hand-wave into a statement with hypotheses you can check.

The ideal-cache model

The model is a two-level machine with three deliberate idealizations. The cache holds Z words partitioned into cache lines of L consecutive words that always move together between cache and memory; it is fully associative, so a line can sit anywhere; and it replaces lines by the optimal offline strategy, evicting the line whose next use is furthest in the future [1]. Algorithms are charged two costs: the usual RAM work W(n), and the cache complexity Q(n; Z, L) - the number of lines moved. The one substantive regularity assumption is the tall cache Z = Omega(L^2), which the paper justifies as “usually true in practice” and which is needed mainly so that two-dimensional row-major data has lines as long as the sub-rows it wants to touch.

        CPU
         |  references one word at a time
         v
  +---------------------------+
  | ideal cache: Z words      |   fully associative
  | = Z/L lines of L words    |   optimal replacement (Belady):
  +---------------------------+   evict line used furthest in future
         | whole lines of L consecutive words move as a unit
         v
  +---------------------------+
  | main memory               |
  +---------------------------+

  charge per algorithm:  W(n)        RAM work (operations)
                         Q(n; Z, L)  cache misses (line transfers)
  tall cache:  Z = Omega(L^2)   e.g. 512 lines x 16 words = 8192 words

The optimal-replacement assumption is defensible because of a simulation lemma the paper proves from Sleator and Tarjan’s competitive analysis: an algorithm that incurs Q*(n; Z/2, L) misses on an ideal cache incurs at most 2 Q*(n; Z/2, L) misses on a (Z, L) cache run with LRU, and whenever the bound satisfies the mild regularity condition Q(n; Z, L) = O(Q(n; 2Z, L)) - true of every bound on this page - LRU misses are Theta(Q(n; Z, L)) [1]. So optimal replacement costs at most a factor of 2 in the analysis and usually nothing asymptotically, and every ideal-cache bound below transfers to the LRU caches that actually ship.

Three prices: scan, binary search, and the layout that fixes search

Scanning n contiguous elements costs Theta(1 + n/L) misses and could not cost less, since the elements occupy at least ceiling(n/L) distinct lines; contiguous access is the one pattern where naive code is already optimal, oblivious or not. Binary search on a sorted array is the instructive failure. Each of its lg n probes lands where it must - half the remaining window each time - and the probes are unrelated by line until the window shrinks to L elements, after which all remaining probes share one line: Theta(lg n - lg L) misses, a bound Demaine states as Theorem 3 in his survey [4]. The gap to optimal is a factor of about lg L, because the information-theoretic floor is lg(n+1) bits of answer at lg(L+1) bits revealed per line touched, i.e. Omega(log(n+1)/log(L+1)) misses [5].

Prokop’s static search trees close the gap with a memory layout, which is why they are the canonical first cache-oblivious data structure: search cost O(log_L n) misses, matching the B-tree search that is handed L explicitly, without the code ever containing L [2], [3]. The construction lays out a complete binary tree recursively, splitting at the middle level of edges: lay out the top subtree, then each of the roughly sqrt(n) bottom subtrees, each of size roughly sqrt(n) [4]. Demaine’s survey also records the boundary of the idea: a lower bound of log2 e · log_L n ~ 1.44 log_L n misses holds for every cache-oblivious search, so the layout pays one constant factor against a cache-aware B-tree and no layout can do better [3].

  height-4 tree, 31 nodes, keys are the in-order ranks 1..31
  (BST property: every left subtree holds the smaller keys)

              16                    top part: depths 0-1, 3 nodes
            /    \
           8      24
          / \    /  \
         4  12 20  28              4 bottom subtrees, 7 nodes each
        /\  /\  /\  /\             (roots 4, 12, 20, 28 at depth 2)
       1  2..7 ...                 each splits again at its middle level

  vEB memory order:
    [16, 8, 24] | [4, 2, 1, 3, 6, 5, 7] | [12, ...] | [20, ...] | [28, ...]
     top part      bottom 1               bottom 2    bottom 3    bottom 4

  search for 1: probes 16, 8, 4, 2, 1 -> vEB lines {0, 1} at L = 4: 2 misses
  same search, in-order layout: probes land on lines {3, 1, 0}: 3 misses

The search walk touches at most two subtrees per split level, and once a subtree of height h fits in one line the rest of the walk is free, giving the log_L n bound; comparisons stay lg n, so the layout buys I/O optimality at zero asymptotic work overhead. The demo below runs exactly this height-4 example with L = 4 and counts lines by hand.

Funnelsort: the merge that refuses to know Z

Sorting is where obliviousness gets hard, because mergesort’s natural recursion - merge two halves - produces merges whose working sets are the wrong size. Funnelsort keeps the merge-tree idea but restructures the merge itself [1]. To sort n elements: split the input into n^(1/3) contiguous arrays of n^(2/3) elements, sort each recursively, then merge the n^(1/3) sorted sequences with an n^(1/3)-merger. A k-merger is built recursively out of sqrt(k) “left” k-mergers whose outputs feed buffers, each holding 2k^(3/2) elements, whose outputs feed one “right” k-merger; each invocation of a k-merger outputs the next k^(3/2) elements of the merged sequence, and before each invocation of the right merger the buffers less than half full are topped up by invoking their left mergers. The buffer sizing is the whole trick: it decouples the merge’s working set from its output length so that only one active merge is ever memory-resident, and the invocation discipline keeps every buffer pass amortized against the elements it produces.

The paper proves Theta(n lg n) work and Theorem 7’s cache bound of O(1 + (n/L)(1 + log_Z n)) misses, which it shows is cache-optimal against the Aggarwal-Vitter sorting lower bound Theta((n/L) log_{Z/L}(n/L)) [1], [8] - the same bound the cache-aware external mergesort of the Ch 159 chapter reaches by picking its fan-out from M and B directly. Later work simplified the construction (Lazy Funnelsort, which fills buffers lazily) and mapped the design space: Brodal and Fagerberg proved that no cache-oblivious comparison sort is I/O-optimal without a tall-cache assumption, and that funnelsort and plain binary mergesort sit on the optimal frontier of the resulting trade-off between assumption strength and overhead when Z is much larger than L [3], [7]. The dynamic-dictionary side of the same program is the cache-oblivious B-tree of Bender, Demaine, and Farach-Colton: searches and amortized updates in O(log_L n) misses, built on the static vEB layout plus list labeling [6]. Funnelsort’s merge tree is also a parallel merge structure, which is why the same diagram reappears in parallel sorting with span instead of misses as the second cost.

Matrix algorithms with zero tuning parameters

Matrix multiply is the canonical cache-aware algorithm: BLOCK-MULT tiles n x n matrices into s x s blocks and chooses s as the largest value with three s x s blocks resident, which the tall-cache assumption prices at s = Theta(sqrt(Z)) - a hardware parameter, hard-coded [1]. The oblivious alternative REC-MULT simply halves the largest of the three matrix dimensions and recurses, no parameters: it does Theta(mnp) work and incurs Theta(m + n + p + (mn + np + mp)/L + mnp/(L sqrt(Z))) misses. For square matrices that is Theta(n + n^2/L + n^3/(L sqrt(Z))), which the paper notes is the same cache complexity as the cache-aware BLOCK-MULT and matches the Hong-Kung lower bound for algorithms that perform the Theta(n^3) scalar operations. The recursive transpose is even cleaner: O(mn) work and Theta(1 + mn/L) misses, optimal, against Theta(mn) misses for the naive nested loops when both dimensions are large [1].

Strassen belongs in this table as a bonus: the paper observes that Strassen’s algorithm, itself a parameter-free recursion, incurs Theta(n + n^2/L + n^(lg 7)/(L sqrt(Z))) misses, so the asymptotically faster algebra is automatically cache-optimal too [1]. The general lesson for matrix algorithms is that divide-and-conquer over the largest dimension makes blocking emerge on its own at every scale, which is why the same recursion pattern reappears in the cache-oblivious summaries of parallel graph algorithms - recursion is the one blocking schedule that is correct for all (Z, L) at once.

The demo: counting misses on a height-4 tree

The simulation is deliberately literal. The tree is complete with height 4 and 31 nodes; keys are the in-order ranks 1..31, so descending the tree is binary search on the sorted array. A cache line holds L = 4 keys. A search pays one miss per distinct line it touches, starting cold, which is the correct accounting for a single search in an ideal cache that had none of it resident. The in-order layout stores key k at position k - 1; the vEB layout stores keys in the recursive order defined above. Ten fixed search keys span the root, the extremes, and the deep interior.

# Cache-oblivious vs cache-aware layout: static BST search miss counts.
# Complete binary tree of height H = 4 (31 nodes); keys are the in-order
# ranks 1..31, so searching the tree IS binary search on the sorted array.
# Cache lines hold L = 4 keys. A search pays one miss per distinct line it
# touches (cold start), so the memory layout alone decides the miss count.
import math

H, L = 4, 4
N = 2 ** (H + 1) - 1                      # 31 nodes

key = {}                                  # heap index -> in-order rank
def label(i):
    if i <= N:
        label(2 * i)
        key[i] = len(key) + 1             # left subtree, then me, then right
        label(2 * i + 1)
label(1)

def preorder_upto(i, dmax, d=0):          # heap indices at depths 0..dmax
    return [i] + ([] if d == dmax else
                 preorder_upto(2 * i, dmax, d + 1) +
                 preorder_upto(2 * i + 1, dmax, d + 1))

def depth_nodes(i, want, d=0):            # heap indices at exactly depth want
    if d == want:
        return [i]
    return depth_nodes(2 * i, want, d + 1) + depth_nodes(2 * i + 1, want, d + 1)

def veb(i, h):
    """vEB memory order (heap indices) of the subtree rooted at i, height h.
    Split at the middle level of edges: lay out the top part, then each of
    the 2**cut bottom subtrees recursively."""
    if h == 0:
        return [i]
    if h == 1:
        return [i, 2 * i, 2 * i + 1]
    cut = h // 2
    top = preorder_upto(i, cut - 1)
    bottoms = depth_nodes(i, cut)
    return top + [n for r in bottoms for n in veb(r, h - cut)]

def find(k):                              # BST descent; returns heap path
    p, i = [], 1
    while key[i] != k:
        p.append(i)
        i = 2 * i if k < key[i] else 2 * i + 1
    return p + [i]

pos_inorder = {i: key[i] - 1 for i in key}     # sorted-array layout: pos = rank-1
order = veb(1, H)
pos_veb = {i: p for p, i in enumerate(order)}

def misses(path, pos):
    return len({pos[i] // L for i in path})

keys = [16, 8, 24, 4, 12, 20, 28, 7, 1, 31]
rows = []
for k in keys:
    p = find(k)
    rows.append((k, len(p), misses(p, pos_inorder), misses(p, pos_veb)))

print(f"tree height {H} ({N} nodes), keys = in-order ranks, L = {L} keys/line")
print("vEB memory order (keys):")
print(" ".join(str(key[i]) for i in order))
print()
print(" key  probes  in-order  vEB")
for k, np_, mi, mv in rows:
    print(f"{k:4d}  {np_:6d}  {mi:8d}  {mv:3d}")
ti, tv = sum(r[2] for r in rows), sum(r[3] for r in rows)
w = sum(1 for _, _, mi, mv in rows if mv < mi)
t = sum(1 for _, _, mi, mv in rows if mv == mi)
print(f"totals: in-order {ti} misses, vEB {tv} misses")
print(f"vEB strictly better on {w}/{len(rows)} searches, ties {t}, losses {len(rows) - w - t}")
lb = math.log(N + 1) / math.log(L + 1)
bh = math.log2(N) - math.log2(L)
print(f"info-theoretic floor: log({N + 1})/log({L + 1}) = {lb:.2f} misses per search")
print(f"binary-search count:  lg({N})-lg({L}) = {bh:.2f} misses (Demaine, Thm 3)")

Real output:

tree height 4 (31 nodes), keys = in-order ranks, L = 4 keys/line
vEB memory order (keys):
16 8 24 4 2 1 3 6 5 7 12 10 9 11 14 13 15 20 18 17 19 22 21 23 28 26 25 27 30 29 31

 key  probes  in-order  vEB
  16       1         1    1
   8       2         2    1
  24       2         2    1
   4       3         3    1
  12       3         3    2
  20       3         3    2
  28       3         3    2
   7       5         3    3
   1       5         3    2
  31       5         4    3
totals: in-order 27 misses, vEB 18 misses
vEB strictly better on 8/10 searches, ties 2, losses 0
info-theoretic floor: log(32)/log(5) = 2.15 misses per search
binary-search count:  lg(31)-lg(4) = 2.95 misses (Demaine, Thm 3)

Read the table the way the theorems predict. The two ties are structural: key 16 is the root and sits on line 0 in both layouts, and key 7’s five probes happen to hit three lines either way. The in-order maximum of 4 misses tracks the lg(n) - lg(L) ~ 2.95 count plus end effects; the vEB maximum of 3 sits just above the information-theoretic floor of 2.15, exactly the constant-factor slack the lower-bound argument allows. With L = 4 the total gap is 27 versus 18; the gap widens as L grows, since the in-order count keeps lg L wasted levels while the vEB count adds only constants - and real caches live at L = 8 to 64 words per line, not 4.

Why obliviousness wins on real hierarchies (and when it does not)

The multi-level theorem is the reason this subject survived its own idealizations. The paper proves that an optimal cache-oblivious algorithm designed for two levels of memory is also optimal for multiple levels: given a hierarchy of LRU caches where each level contains the lines of the level above (inclusion), lines nest across levels, and each level has strictly more lines than the one above, a cache-oblivious algorithm whose two-level bound is optimal incurs, on each level i, the same misses as the optimal (Z_i, L_i) algorithm for that level [1]. The mechanism is the recursion itself - it bottoms out at every scale, so some level of the recursion always matches whatever cache it lands on - and it is precisely the argument a cache-aware algorithm with one hard-coded s cannot make.

The portability dividend compounds with the simulation results above: LRU costs at most a factor 2 against a half-size ideal cache, the regularity condition erases that factor asymptotically, and the multi-level lemma applies level by level, so the single bound Q(n; Z, L) proven on paper describes a three- or four-level real machine line by line. What the theorems do not promise is constant-factor supremacy, and the empirical literature is blunt about where the constants go. The SIGMETRICS 2007 experimental comparison of cache-oblivious and cache-conscious programs found that the innermost base-case kernels (“microkernels”) of recursive matrix multiply lose to tuned iterative kernels by a wide margin on three of the four architectures they studied, and since overall multiply performance is bounded by the microkernel, their recommendation is recursive structure outside, tuned kernel inside [9]. The Frigo et al. paper itself reports preliminary experiments in the same spirit - oblivious algorithms competitive with, not always faster than, tuned ones [1]. The mature engineering position, and the interview answer: use oblivious recursion for the outer structure where the machine parameters are unknown or multiple, and spend hand-tuning effort on the base case where it is concentrated.

The limits are theorems too, which is what makes them worth stating in an interview. Without the tall-cache assumption, no cache-oblivious comparison sort achieves the I/O-optimal bound [7]; permuting an array has no cache-oblivious algorithm matching the I/O model’s Theta(min{n, sort(n)}) even with a tall cache [3]; and search pays the 1.44 constant [3]. Obliviousness buys optimal adaptation, not optimal communication: problems whose I/O structure is genuinely per-instance, like permuting, can hide information the oblivious code never sees.

Interview lens: four questions this model settles

“Your tile-size-tuned GEMM hits 90% of peak on the dev box and 60% in production. What is the cache-oblivious diagnosis and fix?” The tuned tile s encodes one machine’s Z; production differs (shared L3, virtualization, different SKUs), so s is wrong there and the miss profile degrades. The fix is structural: replace the explicit two-level tiling with largest-dimension recursion (REC-MULT), which reproduces the tuned bound Theta(1 + n^2/L + n^3/(L sqrt(Z))) on every machine without parameters, and keep a tuned microkernel for the base case where the recursion’s constants live. Mention that the recursion is what makes the multi-level theorem applicable - three distinct tiling parameters for three cache levels is the alternative, and it is twelve nested loops.

“Why does binary search on a sorted array cost lg n - lg L misses, and how does the van Emde Boas layout fix it? What does the fix cost?” The probes halve the window, so the last lg L probes all land inside one line - Theta(lg n - lg L) misses total [4] - against the information-theoretic floor of log(n+1)/log(L+1) per search [5]. The vEB layout stores the complete BST in recursive halves so that every depth-d subtree is contiguous; the walk then touches O(log_L n) lines, matching a B-tree that knows L [2], [3]. The costs: index arithmetic per step (computing children’s offsets across layout boundaries), static data only - insertions need the cache-oblivious B-tree machinery of packed-memory arrays [6] - and the unavoidable log2 e constant against cache-aware search [3].

“Funnelsort is called cache-optimal, but it needs Z = Omega(L^2). Doesn’t that break the ‘no assumptions’ pitch?” No - and this is the question’s trap. The tall-cache assumption is a restriction on machines the analysis covers, not a parameter the code reads; the algorithm still contains no Z or L. The deep result is Brodal and Fagerberg’s: some assumption is provably necessary, since no cache-oblivious comparison sort is I/O-optimal without a tall cache, and funnelsort sits on the optimal trade-off curve between assumption strength and overhead for Z much larger than L [7]. A candidate who answers “assumptions are what you prove theorems under; parameters are what you hard-code” has understood the model; one who conflates them has not.

“Your cache-oblivious bound is optimal for one ideal cache. Why does it say anything about a four-level hierarchy with LRU replacement?” Two simulation lemmas bridge the gap [1]. For LRU: Sleator-Tarjan competitiveness gives at most twice the misses of a half-size ideal cache, so an algorithm with the regularity property Q(n; Z, L) = O(Q(n; 2Z, L)) suffers Theta(Q(n; Z, L)) LRU misses - and every bound in the FOCS paper is regular. For multi-level: under inclusion, line nesting, and strictly increasing line counts, an optimal two-level cache-oblivious algorithm is optimal on every level of the hierarchy simultaneously, because its recursion contains subproblems matched to each (Z_i, L_i). Then ask the inverse question they should ask you: which real hierarchies violate inclusion or line nesting, and what does that cost? (Some, and usually a constant - but the theorem’s hypotheses are the honest checklist.)

References

1. M. Frigo, C. E. Leiserson, H. Prokop, S. Ramachandran, “Cache-Oblivious Algorithms,” 40th Annual Symposium on Foundations of Computer Science (FOCS), pp. 285-297, 1999, DOI 10.1109/SFFCS.1999.814600 (Crossref-verified; note IEEE registers FOCS ’99 under the double-F SFFCS prefix — the single-F SFCS.1999.814600 variant sometimes cited does not resolve, and 10.1109/SFCS.1999.814916 is likewise dead under either prefix). Source of the ideal-cache model, cache-aware/oblivious definitions, REC-MULT/REC-TRANSPOSE/FFT/funnelsort bounds, LRU and multi-level theorems.
2. H. Prokop, Cache-Oblivious Algorithms, M.Eng. thesis, MIT, June 1999, https://dspace.mit.edu/handle/1721.1/80568 (metadata verified via the DSpace API; full text behind a bot wall at access time). Origin of the van Emde Boas static search tree layout with O(log_B N) search.
3. G. S. Brodal, “Cache-Oblivious Algorithms and Data Structures,” invited lecture, 9th Scandinavian Workshop on Algorithm Theory (SWAT), LNCS 3111, 2004, DOI 10.1007/978-3-540-27810-8_2, PDF: https://cs.au.dk/~gerth/papers/swat04invited.pdf - source for Prokop-tree attribution, the log2 e·log_B N search lower bound, Lazy Funnelsort, and the sorting/permuting impossibility results of Brodal-Fagerberg.
4. E. D. Demaine, “Cache-Oblivious Algorithms and Data Structures,” survey lecture notes, MIT CSAIL, 2002, text verified from https://cs.yazd.ac.ir/hasheminezhad/BGF15R5.pdf - source for Theorem 3 (binary search Theta(lg N - lg B) transfers), the information-theoretic search lower bound, and the vEB-layout search-tree analysis.
5. MIT OCW 6.851 Advanced Data Structures, Spring 2012, Lecture 7 notes “Memory Hierarchy Models”: https://ocw.mit.edu/courses/6-851-advanced-data-structures-spring-2012/6ab00c67f451beda0bbd014ab7328c98_MIT6_851S12_L7.pdf - B-tree search at O(log_{B+1} N) transfers and the bits-per-line argument giving Omega(log(N+1)/log(B+1)).
6. M. A. Bender, E. D. Demaine, M. Farach-Colton, “Cache-Oblivious B-Trees,” SIAM Journal on Computing 35(2):341-358, 2005, DOI 10.1137/S0097539701389956 (Crossref-verified; conference version FOCS 2000, DOI 10.1109/SFCS.2000.892128).
7. G. S. Brodal, R. Fagerberg, “On the Limits of Cache-Obliviousness,” 35th ACM Symposium on Theory of Computing (STOC), 2003, DOI 10.1145/780587.780589 (Crossref-verified) - no cache-oblivious comparison sort is I/O-optimal without a tall-cache assumption; the tall-cache/overhead trade-off.
8. A. Aggarwal, J. S. Vitter, “The Input/Output Complexity of Sorting and Related Problems,” Communications of the ACM 31(9):1116-1127, 1988, DOI 10.1145/48529.48535 (Crossref-verified) - the Sort(N) = Theta((N/B) log_{M/B}(N/B)) bound funnelsort matches.
9. H. Yotov, T. Roeder, K. Pingali, J. Gunnels, F. Gustavson, “An Experimental Comparison of Cache-Oblivious and Cache-Conscious Programs,” ACM SIGMETRICS, 2007, DOI 10.1145/1248377.1248394 (Crossref-verified), PDF: https://www.cs.utexas.edu/~pingali/CS378/2009sp/papers/co.pdf - source for the microkernel findings; the FOCS’99 extended abstract was verified from the mirror https://www.cs.utexas.edu/~pingali/CS395T/2012sp/papers/coAlgorithms.pdf.
10. MIT 6.6506 Data Structures for Performance, Spring 2023, Lecture 3 notes, “The Ideal-Cache Model”: https://jshun.csail.mit.edu/6506-s23/lectures/lecture3.pdf - source for the s/t/u per-level tuning-parameter framing, the “voodoo parameters” and twelve-nested-loops description of multi-level cache-aware tiling, and the tall-cache transformation treatment.