Cache — where it appears
Named by 3 essays across one field — each of them below, with the objects they name alongside it.
The same arithmetic at a different price
A blocked and an unblocked elimination perform 72,568 operations each — the same operations, associated differently — choose the same pivots, and return a factorisation identical to the last bit: ‖PA − LU‖/‖A‖ = 4.487946226420872·10⁻¹⁶ in both. One of them moves 41,332 words between fast and slow memory and the other moves 19,476.
A block size is a property of the machine
Three lines of counting say the best block size is √(M/3). Scanned over every integer at five fast memories, the measured optimum is √M − 2 — exactly, at all five. The count has the right scaling and the wrong constant, low by a factor of 1.56, and the wrong form: the answer is affine in √M rather than proportional to it.
One column of room past the edge
A recursive LU cut at multiples of the cache's edge leaves one short leaf per dimension, and the one-column leftovers cost the most. Folding the leftover into the leaf beside it puts that leaf one column past the edge, where every leaf at once costs two and a half times the pure recursion — so the prediction was that folding loses at 256 words and wins only where there are many leaves. It wins at every memory, on every one-column size, and wins more where the leaves are fewer: 0.021 of the pure recursion's traffic at 64 words, 0.074 at 400, bringing the short sizes down among the sizes with no leftover at all. Folding two columns loses everywhere, by up to three quarters. One leaf product says why: the edge is set by the cube, and a leaf wider in one dimension has exactly one column of room.
Named alongside it
The objects these essays reach for when they reach for this one.
Blocked algorithmData movementFlop countMemory hierarchyLoop orderLU factorisationCommunication lower boundFitted exponentRecursive factorisationResidual