Why Bitwise Reproducibility Matters
thewinnower.com
thewinnower.com
When you use irreproducible floating-point, you're essentially treating your CPU as an analog computer. For a subset of very specialized numerical applications, this is probably okay. For any kind of integration with interesting, non-numerical system software (let alone scientific publishing!), it's a disaster.
I always recommend this link on FP determinism: http://gafferongames.com/networking-for-game-programmers/flo...
In fact, FP32 is commutative (go ahead, check it out). It's just not associative. If you can't figure out how to reduce sums of FP32 numbers in a deterministic manner, you suck, no that's too weak, you really suck. And your complete lack of numerical analysis has turned a digital computing problem effectively into an analog nightmare you'll never debug. HPC people love to use this excuse for why their parallel code isn't deterministic, but it turns out that making it so is effectively free in an age of fast RDMA and INT64 atomics.
To be fair, there are situations where noisy non-deterministic inputs (cameras, microphones, and other sensors) are part of the deal. However, if given simulated deterministic examples of inputs, your result isn't deterministic, you still suck. That said, I'm willing to relax the constraint to assume reproducibility given the same HW/compiler/toolchain so I think the naysayers are pretty much out of excuses here.
I speak from experience. And the efforts I've made to achieve bitwise reproducibility in HPC algorithms are dismissed as "engineering" by the people who can't do so.
I've decided to take that as a compliment.
I'm just saying, like OP, that this work shouldn't be needed. You should get this result for free and not even have to think about it.
The instruction sets certainly aren't irreproducible and I shouldn't have implied that, although there are plenty of IEEE extensions not well-standardized (eg, transcendentals). The problem is that their specifications grow weaker as you move up the programming hierarchy. Optimizers rearranging algebra, etc. And the result that's presented to the normal programmer is that floating-point is analog computing.
As for the second part, one needs a great deal more thought into the definitions of transcendentals before proceeding. The 22-bit mantissa approximations of transcendentals on GPUs are fantastic for most scientific computing and machine learning applications. Any error they introduce is more than offset by errors introduced by the assumptions that led to those algorithms in the first place.
(1)We agree that the farther you move up the programmer hierarchy, the harder it is to make a reproducible algorithm. My solution is to defy the trend and implement the bowels of the hierarchy, but I'd be happy for a computer scientist to design something from the ground up that was bitwise-reproducible (and please please strongly typed so it's L1-friendly without doing functional programming backflips to make it so). I really don't think it should be that hard given how easily and repeatedly I have done so from the guts outward.
You're right - it's not that hard, for certain values of "hard." Working on it... :-)
This is worse for our codes because our mesh structure changes topology based on floating point comparisons, so error in values turns into different discrete structures.
Parallelism introduces more headaches, making some codes non-deterministic between runs on the same machine, although I've been able to fix this for the most part.
Its important to break down "determinism" into consistency across changes in something, whether it be hardware or time or partitioning.
Unless the timings themselves are non-deterministic, sigh. But then I'm far more sympathetic. I have not found this sort of thing to be the case for the most part and when I have, I've used a deterministic measure rather than timing (i.e. number of calculations as opposed to how long they take).
For even compiler revisions are sufficient to break FP32 associativity let along different transcendental approximations (we ought to fix that, no?).
Where I get angry is when people sloppily use FP32 for everything or FP64 because it's double(tm) and then insist determinism isn't possible. That isn't even science IMO.
A lot of machine learning tools like random forests and neural networks inherently inject randomness. Are we just going throw up our hands and say we only use classical deterministic algorithms run in single threaded mode, because we can't think of any way to compare multiple test runs except memcmp? Because that's what I'm hearing (maybe I'm missing something).
But parallel code is how one continues to benefit from Moore's law w/r to multiple cores and ever-increasing SIMD width and SIMD units. And it happened at exactly the same time as the migration to mostly single-threaded weakly-typed languages began.
For if your results aren't reproducible, there's no way to detect if your code has a race condition that is reducing the efficacy of your methods.
For an application like molecular dynamics, it's important to conserve overall energy. Any such inconsistency is the equivalent of setting off tiny little hand grenades in the simulation. Inconsistent summation obscures this without a great deal of work to sample many independent simulations. Compare and contrast to running things twice to sniff this out in deterministic code.
For machine learning, it can amount to anything from a harmless implicit regularizer to the AI equivalent of Gary Busey taking the wheel and driving you straight to crazy town.
I speak from experience in both cases. And speaking from experience, as long as your reductions are associative, you'll be fine. That can be achieved with fixed point atomics, or if you don't have them, reduction buffers, or finally, a deterministic reduction algorithm if you have neither. I've used all of the above and they have at most cost 2-3% more than the non-deterministic alternatives (usually much less).
Finally, I inject randomness like crazy, but I do so in a reproducible manner. Confusing determinism and randomness reminds me of people who don't understand the difference between precision and accuracy (TLDR: precision is easy, accuracy is tough).
You are right that deterministic pseudo-random numbers can be used when "random" inputs are required. I overlooked that... thanks for pointing it out.
Do this a few times until you've characterized what's happening and your brain figures out how and why by seeing the pattern this will (hopefully) reveal.
In this day and age, I suspect the latency issues would be unnoticeable on a 10 Mb/s or better router (which is to say any LAN party) but this was done in the mid-90s.
This was years ago, and I may still have been using 16 bit samples. It would be worth repeating this for 16 bit, 24 bit and 32-but float sample sets.
That's not bad.
Hopefully developers don't misinterpret this to mean that it is idiotic or overly obsessive about performance to use floating point types in calculations. That's not true.
As an example, I once decided to use double-precision floating-point in calculations that would accumulate enough accuracy error that I had to do approximate equality conditions throughout the parts of the code that determined these solutions. This not involve monetary amounts, and we needed solutions in a few seconds, not 20-30 seconds. Each step in the solution built on the former, so I could not break it up any more to solve in parallel than it already was. Throwing faster hardware at it wasn't an option available at the time. I still think I did the right thing, and it's still an integral part of production. Just going with the standard "just use BigDecimal because it's accurate" approach would have been a mistake.
http://www.vrworld.com/2015/03/24/the-evils-of-floating-poin...
http://sites.ieee.org/scv-cs/files/2013/03/Right-SizingPreci...
One interesting thing, John and I had an argument about the implementation, because there is one part about it that really sucks. Eventually he admitted that it had rankled him too and that the reason why he made this design choice was so that float64 could bitwise map smoothly onto unum{4,6} and float32 onto unum{4,5}... And that people would actually refuse to use unums if not for this direct bitwise mapping! So I capitulated.
Don’t leave us hanging! What is the part that really sucks?
And which part would that be? I'm mostly asking out of curiosity, so don't put yourself out if the answer is too long and involved.
As someone who has implemented a couple FPUs, I can assure you that there are quite a few pieces of IEEE 754 that suck to implement.
I would love to have floating point decimal on embedded systems rather than a binary floating point unit. But the libraries are generally huge.
I use the equivalent of decimals WAY more on embedded hardware. User entry is always decimal. Percentages--decimal. Time specifications--milliseconds, microseconds, nanoseconds--decimal with precision.
I wind up writing integer fixed-point arithmetic versions of this crap, over and over and over.
Maybe since Moore's law broke and memory transistors are now way more expensive that processor transistors, we'll get decimal floating point as a feature soon.
I won't hold my breath, though.
We only store to hundredths ... oops ... new regulations require us to decimal round to thousandths. Cue full reload of the database with all your numbers in them.
Or, even better, try dealing with mm and mils in the same CAD database simultaneously. (conversion factor of 25.4--a clean number in decimal but very much not in binary)
In addition, you forget that simply adding decimals doesn't work in binary floating point. Adding 0.10 10 times doesn't equal 1.00 in binary floating point no matter how much precision you use.
Do we really expect everyone who does linear regression to say "I did linear regression, using the following implementation of a linear solver". Because that's what is being asked.
A much better alternative is to test that algorithms give expected answers (within some tolerance) on simulated but non-trivial data. It will still require some care to distinguish bugs from rounding errors, but it is more, er realistic, than expecting bitwise reproducibility.
Maybe the optimization is important. In that case, couldn't you add another layer devoted to that special case? For instance, reorder matrix multiplies in a source-to-source transformation? Put leap seconds in the presentation layer, not the chronology layer?
Everyone who does linear regression for the purposes of publishing a scientific paper should post their code and data, so that anyone else can recompute it and get the same bits. How is this controversial in 2015?
What do you mean by "reorder matrix multiplies in a source-to-source transformation?" To be clear, the issue is that matrix multiplication (which forms the basis for a huge part of numerical computing) is only deterministic when the order of operations is known. But any kind of fast algorithm is going to have a highly complex order of operations that depends on the algorithm and parameters. You can't reorder these back to some canonical order without completely changing the algorithm (and destroying its performance gains).
Given the above, posting code and data won't be enough for binary reproducibility. Source code for every dependency would be needed too.
As I noted I do support testing and reproducibility, just not at the level of binary data.
This is a classic source-to-source transformation problem. You have an abstract matrix multiplication algebra which needs to be converted into a deterministic algorithm with a known order of operations. You need a second algorithm, essentially a macro, which converts the abstract operation into the concrete operations, which are then compiled to deterministic code.
This macro should itself be deterministic, even if its inputs contain information about local hardware configuration that's needed to make the optimized code run as fast as possible. If this information is in your data set, it's in your data set. Optimization is typically much less important to the reproduction pass, so a reproduction will probably just use your configuration details rather than those matched to the reproducer's machine.
Either way, both algorithms are deterministic and the result is reproducible. What's wrong with this picture? I ask because I genuinely want to know :-)
[Edit: it's disappointing to see "disagree == downvote" applied to the parent.]
Also we have the problem of what is "right"? Maybe your first implementation does (a+b)+c, then someone finds doing (a+c)+b gives a more accurate answer. Should we change?
Then you are given two CPUs. If I want to do x1 + x2 + ... + xn, then obvious thing to do is going to be to give each CPU half the input data. But now however I split will give me a (slightly) different answer.
With matrix multiplication this is much worse -- all algorithms chop the matrix into little pieces in different ways, each giving a slightly different answer. Even if you try to define some plain simple algorithm, it will usually give a less accurate answer, due to how the floating point rounded!
With integer matrices on finite fields, it is much easier to get what you want, 100% reproducability.
Suppose CPU count is the configuration input. Then you have a deterministic macro function M(nCPU, abstract program) => concrete program. And another deterministic function C(concrete program) => CPU instructions.
Now nCPU is no longer a random piece of information randomly found in your environment: it's data in your data set. And your results are bitwise reproducible.
With a reproducible toolchain, I can use a 1-CPU machine to get the same results as you did on your 32-CPU machine, by using the same data set (including your nCPU=32). Why? Because I'm reproducing your results and I care more about precision than performance.
For what I am proposing, keeping track of the major versions of dependencies should be enough.
See also sibling comment.
Yes, reproducibility requires source code for the entire dependency graph, down to a set of bootstrap binaries. This is what tools such as GNU Guix and Nix allow you to do. They enable reproducible science.
My original point is that the complexity of dealing with differing environments and code versions, combined with the sensitivity of floating point results on the exact source code and environment, practically kills the possibility for exact reproducibility.
That's why I'm claiming that a better goal is approximate reproducibility.
So a sufficient improvement in toolchains/package management etc. would probably enable bitwise reproducibility, but I think a lot of people in this thread, and the original article, were implying that current tools are sufficient and scientists just need to stop being lazy.
My article argues that infrastructure tools (compilers, runtimes, ...) should ensure bitwise reproducibility, making it possible for a programmer to define a computational result exactly through a program's source code.
This does not mean that we can't have different algorithms. It doesn't even mean that no compiler could ever re-arrange operations for optimization. The latter could well be enabled through a compiler option.
All I am asking for is that infrastructure tools leave all these choices to the programmer.