The recursion that was never told the memory

A block size is a property of the machine scanned a blocked LU factorisation over every integer block size at five fast memories and found the best block at exactly √M − 2, at all five. It is a strong result and a slightly uncomfortable one. A block size that belongs to the machine has to be told the machine, and a real machine has several fast memories nested inside each other, so the tuning has to pick one of them.

That essay ended by naming the way out without measuring it. A recursive elimination has no block size. It splits the columns in half, factors the left half, updates the right half, and factors what is left — doing each of those by splitting again, down to a single column. At some depth of that recursion every subproblem fits whatever the fast memory is, because the subproblems have every size between the whole matrix and one entry. The claim, stated in the memory-hierarchy literature as a theorem about asymptotic traffic, is that such a recursion gets the right behaviour without being told any of the sizes.

The theorem says nothing about constants, and the whole of the previous essay was about a constant — the factor of 1.56 between √(M/3) and √M − 2 — so the useful question is a measurement. On the same counted memory, on the same matrix, how many words does the recursion move against the best block the scan can find?

The same elimination, associated a third way #

The recursion is not a different factorisation, and the first thing to check is that it is not. The same arithmetic at a different price established that the blocked and unblocked eliminations perform the same operations, associated differently, and return factors identical to the last bit. The recursion is a third association of the same set — the same move the order the products are taken in makes for a contraction of tensors, where one value has many evaluation orders and their costs differ by a factor of two million.

Its pivot search is partial pivoting over the whole column below the diagonal, and every interchange swaps whole rows exactly as the unblocked elimination does — the interchanges the swap that is not optional insists on — so the traffic of the swaps is common to all three and the comparison is of the update. By the time the recursion searches a column, every update from the columns to its left has been applied to it — the left half is always finished before the right half is touched — so the pivots are the unblocked elimination’s pivots. That is checked on the permutation rather than argued: the three permutation vectors are identical.

The operation count is compared as an integer, and it is the same integer: 585,200 multiply-adds and divisions for all three orderings at n = 96. The residual ‖PA − LU‖/‖A‖ is 2.9·10⁻¹⁶. Everything that differs between the three is in the column headed “words moved”, which is the point of having counted the memory rather than timed a machine: elimination is a sequence of choices, and none of the choices has changed.

The memory being counted is the model from the two earlier essays on blocking: a fast memory of M words, fully associative and least-recently-used, a slow memory of unlimited size, and a count of every word that has to cross between them. Nothing in the recursion reads M. The triangular solve and the Schur complement update inside it are recursive too, each halving whichever of its dimensions is larger, down to a single multiply-add. The only base case of the whole factorisation is the panel of one column.

Eight memories, and the recursion never knew which #

The blocked elimination is tuned by brute force: at each memory the scan runs every block from 1 to 24 and keeps the minimum, which is the best any tuning restricted to that range can do. The recursion is run once per memory, with nothing to tune.

Never more than 28% above the tuned block, and below it at the two largest memories. The worst case is M = 64, where the tuned block of 6 moves 158,119 words and the recursion 201,919.

The two wins need an honest reading, because they are partly the scan’s limitation rather than the recursion’s strength. At M = 400 and 576 the best block within 1 to 24 is 10 and 12, not the √M − 2 = 18 and 22 the previous essay’s rule predicts; the scan’s own minimum has stopped following √M at those memories, for a reason this measurement did not isolate. The recursion is bound by no rule of that kind. So the honest statement at the two largest memories is that the recursion beats every block this scan tried, not that it beats every schedule there is — a larger block, or a block that differs between the panel and the update, was not tried.

What the table does establish is the shape of the recursion’s cost. Across the six memories where the scan’s minimum is genuine, the recursion pays between 10% and 28% for not knowing M. That is a small price against what a wrong guess costs a blocked elimination: the previous essay’s table has a block chosen one column too large costing 2.7 times the best, and the two-cache measurement below has a block tuned to one memory costing up to 2.87 times the best at another. The recursion never pays the cliff, and it never collects the last 10 to 28 per cent of the slope.

A constant distance from the floor #

