What determinism costs

The sum that cannot be wrong establishes that order-independent summation exists. The question that follows immediately is what it costs, and the answer has two halves that point in different directions.

The first half of the answer is on the figure. The second half is not, and is the more important of the two.

Reading the figure #

Six policies, one vector of 2,048 numbers with a summation condition number of about 10⁶.

Runtime order — one add per element, one accumulator, whatever ordering the runtime picks. This is the baseline and it is the fastest thing on the figure.

A fixed partition — the same loop with the thread count pinned. Identical cost, identical accuracy, and reproducible only across runs that agree about the partition, which is why its marker is open rather than filled.

Pre-rounded, one pass — three operations an element, order-independent, and the least accurate policy on the figure at 2.3·10⁻⁷.

Pre-rounded, two passes — seven operations, order-independent, and on this vector exactly the correctly rounded answer.

Compensated — four operations, accurate, and not reproducible, which is the finding of the previous essay.

Exact accumulation — about twelve operations and a list of partials, correctly rounded, and order-independent by definition.

Nothing sits in the bottom left. There is no policy that is both as cheap as the baseline and independent of the order, and there cannot be one: the baseline’s cheapness is exactly its freedom to round wherever the arithmetic lands, and removing that freedom is the whole of what the other policies do.

The operation count is the half that misleads #

Now the half of the answer that is not on the figure, and it is the one this site has a field about.

The same arithmetic at a different price measures two eliminations performing 72,568 operations each, choosing the same pivots, returning a factorisation identical to the last bit — and moving 41,332 and 19,476 words between fast and slow memory. The operation count is identical and the cost is not, by a factor of two.

A reduction is the extreme case of that. It reads n numbers and performs n adds, so it is memory-bound on every machine built in the last thirty years: the loop spends its time waiting for data and the arithmetic unit is idle most of the way. Adding two more operations per element to a loop that is waiting for memory costs approximately nothing.

So the honest reading of the figure’s horizontal axis is not three times the cost. It is:

• the one-pass pre-rounded policy is nearly free on a memory-bound reduction, because the arithmetic it adds fits in time the loop was already spending;
• the two-pass policy costs a second pass over the data, which on a vector that does not fit in cache is a genuine doubling — not because of the seven operations, but because of the second traversal;
• exact accumulation costs what its state costs. A data-dependent inner loop is the description of something that does not vectorise, and a reduction that does not vectorise gives up a factor that has nothing to do with its operation count. The state column below says forty words per accumulator and the measured number is seven, which is a section of its own.

Which reorders the figure. On flops, the ordering is 1, 3, 4, 7, 12. On what a reduction actually spends, it is closer to: the baseline and one-pass pre-rounding are the same speed, two-pass pre-rounding is twice that, and exact accumulation is a different kind of loop.

The state column, which is the one to read #

Every policy on the figure carries a second number that the horizontal axis does not show: how much live state it needs per accumulator.

One accumulator vectorises trivially — the compiler keeps four or eight of them in registers, which is the same trick the length that changes the kernel is about. Two is still fine. Forty is not, and the pattern of writes into them depends on the values, which would defeat the vectoriser for a second reason.

That was offered as the whole argument for the pre-rounded policies over the exact one, and as an argument about registers rather than about arithmetic. Half of it does not survive being measured.

Forty is the format’s worst case, not the vector’s #

The last row of that table is the only one that is not a small constant, and it is the row the argument rests on. It is also the only one that is a bound rather than a count.

Shewchuk’s expansion carries as many non-overlapping partials as it needs, and how many it needs is decided by how far apart in magnitude the terms are. Forty is what the entire binary64 exponent range would require: (1024 + 1074)/53 is about forty non-overlapping doubles, which is the state a reduction would carry if its terms ran from the smallest subnormal to the largest finite number. Instrumented on the four families this field measures, at n = 2,048:

Seven, on the cancelling vector the hero figure is drawn from. Never more than eleven, on data deliberately chosen to be hard. Seven doubles sit in registers as comfortably as two do, so the register argument is not an argument: the state count does not distinguish exact accumulation from compensated summation in any way a compiler would notice.

And the price of the cheapest reproducible policy is a moving quantity, which the cost axis of the hero cannot show.

Three operations an element at every conditioning, and a hundredfold worse answer per hundredfold of κ. At κ = 10², 10⁴, 10⁶ and 10⁸ the cheapest reproducible policy costs the same three operations and reaches 1.91·10⁻¹¹, 2.14·10⁻⁹, 2.29·10⁻⁷ and 2.29·10⁻⁵, while the most accurate policy sits at 10⁻¹⁷ throughout.

