The same program, twice

Here is a claim that sounds like a definition rather than a measurement: a deterministic program, run twice on the same input, returns the same output twice.

It is false of almost every numerical library in use, and the reason is one line of arithmetic this site has already argued about. The order they are added in measures what non-associativity costs: a million reciprocals summed left to right are wrong in the third figure, and summed in a tree are wrong in the seventh. That essay treats the ordering as a decision — pick the tree, sort the terms, compensate — because in a serial program it is one.

In a parallel reduction nobody picks it. A runtime divides the vector across however many workers it has, each worker sums the piece it was given, and the pieces are combined as they arrive. The number of pieces is a property of the machine. The order of the combination is a property of the afternoon.

Twenty-six runs of one algorithm on one vector at one precision. Twenty-one of them returned different numbers. The vector’s summation condition number is 1.01·10⁸, the answers span 2.3·10⁷ ulps, and the exactly rounded sum — the one a correctly rounded algorithm would return, and which this site computes by Shewchuk’s expansion as a second route — is not any of them.

What is not going on #

Three readings of that figure are available and two of them are wrong, so it is worth closing them off before the field goes any further.

It is not a bug. Every one of those twenty-six runs performed the additions its source code specified, in binary64, with correct rounding at every step. There is no incorrect operation anywhere in the picture, and no implementation would be improved by fixing something.

It is not imprecision in the ordinary sense. The site’s whole vocabulary for a wrong answer is the exact answer to a nearby problem: a computation is judged by how large a perturbation of the data would make its answer exact. By that standard all twenty-six runs are excellent. Each is the exact sum of a vector within a rounding of the one it was given. They are all backward stable and they disagree.

And it is not rare. The figure’s vector is constructed, but the mechanism needs only two things — a reduction, and cancellation in it — and the fields before this one are full of both. A residual norm, an orthogonality check, a Gram matrix entry, a trace probe: every one is a sum with terms of both signs, and every one is computed by exactly the reduction drawn here.

The one number that decides how far apart they can be #

The quantity that governs it is not the length of the vector, not the precision, and not the number of workers. It is the summation condition number

κ = Σ|xᵢ| ÷ |Σxᵢ|,

the total size of what was added up divided by the size of what came out. It is a property of the data alone — no algorithm appears in it — and it is the factor by which cancellation magnifies every rounding committed along the way. A vector of positive numbers has κ = 1 exactly. The vector in the figure has κ = 10⁸ because it is built to, and a residual vector near convergence has whatever κ its problem gives it.

Vary it and nothing else, and two things move while a third does not.

The spread tracks κ and the disagreement does not. From κ = 100 to κ = 10¹⁰ the spread goes 22, 2,800, 3.6·10⁵ and 2.9·10⁹ ulps — about 0.3κ at every stop, which is the cancellation doing exactly what the definition says. What does not grow is the number of distinct answers: 15, then 21, then 20, then 20 out of 26. Past a hundred it saturates, because twenty-six orderings can only produce twenty-six answers and most of them are already distinct at κ = 10⁴. So κ decides how far apart the answers are and has almost nothing to say about how many there are, and a reader who has only ever seen the well-conditioned case has seen the wrong half of that.

Vary it and nothing else:

The measured spread and κu are one curve times a constant. Across ten decades the ratio between them runs from 0.253 to 0.258 — a spread of 1.02 while both quantities move by ten orders of magnitude. So the disagreement between machines is not a mysterious quantity: it is a quarter of κ·u, it is computable from the data before anything is run, and it is the thing to report beside a reduction whose value anyone is going to compare.

That constant is a fact about this family of vectors rather than a universal one — across seeds it moves between 0.20 and 0.52, and at 256 terms rather than 2,048 it is 1.4 times wider still, because a short reduction commits few enough roundings that one of them is a noticeable share of the total. What survives every version of the measurement is the proportionality, and it is the proportionality that makes the number useful.

Why a positive vector shows nothing #

The immediate consequence is a warning about measurement rather than about arithmetic.

Run the identical experiment on 4,096 positive numbers and the answers agree to a relative 1.6·10⁻¹⁵. Five of the runs still return distinct values — it is the same arithmetic, and nothing about positive data makes a reduction associative — but the disagreement is at the last bit and nobody would notice it. Run it on a vector with κ = 10¹⁰ and the disagreement is 4.9·10⁻⁷, which is three hundred million times larger.