A block size is a property of the machine also measured the blocked elimination against the lower bound on traffic for this model, n³/√M words for an n-by-n elimination, and found it sitting a constant above that floor across matrix sizes. The same floor is available for every row of the table above, and it separates the two orderings in a way the ratio column does not.

At n = 96 the floor is 884,736/√M words. Against it the tuned block moves 1.42, 1.43, 1.41, 1.48, 1.50, 1.61, 1.73 and 1.74 times the floor across the eight memories from 36 to 576 words — drifting upward by about a fifth as the memory grows, and taking a different block to do it at nearly every step. The recursion moves 1.73, 1.83, 1.72, 1.72, 1.80, 1.76, 1.67 and 1.63 times the floor: between 1.63 and 1.83 at every memory, with no drift.

That is the property the theorem about memory hierarchies states, seen at one size rather than as an asymptote. An ordering that stays within a fixed factor of the floor at every M without knowing M is exactly what having no block size is supposed to buy, and the factor here is about 1.75. The tuned block is closer to the floor on six memories of eight — by the ten to twenty-eight per cent of the ratio column — and further on the two where its own minimum stopped following √M.

Two cautions keep that reading honest. The floor is an asymptotic bound whose constant has not been established for this model, so “1.75 times the floor” is a ratio to a formula rather than to the best schedule that exists. And a flat ratio over a decade and a half of M at a single matrix size is evidence of a shape, not a proof of one. What the column does show is that the recursion’s cost is a property of the problem and the memory together, where the tuned block’s cost is also a property of how well it was tuned.

Why the recursion lands near the best block #

The mechanism is visible in the shape of the blocked elimination’s curve, which is a slope on the left and a cliff on the right. A block slightly too small wastes a little; a block one column too large evicts the data the next inner loop is about to read and wastes a great deal.

The recursion’s subproblems halve at every level. For any fast memory there is a level at which a subproblem’s working set fits and the level above does not, and the subproblems at the level that fits are between half and all of the largest size that would fit. So the recursion is, in effect, always using a block on the safe side of the cliff, within a factor of two of the edge. On the slope side a factor of two is worth tens of per cent, which is the 10% to 28% in the table; on the cliff side it would be worth a factor of three, and the recursion is never on the cliff side because it only ever works at sizes that fit.

That reading is consistent with the table and is not separately verified by instrumenting the recursion’s levels. Two things in the table support it. The recursion’s ratio does not trend with M — 1.22 at 36, 1.28 at 64, 1.16 at 144, 1.10 at 256 — which is what a factor-of-two quantisation of a size against a smoothly moving edge should look like: a sawtooth rather than a drift. And the recursion’s absolute traffic falls at every step of the table, while the tuned block itself jumps — 14 at M = 256, then 10 at 400.

The same halving is what a reduction that changes the order used for a different purpose: a tall-skinny QR computed as a binary tree of small factorisations, where the tree is what lets a machine of sixteen processors touch the matrix once. Recursion and trees keep reappearing in this field for one reason. A problem divided in halves has a piece of every size, and a machine with a limit at an unknown size is served by whichever piece fits. The order decides the memory is the sparse field’s version of the same observation: one factorisation, many orderings, and a cost that belongs to the ordering alone.

A machine with two caches #

The recursion’s case is weakest when there is one fast memory, because then a block can be tuned exactly and the recursion can only come close. Its case should be strongest when there are two, because then no single block can be tuned to both, and the recursion has not been tuned to either.

The counted memory here has two nested caches: an inner one of l₁ words inside an outer one of l₂ words, inside slow storage. Every touch refreshes both; an address missing from the inner cache is counted as a word crossing the inner boundary, and one missing from the outer cache as a word crossing the outer boundary as well. The two counts are kept separate rather than weighted, because a weight would be a guess about how much slower one boundary is than the other on some particular machine.

At caches of 64 and 576 words, the block tuned to the inner cache costs 1.49 times the best at the outer boundary, and the block tuned to the outer cache costs 2.17 times the best at the inner one. Whichever cache the tuning chose, the other one pays between a half and double. The recursion’s worse boundary is at 1.28, and its other is at 0.94.