So the horizontal axis of the hero is a constant and the vertical one is not, which decides how this field’s central table should be read. The price of determinism is three operations an element on every problem — that is the number this essay is named for, and it does not move. What moves is what those three operations buy: six orders of accuracy behind the best policy at κ = 100 and twelve orders behind it at κ = 10⁸. A cost table is therefore the wrong shape for the decision, because the cost is fixed and the thing being bought is not, and the quantity a caller needs is the gap rather than the price.

What does survive is the clause that came after it. The inner loop runs 4.40 times per element on the cancelling family and 2.83 on the heavy one, and which it is depends on a comparison of magnitudes between the incoming term and each partial — so the trip count is a function of the values. A loop whose trip count is decided by its data does not vectorise however small its state is, and that is sufficient on its own. The essay gave two reasons for the same conclusion; one of them was a number nobody had counted.

The same measurement puts a caveat on the horizontal axis. Twelve operations per element is within ten per cent on the cancelling family and out by nearly a factor of two across the four — 8.48 to 16.52 — so it is a figure for one kind of vector rather than a property of the policy.

That matters downstream, because every entry of the conjugate-gradient table below is computed from it, and the table is a straight line in the operation count. Its four entries for the five-point stencil — 1.22, 1.67, 1.33 and 2.22 at 3, 7, 4 and 12 operations — all satisfy

cost ratio = 1 + 0.111 · (operations − 1)

to three digits, which is what it means for the reductions to be a fixed share of a step. Put the measured operation counts through that line instead of the tabled one and the last column runs from 1.83× on the heavy family to 2.72× on the alternating one, against the single 2.22× printed. Which of those a caller faces is a property of their residual vector rather than of their solver, and it is the difference between exact accumulation nearly doubling a step and it nearly tripling one.

None of that moves the essay’s shape. The cheaper the matrix, the dearer the reproducibility, and a dense problem gets it for a few per cent whatever family the residual belongs to — the same line fitted to the dense row has a slope of 0.0045, so 1.05× at twelve operations runs between 1.03× and 1.07× across the four families, which is noise. The spread only becomes visible where the reductions dominate, which is the same sentence the table was already making, with one more variable in it.

assertTheStateColumnIsAWorstCaseBound holds all of it — that the expansion never reaches a third of the tabled state, that it carries seven on the figure’s own vector, that the trip count is above one and varies with the data, and that the operation count moves by more than half across the four families.

What each one is actually for #

Prices are only useful next to purposes, so:

Runtime order is right whenever no comparison is downstream. A residual printed in a convergence log, a norm reported at the end, a diagnostic. Most reductions are in this category and this field is not an argument for changing them.

A fixed partition is the cheapest thing that helps and it is a partial answer. It removes the thread count as a variable and leaves the scheduler in place, so it fixes reproducibility within one machine’s configuration and not between two. It is worth doing because it is free, and worth not mistaking for a solution.

One-pass pre-rounding is for a reduction whose verdict matters and whose value does not. A rank threshold, a definiteness sign, a convergence test: the comparison needs the two machines to agree, and 10⁻⁷ of the largest element is far below any threshold worth setting. This is the case the policy was invented for and it is nearly free.

Two-pass pre-rounding is for a reduction whose value matters too, which is most residuals. Seven operations, two passes, correctly rounded on the vector measured here, and the same on every machine. If this field has one recommendation it is this one.

Compensation is for accuracy alone, on a machine that is not going to be compared with another one. It is the best accuracy-per-operation on the figure and it buys nothing this field is about.

Exact accumulation is for ground truth. It is what every measurement in this field is against, which is a use that justifies its cost completely: a reference implementation runs once and an inner loop runs 10⁹ times.

What it costs inside a solver, which is the number anybody wants #

Operations per element is the right axis for a summation policy and the wrong axis for a decision. The decision is whether to spend it inside something, so here is the same price paid inside a conjugate gradient step.

One step is a matrix–vector product, three vector updates, and two inner products. Only the last of those is a reduction, so only the last is affected — and how much it matters depends entirely on how expensive the product is. Counting operations on a problem with n = 200:

On a dense matrix the whole question is noise: making both reductions exactly accumulated costs five per cent of a step, and the answer stops depending on the machine. On a five-point stencil — the model problem this site’s iterative field is built on, at five nonzeros a row — exact accumulation doubles the step, and one-pass pre-rounding costs 22%.

