replication-crossing
At its defaults it draws what 4 layers save, against the size of the machine. The traffic of a flat layout divided by the traffic of a 4-layer one, at four processor counts, on a logarithmic horizontal axis. The upper line is the √4 the asymptotic analysis promises and the lower one is break-even. The measurement runs from 0.88 at 64 processors — a loss — to 1.44 at 576, and it is the same curve at every matrix size, because every word counted here is exactly proportional to n².
replication-crossing is one function in lib/figures/comm.js —
two ways of buying something back — a second pass, and memory spent on messages. Everything below came out of it during this build, at
arguments taken from the essays rather than invented for this page. A figure here is the
figure a reader meets in an essay, and if the generator changes, this page changes with it.
At its defaults
Drawn even though every essay passes arguments — which on this site is every essay, at 100% of placements since the standard pass. A default nothing exercises is a trap for the next essay to call this with none, and this is the page where a default that has drifted from the figures around it becomes visible.
The traffic of a flat layout divided by the traffic of a 4-layer one, at four processor counts, on a logarithmic horizontal axis. The upper line is the √4 the asymptotic analysis promises and the lower one is break-even. The measurement runs from 0.88 at 64 processors — a loss — to 1.44 at 576, and it is the same curve at every matrix size, because every word counted here is exactly proportional to n².
n: 48
The arguments are the ones A block size is a property of the machine passes. A value drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.
The traffic of a flat layout divided by the traffic of a 4-layer one, at four processor counts, on a logarithmic horizontal axis. The upper line is the √4 the asymptotic analysis promises and the lower one is break-even. The measurement runs from 0.88 at 64 processors — a loss — to 1.44 at 576, and it is the same curve at every matrix size, because every word counted here is exactly proportional to n².
n: 96
The arguments are the ones A limit the matrix never reaches passes. A value drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.
The traffic of a flat layout divided by the traffic of a 4-layer one, at four processor counts, on a logarithmic horizontal axis. The upper line is the √4 the asymptotic analysis promises and the lower one is break-even. The measurement runs from 0.88 at 64 processors — a loss — to 1.44 at 576, and it is the same curve at every matrix size, because every word counted here is exactly proportional to n².
n: 192
The arguments are the ones A norm that overflows before it is a norm passes. A value drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.
The traffic of a flat layout divided by the traffic of a 4-layer one, at four processor counts, on a logarithmic horizontal axis. The upper line is the √4 the asymptotic analysis promises and the lower one is break-even. The measurement runs from 0.88 at 64 processors — a loss — to 1.44 at 576, and it is the same curve at every matrix size, because every word counted here is exactly proportional to n².
n: 144
The arguments are the ones The order they are added in passes. A value drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.
The traffic of a flat layout divided by the traffic of a 4-layer one, at four processor counts, on a logarithmic horizontal axis. The upper line is the √4 the asymptotic analysis promises and the lower one is break-even. The measurement runs from 0.88 at 64 processors — a loss — to 1.44 at 576, and it is the same curve at every matrix size, because every word counted here is exactly proportional to n².
What it checked while drawing
Every figure above asserted its own claims on the way to being drawn, and a claim that failed
would have failed the build rather than drawn a wrong picture. Those assertions used to leave
no trace at all: a passing one returned true and the only evidence the figure had
checked anything was that nothing crashed. The list below is what they actually said, collected
by running this generator with an observer installed — not a description of
what it is believed to check.
17 distinct claims across 5 sets of arguments, grouped below by shape — because most of them are one sentence with a different number in it, and how many separate times that sentence was put to the test is the informative part.
and saves less than √4 at p = 64 — asserted 4 times
the layered layout returns the product at p = 64 — asserted 4 times
a matrix that divides into every grid drawn
and costs traffic outright on the smallest machine
enough machine sizes for a trend
matmul shapes agree
the matrix divides into the grid
the processors divide into c layers of a square grid
the replication factor the grids are chosen for
there is at least one summation block per layer
while saving a real factor on the largest
Against the rule
The rule does not apply to it. It factorises nothing, so there is no residual it could be withholding. That is worth stating rather than leaving blank: a site that reported the rule as satisfied by every generator would be counting mostly generators the rule never reached.
Across the library: the rule bites on 70
of 151 generators —
55 print a residual and
15 are exempt with a published reason;
81 factorise nothing.
Read from lib/residual-rule.js, which is the same body the gate enforces from,
and the gate's last check fails the build if this page and it disagree about any generator.
Where it is called
Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.
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.
Structure, and the solver that cannot see itA limit the matrix never reaches
Szegő's theorem gives a Toeplitz family's condition number in closed form — ((1+ρ)/(1−ρ))², which is 81 at ρ = 0.8. The 8×8 section reaches 52% of it, the 128×128 reaches 98.9%, and none of them ever arrives. A statement about a family is not a statement about the matrix in front of you.
The arithmetic underneathA norm that overflows before it is a norm
The vector of sixteen thousands has a Euclidean norm of 4,000, which fp16 represents exactly. Written as the square root of the sum of squares it returns infinity, because squaring doubles the exponent — and the expression costs half the format's range on the one computation every iterative method performs at every step.
Where the flop count stopped predicting the timeA reduction that changes the order
A tall-skinny QR computed as a tree of independent block factorisations touches a 512×12 matrix once instead of twelve times, computes a completely different sequence of roundings from the sweep it replaces, and returns ‖AᵀA − RᵀR‖/‖AᵀA‖ = 1.65·10⁻¹⁵ against the sweep's 9.95·10⁻¹⁵. On the same matrix classical Gram–Schmidt returns 4.6·10⁻¹⁰.
Where the flop count stopped predicting the timeMemory bought with messages
Holding four copies of the data instead of one is supposed to cut a matrix multiplication's communication by √4. Measured on a machine of 64 processors it costs 14% more traffic; at 576 it saves 44%, which is 72% of what the law promises. The memory is exactly four times, and that part is not asymptotic.
Elimination, and the swapThe bound that is never attained
Partial pivoting's stability guarantee permits the entries to double at every step — a factor of 5.5·10¹¹ at n = 40. The measured growth on random matrices of that size is about three. The gap is eleven orders of magnitude, and the guarantee is still worth having.
The arithmetic underneathThe order they are added in
Addition is associative in the algebra and is not associative in the arithmetic. The same million numbers, added in a different order, give answers that differ in the third significant figure — and the fix is not a wider float, it is a different order.
Where the flop count stopped predicting the timeThe 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.
Structure, and the solver that cannot see itTwo dimensions, and the cluster that thins
The same kernel, the same averaging, the same transform — applied along two axes instead of one. In one dimension the preconditioned step count is 7, 10, 10, 10; on square grids with the same unknown counts it is 10, 18, 20, 21, and the share of the spectrum near one falls from 56% to 17%.
Sparsity, and what elimination costsWhat the symbolic phase can only bound
Without pivoting, the fill can be computed from the graph and the count is exact — 233 predicted, 233 measured. With pivoting it is 233 predicted and 242 measured, and what survives is a bound that is right at every threshold and loose by 1.7 times at the largest grid drawn.
The arithmetic underneathWhere the hardware went
bfloat16 carries eight mantissa bits, which puts its refinement threshold at a condition number of 256. That is not an exotic matrix. It is an ordinary one, and past it the method still improves the answer by a factor of four hundred while getting nowhere near a usable one.