That ratio is the whole reason this effect has a reputation for being a curiosity. Every quick demonstration of a parallel sum uses positive data, because positive data is what a synthetic benchmark generates, and positive data is the one family on which the phenomenon is invisible. A census of the reductions this site actually computes is the essay that takes that apart; the short version is that the sums with κ = 1 are the sums of squares, and nobody makes a decision from one.

The bound covers every answer, which is why it cannot help #

There is a bound for this, it is in every textbook, and it is correct. For a sum of n terms evaluated in any order,

|ŝ − s| ≤ γₙ₋₁ · Σ|xᵢ|,     γₙ = nu / (1 − nu).

Every one of the twenty-six answers satisfies it. That is not a compliment to the bound — it is the problem with it. The bound contains n and Σ|xᵢ| and nothing about the order, so it is the same number for all twenty-six runs, and a statement that is true of all of them cannot distinguish between them. It answers how wrong might this be and the question a reader now has is will the next run say the same thing, which is a different question with a different answer.

It is also loose by four orders of magnitude here: 2.58·10⁴ times the largest error any of the runs actually made — and that factor is the same at every conditioning, which is worth seeing.

The looseness is a property of the bound rather than a fact about this data. 2.47·10⁴ at κ = 100 and 2.58·10⁴ at 10⁴, 10⁶ and 10¹⁰ — eight decades of conditioning and the ratio moves by 4%. The reason it cannot depend on κ is visible in the two expressions: the bound is γₙ₋₁·Σ|xᵢ|, and the error actually committed is some multiple of u·Σ|xᵢ| decided by how the roundings happened to cancel. Both are proportional to Σ|xᵢ|, which is where all the κ lives, so it divides out and the ratio is left as a statement about n and about that cancellation — neither of which the conditioning touches. So refining an estimate of κ cannot tighten this bound by anything at all, which is the practical form of the objection: the quantity a reader would think to measure is exactly the one already accounted for. That looseness is not a flaw either — a worst-case bound over all orderings is attained by an ordering nobody runs — but it means the bound cannot even be used as a proxy. The disagreement is 0.25κu and the bound is 10⁴ κu, and between those two numbers there is a factor nobody can spend.

A bound every answer satisfies is the essay that makes this precise, because it is the point at which this field stops being an extension of the arithmetic field and starts being about something the identity has no term for.

Where it comes from, in one picture #

The mechanism is worth having, because it explains both the size of the disagreement and the fact that its value cannot be predicted.

A rounding is committed at every partial sum, and the size of that rounding is the spacing of the running total — not of the answer. On this vector the running total climbs to 52 on its way to an answer of 1.6·10⁻⁵, which is what a summation condition number of 10⁸ means concretely: the arithmetic spends the whole computation manipulating numbers eight orders of magnitude larger than what it returns, and each of them is rounded at its own scale.

So the error of a reduction is a walk, and its step length is set by how far the partial sums wander. Two partitionings are two different walks over the same terms. They separate at the first step and never meet again.

That reading also settles a question everybody asks in the wrong direction. Dividing the work improves the accuracy on average, because each accumulator’s walk is shorter: over eight vectors the mean error falls from 4.8·10⁻¹⁴ with one accumulator to 8.1·10⁻¹⁵ with sixty-four, a factor of 5.9 where √64 would predict 8. The parallel answer is not the worse one. It is a different one, and on average it is better.

But the end point of a walk is not a function of its step sizes. Predicting the size of the disagreement is easy and predicting which answer a given machine will return is not, and that asymmetry is the whole practical content of the field.

What actually changes between two runs #

Three things, and they are worth separating because only one of them is fixable by an instruction.

The number of pieces. Set by the thread count, which is set by the machine, the scheduler, the job manager or an environment variable somebody else exported. Pinning it is possible and is the first thing anybody tries.

The split points, at a fixed number of pieces. A work-stealing runtime hands out chunks as workers become free, so two runs of the same binary on the same machine with the same thread count divide the vector differently. Those are the open dots in the hero figure and they are the reason pinning the thread count is not by itself an answer.

The order of the combination. The partial sums are combined as they arrive, and which worker finishes first is not a property of the program at all.

The first is a setting, the second is a scheduling policy, the third is a race. Only the first is something a caller can control from outside, which is why “OMP_NUM_THREADS is pinned” is a partial answer that people reasonably mistake for a complete one.

The vocabulary this field needs #

The identity this site is built on has two terms in it, and two later fields added two more. Three errors and one number sets them out: the problem’s conditioning, the algorithm’s backward error, the reformulation, and the approximation. Every one of them is a statement about one computation and how far its answer is from the truth.

