Where the disagreement comes from

Two essays have now measured a disagreement without explaining it. This one explains it, in a sentence that turns out to carry everything the field needs:

A rounding is committed at every partial sum, and its size is the spacing of that partial sum, not of the answer.

Everything follows. The size of the disagreement, the fact that dividing the work reduces it, the fact that the value cannot be predicted, and the reason a vector of positive numbers shows nothing — all four are consequences of where the roundings are committed rather than of how many there are.

Reading the picture #

Two walks. They separate within the first handful of terms and never meet again, ending at 2.4·10⁻¹⁴ and 7.6·10⁻¹⁴ — a factor of three apart, on the same numbers, with the same algorithm.

Neither is a curve with noise on it. Each is a path: at every step the arithmetic commits one rounding of size at most half the spacing at the current running total, and adds it to what has accumulated. Sometimes the new rounding cancels part of what is there and the curve dips. Nothing about the path is deterministic in any useful sense, because it depends on the low bits of every partial sum.

The horizontal axis is where the mechanism is visible. This vector’s running total climbs to 52 on its way to an answer of 1.6·10⁻⁵. That is what a summation condition number of 10⁸ means in concrete terms: the arithmetic spends the entire computation handling numbers seven orders of magnitude larger than the one it returns, and rounds each of them at its scale rather than at the answer’s.

A rounding committed at a partial sum of 52 is worth about 5.8·10⁻¹⁵ in absolute terms. Relative to the answer of 1.6·10⁻⁵, it is worth 3.6·10⁻¹⁰. One rounding, in the middle of the loop, is already ten orders larger than the last bit of the result. There are 2,048 of them.

Why the answer’s own size is irrelevant #

This is the point at which the field parts company with the ordinary reading of floating-point error, so it is worth stating twice.

The usual mental model is that each operation contributes a relative error of about u to the answer, so n operations contribute about nu. That model is right when the running total stays near the answer — which is what a sum of positive numbers does, and why the order they are added in can talk about a million reciprocals losing accuracy in a way that is proportional to how many of them there are.

When the terms cancel, the running total is nowhere near the answer, and the errors are committed at a scale the answer never sees. The right model is that each operation contributes about u·|running total| in absolute terms, and the answer’s smallness is what turns those absolutes into enormous relatives. That is the same mechanism cancellation takes the answer describes for one subtraction, applied n times to a running total instead of once to a pair.

The consequence is that the number of terms almost drops out. Fix κ and vary the length: the relative error of a single-accumulator reduction is 4.2·10⁻⁹ at 128 terms and 3.1·10⁻⁹ at 8,192, a fitted exponent in n of −0.083. No power of n at all, where the classical bound carries a full one — which a bound every answer satisfies works out in detail, and which comes out of exactly the two square roots this essay is about.

The two square roots #

Written out once, because the cancellation of the two is what makes the whole field’s numbers small and stable.

The first √n is the roundings. They do not conspire. n roundings of similar size and independent sign accumulate like a random walk, reaching about √n times one of them rather than n times one of them. This is what the probabilistic error analysis of the last decade formalises, and it is why the deterministic bound’s factor of n is pessimistic by √n on any real data.

The second √n is the data. A vector of n mixed-sign terms with a fixed Σ|xᵢ| has entries of typical size Σ|xᵢ|/n, so its partial sums are themselves a walk and reach about √n · Σ|xᵢ|/n = Σ|xᵢ|/√n. The roundings are committed at that scale, which shrinks as the vector gets longer.

Multiply them: √n roundings, each of size u·Σ|xᵢ|/√n, gives u·Σ|xᵢ|. The length has gone. What is left is a quantity proportional to the sum of magnitudes, which divided by the answer is exactly κu — the constant this field reports, measured at 0.25 and derived here at 1.

The factor of four between the derivation and the measurement is honest and worth keeping: the derivation treats the roundings as independent and of full size, and they are neither. What the derivation buys is not the constant, it is the shape — no n, one κ, one u — and the shape is what survived ten decades of measurement at a spread of 1.02.

Why more workers is more accurate #

Now the consequence that surprises everybody, including the author of the refusal this essay publishes.

Each accumulator in a p-way reduction sees n/p terms, so its own walk reaches about Σ|xᵢ|/(p√(n/p)) · √(n/p) — shorter by √p than the single accumulator’s. The roundings committed inside it are smaller in proportion. The final combination of p partial sums adds log₂p more roundings, at the scale of the answer, which is negligible when the answer is small.

So a divided reduction should be more accurate by about √p. Measured over eight vectors at 2,048 terms:

A factor of 5.9 from one accumulator to sixty-four, where √64 = 8. The prediction is right in direction and within 25% in size over that range.

