One column of room past the edge

The short leaf belongs at the bottom settled where a recursive LU’s one short leaf should go. The recursion cuts every dimension at a multiple of the cache’s edge — $\sqrt{M} - 2$ columns, the width a block size is a property of the machine found to be the cheapest leaf at every memory it scanned — so that every leaf is exactly the edge wide except one leftover per dimension. Cut off last, at the bottom of the recursion, the leftover is cheaper than cut off first. But it still costs: at 256 words the one-column sizes 99, 113 and 127 moved 0.90 to 0.95 of the pure recursion’s words against 0.85 to 0.90 for the sizes with nothing left over. And the same essay measured the edge’s other side. With the base case one column past the edge — every leaf a column too wide — the aligned cut’s median size costs two and a half to three times the pure recursion.

Its last section proposed the obvious repair and predicted it would fail. “A cut that absorbs a one-column leftover into its neighbour makes one leaf a column wider than the edge — one leaf on the cliff instead of a narrow one off it. The width sweep’s cliff is a factor of two for a leaf one column too wide, but one leaf of eight is an eighth of the traffic, and the prediction with a sign is that folding loses at 256 words and wins only where the leftover is one column and the leaf count is large.”

Folding wins at 256 words, and at every other memory, and it wins most where the leaves are fewest. The premise was that a leaf one column past the edge is on the cliff. It is not, unless it is past the edge in every dimension at once.

The fold, and what stays the same #

The setting is the earlier essays’, the one the same arithmetic at a different price set up to compare two orderings of one elimination. A recursive LU with partial pivoting is run against a counted memory: one fully associative cache of M words with least-recently-used replacement, every word fetched from memory counted. The factorisation, the triangular solve and the trailing product are each cut along their largest dimension until the leaves fit the base case, and the leaves are done by plain loops. The test matrix is diagonally dominant, so every ordering of the elimination chooses the same pivots, and on every run the multiply-adds and the permutation are checked against the pure recursion’s: the arithmetic and the answer are identical, and only the traffic differs.

The new cut differs from the aligned one only when a dimension’s leftover is short. The aligned cut divides a dimension of x columns at the multiple of the edge b nearest its middle, so the leftover $x \bmod b$ ends up as the last leaf. The folded cut divides $x - (x \bmod b)$ that way instead, so the leftover rides on the last full leaf, which is then $b$ plus the leftover wide, and the recursion treats that one widened leaf as a base case. It folds a leftover of one column; a second version folds one or two. Four memories are measured — 64, 144, 256 and 400 words, edges of 6, 10, 14 and 18 columns — on every size from 96 to 127 columns whose leftover is one or two.

One column folded is cheaper everywhere #

The figure above holds the whole result for one-column sizes. At each memory three groups: the sizes with no leftover, the one-column sizes with the leftover cut off last, and the same sizes folded. At 256 words the folded sizes 99, 113 and 127 move 0.883, 0.846 and 0.855 of the pure recursion’s words, against 0.947, 0.898 and 0.902 with the leftover last, and against 0.903, 0.847 and 0.863 for the sizes 98, 112 and 126 that have no leftover at all. Folded, the short sizes stop being short. At 400 words the two one-column sizes, 109 and 127, go from 1.049 and 1.024 — more traffic than the pure recursion — to 0.966 and 0.960, below the sizes with no leftover, which sit at 0.984 and 0.978.

The dial runs the comparison at every memory. At 64 words, edge six, the six one-column sizes save about two hundredths each: 97 from 0.807 to 0.783, 127 from 0.821 to 0.802. At 144 words the three save four hundredths. At 256 the three save five, and at 400 the two save six and eight. On every one-column size at every memory, the folded cut moves fewer words than the leftover-last cut, with the same elimination underneath.

The prediction tied the saving to the number of leaves, on the reasoning that one wide leaf among many is a small share of the traffic. The saving runs the other way: 0.021 at 64 words, where a dimension of a hundred columns has sixteen full leaves, 0.044 at 144 with ten, 0.051 at 256 with seven and 0.074 at 400 with six. The reasoning priced the wide leaf as a cost to be diluted. It is not a cost. What folding removes is the narrow leaf, and a narrow leaf’s cost is set by how much wider the edge is than one column — six times at 64 words, eighteen at 400 — so the larger the edge, the more a one-column leftover was wasting and the more folding recovers.