Across seven pairs of cache sizes the block tuned to the inner cache costs 1.21 to 2.87 times the best at the outer boundary, and the block tuned to the outer costs 1.64 to 2.57 at the inner. The recursion’s worse boundary sits at 1.08 to 1.35 times its best. Against a block tuned to one cache the recursion wins on six of the seven machines. On the seventh, caches of 100 and 576 words, the inner cache’s own block of 8 happens to serve the outer cache too, at 1.21, against the recursion’s 1.22.

The block that knows both caches, and where it wins #

There is a fairer opponent. A scan that is told both cache sizes can choose the block that minimises the worse of the two ratios — a compromise no single-cache tuning would find, and a block that often sits at neither cache’s own optimum. Against that block the recursion’s record is mixed, and the mixture is the finding.

The recursion is better on five of the seven machines, within one per cent on one — 1.218 against 1.208 at caches of 100 and 576 — and worse on one, at caches of 16 and 256, where a block of 7 holds both boundaries within 1.24 and the recursion’s inner boundary is at 1.35.

The losing machine has the smallest inner cache, sixteen words, where the recursion’s factor-of-two quantisation is a factor of two on a very small size, and at that scale the slope side of the curve is steep. That is the same mechanism as the one-cache table’s worst case at M = 64, pushed further, and it is a prediction rather than an explanation until the recursion’s levels are counted directly.

The refusal on this essay is the overstatement a reader might take from the headline, that the recursion moves fewer words than every tuned block. It does not. Against a block tuned to one memory with that memory known, it loses by 10% to 28% at six of eight memories. What it beats is the schedule tuned to one cache when there are two, on six machines of seven, and it roughly matches the schedule tuned to both without being told either size — which is the property a factorisation shipped in a library, to machines its authors will never see, actually needs.

What the memory model can and cannot say #

The counts are exact integers on a model, and the model is the one the whole field has used: least-recently-used, fully associative caches with every word the same size and every boundary the same kind of boundary. A real cache is set-associative, has lines of eight or sixteen words, and is not least-recently-used, and a real machine’s second cache is shared between processes. The earlier essays measured the blocked elimination on this model precisely so that the comparison between orderings could be exact, and the same trade applies here: the ratios are properties of the orderings on the model, and not predictions of seconds on a machine.

The recursion’s cost is also larger in one respect the model does not count: the overhead of the recursion itself — function calls, index arithmetic, the bookkeeping of which half is being worked on — which is free on the model and not free on hardware. Recursive implementations commonly switch to an unblocked kernel below some small size for exactly that reason, and that switch is a block size again, chosen for the processor’s arithmetic rather than its cache.

And the model is sequential. The message and the word and memory bought with messages are the collection’s account of traffic between processors, where the quantity is messages rather than words and the lower bounds have a different shape; whether the recursion’s indifference to M carries over to indifference to the number of processors is a different question and is not asked here. The general model of memory without stated sizes, and its layouts and search trees, belongs to the study of algorithms rather than to this field, and nothing here re-derives it; what is measured is its numerical instance, on the one factorisation counted here.

Where this goes from here #

Three levels, and the base case. The two-cache model is the smallest in which “tuned to which memory?” can be asked, and the recursion’s advantage should grow with the number of levels, since every added level is another memory a single block gets wrong. A three-level count, together with a recursion that switches to an unblocked kernel below a stated size, would measure the one block size a recursive code still has and how much it matters.

The panel. Every ordering here uses a one-column panel with partial pivoting over the whole column, which is the part of an elimination that neither blocking nor recursion changes. On a matrix much taller than it is wide the panel dominates the traffic, and the answer in the communication literature is a pivoting rule that works on a tree of blocks rather than on one column. That changes the pivots, and therefore the factorisation, and it is the first step on which the “same arithmetic” of these essays would stop being the same.

And recursion for QR. Householder QR has a recursive formulation of its own, with the same halving of columns and a compact representation of the accumulated reflections. Doing it twice and the tall-skinny tree measured QR’s traffic between processors; its traffic between caches, recursive against blocked, is unmeasured.