The improvement has an optimum #

Four partition counts can show a trend and not its end. Seven, with sixty-four vectors each:

It reverses. The improvement peaks near p = 64 and is back to 2.0 by p = 512, so past that point more workers is less accurate — the opposite of the conclusion above, applied past the range that produced it. And the exponent below the turn is −0.38 rather than −0.5, which is the right shape and the wrong power.

The turn has a location and a reason. Dividing the reduction moves the cancellation out of the accumulators and into the combination tree, and once an accumulator holds fewer terms than there are accumulators the tree is doing all of it. That puts the optimum at p ≈ √n, and it is there: the best partition count is 64 at n = 512, 64 at n = 2048 and 128 at n = 8192, against √n of 23, 45 and 91 — within one step of the doubling grid in every case, on a minimum shallow enough either side that the exact position is not the point.

And the peak partial sum is not the mechanism #

On a single vector it does not move at all, which is sharper than the averaged table can show.

The peak partial sum is the same number to three digits at every partition count. At p = 2, 4, 8, 16, 32 and 64 it reads 32.1, 32.1, 32.1, 32.1, 32.1 and 32.1, while the error at the end runs 1.13·10⁻¹³, 4.71·10⁻¹⁴, 2.41·10⁻¹⁴, 2.76·10⁻¹⁴, 2.41·10⁻¹⁴ and 2.74·10⁻¹⁵ — a factor of forty-one.

A quantity that does not move while the thing it supposedly explains moves by forty-one cannot be the explanation. On one vector the peak is fixed by the terms themselves — the largest partial sum any ordering reaches is a property of the multiset, not of how it was cut — so the averaged fall of 1.5 in the table below is an artefact of averaging over sixty-four different vectors whose peaks differ, and not a mechanism at all. Note also that two pieces is worse than one, at 1.13·10⁻¹³ against 7.56·10⁻¹⁴: the improvement does not even begin until p = 4.

The other half of that paragraph does not survive at all. The peak partial sum runs 53.8, 46.1, 38.9, 36.9, 36.6, 35.9, 36.0 — a fall of 1.5 across a 512-fold increase in p, with a fitted exponent of −0.06. It is flat. It is not falling alongside the error, which falls by 4.6 and then rises.

The reason is that the peak is a maximum over the accumulators, and a maximum is set by the largest terms rather than by the walk. A term of size 40 puts every accumulator that contains it above 40, whatever p is, so the peak cannot fall below the largest term however finely the work is divided. What falls with p is the typical running total inside an accumulator, and that is not the quantity the figure reports.

So the mechanism has to be read off the error alone, and read that way it says something the peak would have hidden: the gain is not “smaller partial sums” but “shorter walks”, and shorter walks stop helping when there are enough of them to make a long walk out of their answers.

That has a consequence for the field’s own headline, and it is worth stating because it runs the other way. The folk claim that parallel arithmetic is less accurate is backwards over the range a machine actually uses, and right in the limit. A reduction split across the cores of one machine — tens, or a few hundred — sits below √n for any vector worth reducing, and there the division helps. A reduction split across every lane of every core of a large machine, with a few terms each, is past the turn, and there it hurts.

Neither half of that is a statement about parallelism. Both are statements about how many terms an accumulator holds, which is a property of the schedule rather than of the hardware, and which a code can choose. The useful form of the rule is therefore not more workers is more accurate and not its negation: it is give each accumulator at least √n terms, which costs nothing to arrange and is the only number in this essay a programmer can act on.

This is the same fact a reduction that changes the order measures in the communication field, where a tall-skinny QR computed as a tree of independent block factorisations returns a better backward error than the sweep it replaces — 1.65·10⁻¹⁵ against 9.95·10⁻¹⁵. That essay reads the result as a statement about communication being free of a stability cost. Read from here it is the same √p: the tree’s local factorisations each see less of the matrix.

So the folk claim that parallel arithmetic is less accurate is not merely unproven, it is backwards. What parallel arithmetic is, is different — and different is the whole problem, because the consumer of the number is a comparison rather than a reader.

Why the value is unpredictable #

Everything above is a statement about the scale of the walk. None of it says where the walk ends.

That is not a gap in the analysis; it is the nature of the object. A random walk’s end point is not a function of its step sizes. Two walks with identical step-size distributions end in different places, and the difference between their end points has the same scale as either of them.

The practical consequence is the asymmetry this field lives with:

• the size of the disagreement is computable in advance, from data the caller has, at a cost of one pass;
• the answer any particular machine will return is not computable at all, short of running that machine.

Numerical analysis is usually in the opposite position — a worst case that is rarely attained, and an achieved error that is stable and reproducible. This is the one place on the site where the statistics are tight and the individual outcome is a coin flip.