That table is the practical content of the essay and its shape is worth stating: the cheaper the matrix, the dearer the reproducibility, because the reductions are a larger share of a step whose product is cheap. A solver on a dense matrix can have bitwise reproducibility for nothing. A solver on a sparse one is making a real choice.

And it points at the right intervention on the expensive side: one-pass pre-rounding at 22% on the sparse problem buys agreement in the stopping test, which is what a stopping test is a race shows costs 674 to 690 iterations — a spread of 2.4%. Spending 22% of a step to remove a 2.4% spread in the step count is a bad trade if the only goal is the count, and a good one if a verdict downstream needs two machines to agree.

What no summation policy buys #

Three of this field’s results are outside the reach of everything on the hero figure, and a reader budgeting for reproducibility should know which they are before spending anything.

The kernel cutoff. A library that switches from one accumulator to four at a length threshold is changing algorithm, not ordering, and no policy applied to either kernel makes the two agree. The step in the length that changes the kernel is a property of a version number.

The contraction. Whether a multiply-add was fused is decided at compile time, and both forms are conforming. A reproducible summation over products that were themselves rounded differently is reproducibly wrong in two different ways. One multiply the compiler removed is that measurement.

The algorithm. Two libraries computing a QR by Householder and by a tall-skinny tree return different numbers, both backward stable, and the difference is not an ordering at all — it is a reduction that changes the order, where the tree is the better of the two.

So the recommendation this figure supports is narrower than make everything reproducible. It is: identify the reductions a verdict is read from, price them against the work around them, and spend there. The rest of the program’s variability has other causes and other repairs.

Where the second pass stops being free #

One detail of the two-pass policy deserves its own paragraph, because it is the difference between a 3% cost and a 67% one in the table above, and it is not visible in either the operation count or the accuracy.

The second pass reads the vector again. If the vector fits in cache, that read is nearly free and the seven operations are what the policy costs. If it does not, the second pass is a second traversal of main memory, and on a memory-bound reduction that is a genuine doubling — the whole cost of the loop, paid twice, for a policy whose arithmetic is trivial.

The repair is to fuse the two passes: snap, accumulate, and accumulate the residue, all in one traversal, at the price of a second accumulator and a second δ that has to be fixed in advance rather than computed from the residues. Fixing it in advance costs accuracy — the residue’s largest element is not known until the first pass has run — so the fused version is a policy between the two, and which of the three is right depends on whether the data fits in cache.

That is the same arithmetic at a different price in miniature, and it is the reason this essay’s table is a table of operation counts with a warning attached rather than a table of times: the operation count is the same on every machine and the answer to which policy is not.

The comparison nobody runs #

A closing observation about why the figure is unusual rather than standard.

Every library that ships a reduction has measured its speed. Many have measured its accuracy against a reference. Almost none publish the third column, because the third column requires running the same input twice under different partitionings and comparing bits — which is not a benchmark, it is a test, and it lives somewhere else entirely from a timing.

The consequence is that the trade-off in the hero figure is not visible from any documentation. A caller choosing between two routines can find out which is faster and which is more accurate, and cannot find out which returns the same answer twice. That is the gap what a regression test can ask for measures from the consumer’s side, where the same missing column turns into a tolerance nobody can choose.

And it is the reason this field’s recommendation is stated in terms of the caller’s own data rather than in terms of a library’s. κ of the caller’s sum is computable in one pass; which reduction the library performed is not discoverable at all.

A note on the axis that is missing #

The figure has cost and accuracy on it and not the third property, because the third property is not a number: a policy either returns the same bits or it does not. That is why the reproducible ones are drawn as filled markers rather than as a third axis, and it is worth saying plainly, because the temptation to make it continuous is strong and produces nonsense.

How reproducible is not a quantity. The count of distinct answers over four hundred permutations — 303, 72, 119, 1, 1 in the sum that cannot be wrong — looks like one, and it is not: it is a property of the sample rather than of the policy, and a longer sample moves every number above one and none of the ones equal to it. The only honest reading of that column is binary, and the only honest way to draw it is a mark.

The same applies to the spread in ulps that the earlier essays report. It is a useful size, it predicts what a tolerance has to clear, and it is not a measure of reproducibility — a policy with a spread of two ulps is exactly as irreproducible as one with a spread of two million, and it will fail a bitwise test just as reliably. What the small spread buys is that a tolerant test can be written, which is the whole subject of what a regression suite can ask for.