Two columns folded is over the cliff #

The second version folds a leftover of two columns as well, so the widened leaf is two past the edge. It loses on every two-column size at every memory. At 64 words the five two-column sizes go from about 0.80 to about 0.90; at 144 words from 0.82–0.86 to 1.07–1.14, above the pure recursion; at 256 from 0.94 and 0.90 to 1.46 and 1.36; at 400 the one two-column size, 110, goes from 1.042 to 1.766. The dial shows the two-column dots climbing away from the others as the memory grows, while the one-column dots fall beneath them.

So between one column of overhang and two, the cut goes from the best thing measured on these sizes to the worst. That is a cliff, but it is not where the earlier essay placed it. One column past the edge in every leaf was over it; one column past the edge in one leaf per dimension is not; two columns past the edge in one leaf per dimension is. The question is what a leaf’s width is measured against.

What one leaf product can hold #

The recursion’s traffic is the sum of its leaves’, and a leaf is a product $C \mathrel{-}= XY$ with C of $m \times q$, X of $m \times k$ and Y of $k \times q$, done by three loops, rows of C outermost. Running one such product three times through the same cache and counting what its third pass fetches gives its price when the recursion reaches it warm, with nothing else in the way.

At the edge the product fetches $2/b$ words a multiply-add — 0.333 at 64 words, 0.143 at 256, 0.111 at 400 — which is C and X brought in once a pass while all of Y stays in cache. Widen the rows by one or two and nothing changes per multiply-add: the rows of C and X stream through and Y still stays. Widen the inner dimension or the columns by one and the product gets slightly cheaper, 0.138 instead of 0.143 at 256 words: more work for the same pass over C and X. Widen either of them by two, or all three dimensions by one, and the product fetches 1.10 to 1.25 words a multiply-add at every memory — about every operand, every time. Y no longer stays.

The count behind it is the size of what has to stay. With rows outermost, the working set is the block of Y, $kq$ words, plus a row of X and a row of C, $k + q$ more. At the edge, $b = \sqrt{M} - 2$ in all three dimensions, that is $M - 2\sqrt{M}$: two edges’ worth of words to spare. One dimension a column over takes about $\sqrt{M}$ of them and leaves about $\sqrt{M}$; that is enough. Two columns over in one dimension, or one over in both $k$ and $q$, leaves one or two words — $M - 2$ and $M - 1$ — and a least-recently-used cache that must also bring in the next row before the last one leaves cannot do it. The rows, $m$, are not in the count at all.

So the edge, $\sqrt{M} - 2$, is the widest cube that fits — the widest leaf that can be that wide in all three dimensions — and the room it leaves is one column in one dimension. A recursion whose leaves are all one column past the edge is past it in all three, every time two such leaves meet in a product, and that was the earlier essay’s cliff. The recursion that was never told the memory measured the pure recursion within 0.94 to 1.28 times the best tuned block at every memory; the fold is one more place where telling it the memory, to the column, is worth a few per cent. A folded leaf is one column past in one dimension of most products it takes part in. It meets another widened leaf in the same product only where the last leaves of two dimensions cross, at the bottom-right corner of the factorisation.

The fold also takes the leftover’s calls away #

Words are what the counter measures, and the earlier essays measured nothing else. The message and the word made the same distinction between a distributed code’s volume and its count of exchanges, and found the method with the fewest exchanges sending the most words. The recursion’s calls are a second cost, the one a real machine pays in function entries and loop set-ups, and the fold changes them too. A one-column leftover is a dimension that never stops being cut until it reaches a one-wide piece: it adds a level of products along every edge of the recursion that touches it. Folded, the leftover rides on a leaf the recursion treats as a base case, and those products are never made.