Why sorting changes everything, and why nobody can #

The derivation above assumed the partial sums wander. Break that assumption and the mechanism gives a different answer, which is the strongest evidence that the mechanism is the right one.

Sort a vector by magnitude and the partial sums stop wandering: they climb monotonically, so the walk is a line and the errors accumulate in a line too. That is why sorting matters at all — the order they are added in measures a factor of 470 from sorting a million reciprocals — and it is why the factor of n comes back for sorted data.

For a positive vector, sorting ascending is the classical repair. For a cancelling vector it is worse than useless: sorting by magnitude puts all the positives before all the negatives, drives the running total to its maximum possible value, and maximises every rounding on the way. The best ordering for a cancelling sum is one that keeps the running total small, which means interleaving the signs — and that is a decision that has to be made about the data, by somebody who has seen it.

Which is precisely what a parallel runtime cannot do. It divides the vector by index, because index is all it has. The ordering that would help is one no scheduler is in a position to choose, and the orderings it does choose are drawn from the family whose end points are unpredictable.

The order of the data, which the runtime cannot see either #

There is a second ordering in play and it is easy to miss, because the field has spent three essays talking about the order the arithmetic combines things in. The terms also arrive in an order, and that one is the caller’s.

Take one vector and present it three ways to the same seven partitionings:

The third row is the one to read. Grouping by sign drives the running total to 839 — eighteen times the shuffled arrangement’s peak — because the sum climbs the whole way up and then comes the whole way down. Every rounding on that journey is committed eighteen times too large, and both the error and the run-to-run spread move by an order of magnitude.

Nothing about the arithmetic changed. The terms are the same multiset and the algorithm is the same algorithm; what changed is a property of the data’s layout, which in real code is decided by whatever assembled the vector — a sparse format, a sort somewhere upstream, the order the mesh was numbered in.

Two consequences worth carrying:

A benchmark on shuffled data understates the effect, which is the same warning the vector that hides it makes about positive data, one level down. Grouped signs are not exotic; they are what a physical problem with a source and a sink produces.

And this is why the ordering that would help cannot be chosen by the machine. Keeping the running total small means interleaving the signs, which requires having looked at the values. A runtime divides by index because index is all it has, so the one intervention that would shrink every rounding at once is available only to whoever built the vector — and available cheaply only to them, since a pass that inspects signs costs what the reduction costs.

What this predicts, checked #

A mechanism earns its place by predicting something it was not built to explain. Three predictions, all checked every time this page is produced:

A positive vector should show almost nothing. Its partial sums climb to the answer and stay there, so every rounding is at the answer’s scale and the relative error is a few nu. Measured: 1.6·10⁻¹⁵ across seven partitionings, against 4.9·10⁻⁷ on a cancelling vector at κ = 10¹⁰.

Compensated summation should be accurate and still irreproducible. Kahan’s loop removes most of each rounding but not all, and what is left is still committed at the running total’s scale. So the error should fall a long way and the count of distinct answers should not fall to one. Measured over four hundred permutations: 119 distinct answers, against 303 for a plain loop — three times better and not remotely reproducible.

The disagreement should be immune to a wider float. Every quantity in the derivation carries one factor of u, so doubling the precision moves everything down together and changes nothing about the shape. That is the prediction most often assumed away — use doubles is the standard advice, and it buys accuracy while buying no agreement, exactly as the tolerance that buys no agreement measures for a tolerance rather than for a format.

What it does not explain #

Two things, named because a mechanism that explained everything would be suspicious.

It does not explain the constant. The derivation gives u·Σ|xᵢ| and the measurement gives about a quarter of it. The gap is the independence assumption — consecutive roundings are correlated, because a partial sum that has just been rounded up is more likely to round down next — and recovering the constant would need a model of that correlation. The site’s habit is to report the measured number and to say which part of it was derived, which is what the direction the error leans does for a rounding mode: the size of one rounding is set by the precision, and how ten thousand of them combine is set by something else, with fitted exponents of 0.47 and 1.01 for two modes on identical data.

It does not explain the tail. The measurements here are means over seeds; the worst of twenty runs is about twice the mean and the analysis says nothing about how much worse a rare one can be. For a walk the answer is a Gaussian tail, and the honest version of that claim needs a distribution rather than a mean — which is the shape of statement the randomised field already makes, and a bound that holds with probability is where this site keeps its vocabulary for it.

The one line #

The error of a reduction is a walk over its own partial sums. What a machine changes is which walk, the length of the vector nearly cancels out of the answer, dividing the work shortens each walk and improves the average, and none of that says where any particular walk ends.