None of them has anything to say about a set of computations that are all correct and all different. The condition number is the same for every run here. The backward error is at rounding for every run. Nothing was reformulated and nothing was approximated. And yet twenty-one different numbers came back, and if a reader asks which of them their machine will produce, every quantity this site has built in nineteen fields is silent.

So the field needs two words that the others did not.

Run-to-run variation is the set of answers one computation has over the implementations of it that a machine might choose. It is measured as a spread rather than as an error, it is bounded by 0.25κu rather than by the classical bound, and it has no direction — none of the answers is the right one and the exact answer is usually not among them.

Bitwise reproducibility is the property of returning the same bits. It is not accuracy, it is not stability, and — as the sum that cannot be wrong measures — it is not implied by either. The two properties are independent, the cheapest way to buy the second costs three operations an element, and the most accurate policy on this page does not have it.

Why the disagreement matters at all #

A reader who has followed this far is entitled to the obvious objection: the answers differ in the eighth digit of a quantity nobody reads to eight digits. Who cares?

The answer is that a computed number is rarely the deliverable. It is compared with something.

A stopping test compares a residual with a tolerance. A rank test compares a singular value with a threshold. A definiteness test compares a pivot with zero. Each of those turns a real number into a verdict, and a verdict has no last digits for a disagreement to hide in. Two machines then do not return answers differing by 10⁻¹⁵ — they return different amounts of work, a different rank, and a different model. A stopping test is a race prices the first of those at 674 to 690 iterations for one solve; a rank that depends on the thread count shows one matrix with three different numerical ranks.

And the smallest instance of the whole field needs no parallelism whatever. A compiler is permitted to fuse a multiply and an add into one instruction with one rounding, from source that says nothing about it, and one multiply the compiler removed follows that single rounding to a 2 × 2 determinant whose value is one and which computes as zero.

What to do about it, stated once and early #

The field has four essays of measurement before it reaches a recommendation, so here is the recommendation in advance, since a reader who stops here should still have it.

Report κ of every reduction. It costs one pass over the data and it converts the answers might disagree into the answers will disagree by about a quarter of κu, which is a number a reader can act on.

That constant is worth pinning down, because the whole value of the recommendation is that it hands over a number. Relative spread across partitions p = 1…64, divided by κu, on the cancelling family:

Reading across: the ratio does not move with κ. Six decades of conditioning and the constant is the same to two digits, so spread = c·κu is the right form and the insight behind the recommendation holds exactly — κ really does convert a vague warning into a number.

Reading down: the constant falls with n, from 0.49 at 256 terms to 0.12 at 4,096. So a quarter is not the constant; it is a value near the middle of a range spanning a factor of four, and which end a reader is on depends on how long the reduction is. A quarter over-states the disagreement on a long sum and under-states it on a short one.

That the constant falls with n is worth a sentence, because the instinct runs the other way. More terms means more roundings and a larger absolute error — and it also means that any two partitions resemble each other more, since a reduction over four thousand elements in two blocks and in sixty-four blocks are both averaging over a great many terms. The disagreement between two schedules shrinks as each schedule sees more of the data.

And at κ near one the ratio inverts, coming out between 2.6 and 10.5 rather than a quarter. That is not the rule failing but its denominator vanishing — κu is then u, and a spread of a few units in the last place is several times it. The absolute spread there is 5.8·10⁻¹⁶ to 2.3·10⁻¹⁵, which is the case the last recommendation below already excludes.

Do not require bitwise agreement unless it has been bought. A regression test that demands identical bits fails on a correct build the first time the machine is busy, and a test that fails on correct builds is a test people delete. What a regression test can ask for measures the window: on one problem the tolerance has to be above 3.2·10⁻¹² and below 4.6·10⁻¹², a factor of 1.42, and it is neither zero nor the 10⁻⁸ that usually gets typed.

If a verdict is downstream, buy reproducibility. Order-independent summation exists, it is not exotic, and it costs between three and twelve operations an element depending on how much accuracy comes with it. What determinism costs prices all six policies on one figure.

And check whether the problem is the reduction or the cancellation. A well-conditioned solve is reproducible for the same reason it is accurate. If κ of the sums involved is near one, none of this applies, and the effort belongs somewhere else.

What this field is, in one line #

Every other field on this site asks how wrong an answer is. This one asks how many answers there are, finds that the number is not one, and then asks which of the things a program decides are decided by that.