At every memory the folded one-column size makes no more calls than the size one column smaller, which has no leftover at all: 97 columns at 64 words make 2,675 calls folded against 2,686 for 96 columns, and 3,219 with the leftover cut off last; 99 at 256 words make 218 folded, 220 for 98, and 330 with the leftover last; 109 at 400 words make 136, 138 and 220. The leftover-last cut makes an eighth more calls than the folded one at 64 words and more than half again as many at 400 — the same pattern as the words, for the same reason: the wider the edge, the more a one-wide piece multiplies what has to be cut. The block size a recursion still has found the recursion’s traffic stepping at the halvings of n; the leftover is one more halving the fold removes.

Why the prediction priced it backwards #

The prediction took the cliff as a property of a leaf: a leaf one column too wide costs about twice what it should, and one such leaf among eight costs an eighth of that. Measured on a leaf product, a leaf one column too wide in one dimension costs nothing extra at all; the factor of two belonged to products whose every dimension was too wide. And the narrow leaf the fold removes is the expensive thing. A one-column leftover turns into a one-column panel at the bottom of the factorisation and a one-wide strip in every product that touches it — the shape whose words per multiply-add are worst — and leaves cut to the edge on purpose found those strips costing the one-column sizes five hundredths of the pure recursion’s traffic that the sizes with no leftover did not pay. The fold recovers all of it and a little more, because the widened leaf is itself a slightly better leaf.

The leaf that sits on the edge found no trade between a processor that wants wide leaves and a cache that wants narrow ones: at every width the cheapest leaf in words was the widest that fitted. The fold is that rule applied to one dimension at a time. The widest that fits in all three is the edge; the widest that fits in one, with the other two at the edge, is one column more.

What this changes in the rule #

The rule the earlier essays arrived at was: set the base case at $\sqrt{M} - 2$, cut every dimension at multiples of it, and cut the leftover off last. The measurement adds a clause. A leftover of one column is folded into the last full leaf; a leftover of two or more is cut off last. With that clause the one-column sizes, which were the worst sizes under the old rule, come within two hundredths of the sizes with no leftover at 64 and 144 words and fall below them at 256 and 400.

The clause depends on the edge being known to the column, and that figure is why. The aligned cut is cheapest at the edge or just under it, and one column over it the median size costs nearly three times the pure recursion: every leaf is then past the edge in all three dimensions of every product, the case the leaf product above puts at a word per multiply-add. An edge overestimated by one would also turn the fold’s one column of room into none — the folded leaf would be two past the true edge, the configuration measured above as the worst on the page. The count suggests that a code unsure of its edge by a column should take the lower estimate and fold, which keeps the fold’s room and costs the narrower leaves a few per cent; that is the count’s suggestion, and it is not measured here.

What the counter does not see #

The memory is one level, fully associative, with exact least-recently-used replacement and lines of one word. A real cache moves lines of eight words or more and is set-associative, and both change where the cliff falls: a line size turns the count’s single-word margins into margins of a line, and an associativity limit can put the cliff earlier for a block whose rows map to the same sets. The leaves are done in one loop order; a leaf kernel that keeps C in registers and streams Y would have a different count and its own room. And the sizes are 96 to 127 columns — large enough for a few levels of recursion, small enough that the bottom-right corner where two folded leaves meet is a visible share of the work. At thousands of columns that corner is negligible and the fold’s saving per size would be the narrow leaf’s cost alone.

Still open: a cliff with a line size, and a leftover split across leaves #

The cliff with a line size. The earlier essay’s second question stands, and the leaf count makes it sharp. With lines of eight words a row of X or C costs a line for every eight of its words, the margin left by one extra column is $\sqrt{M}$ words but only $\sqrt{M}/8$ lines, and a fold’s room may vanish. The prediction with a sign is that at 256 words with lines of eight words the folded leaf still costs within a tenth of the edge leaf, because the margin it uses is less than a line per row, and that the two-column fold is still over the cliff — so the rule’s clause survives the line size unchanged.

A two-column leftover split between two leaves. Folding two columns into one leaf is over the cliff, but two columns folded one into each of the last two full leaves would put two leaves one column over in different places. The prediction is that this wins on every two-column size at every memory, by about the one-column saving, unless the two widened leaves meet in a product — which happens when they are adjacent, and so the two columns should go into leaves that are not neighbours.