Why Bitwise Reproducibility Matters(thewinnower.com)
thewinnower.com
Why Bitwise Reproducibility Matters
https://thewinnower.com/papers/954-why-bitwise-reproducibility-matters
47 comments
Neither the instruction sets nor floating point are irreproducible at all. What are you talking about?
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.
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 also work in HPC and have been doing a better job of this but still struggling in some areas. For example, the sin() and cos() implementations are different on some machines, and their only guarantee is being within some ulp of the right answer. So far haven't come up with a rounding idea that will make those values the same again.
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.
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.
If your parallel reductions are consistent, you're cool in my book. That said, I've solved a lot of dynamic load-balancing behavior with 64-bit fixed point reductions and decisions. Maybe that will work for you?
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.
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.
I don't understand the obsession with bitwise reproducibility. It seems like if your algorithm is numerically stable and valid, you can just compare multiple inexact test runs with some margin of error. Even if you hire nothing but guru-level IEEE floating point experts, a focus on bitwise reproducibility will close off a lot of opportunities to parallelize the code.
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).
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).
Moore's Law w/r to clock frequency ran out over a decade ago. And that sucks, because it's trivial to make single-threaded code reproducible.
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).
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).
I've seen race conditions that only happen 1 time in 1000. Or race conditions that only happen when the machine is under load. I agree that it's frustrating to have to debug non-deterministic code, but I feel like there must be a better way to compare test runs than memcmp on the resutls.
You are right that deterministic pseudo-random numbers can be used when "random" inputs are required. I overlooked that... thanks for pointing it out.
You are right that deterministic pseudo-random numbers can be used when "random" inputs are required. I overlooked that... thanks for pointing it out.
One way I addressed this exact situation: Compute a hash on the state after each iteration and save it. Now run again normally and save several iterations worth of state somewhere. When the hash diverges, you have hit the race condition.
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.
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.
Dunno from obsession, but I like having a regression suite available, and bitwise reproducible means you can run the test suite as if it were a "diff", and no output means it passed.
You make my point exactly. It is possible to get deterministic floating point out of existing toolchains. It requires work. Sure, people who can't do that work suck, for certain values of the word "suck."
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.
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.
To get this for free (for various values of the word "free"), you'd have to encapsulate reduction across arbitrary distributions of processes and threads. Good luck with that(1)...
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.
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 can do a lot with single-threaded actors.
You're right - it's not that hard, for certain values of "hard." Working on it... :-)
You're right - it's not that hard, for certain values of "hard." Working on it... :-)
So if you go get FFTW, build it into a program on a PeeCee, then round-trip a .wav file ( .wav=>FFT; FFT->.wav ) you get your original file back.
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.
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.
.wav encodes amplitude data in what is essentially an integer representation (well, it's a fixed point float, but anyways).
Sure. They're constrained to 0...1 . But there are a lot of floating point operations per FFT, and it can be shown that they are invertible.
The issue of determinism for games is interesting with many games trying to compile to javascript to run in the browser. Wouldn't this break multiplayer for those kind of games? You're stuck with double precision optimized floating point when targeting javascript...
As long as there is one true arbiter of the game state, I can't see how. The default these days is to have a master server, but back in the day, I developed a distributed server state that let each node determine the true state of its local inhabitants whilst the others performed a glorified predictor/corrector (with frequent corrections) of those that were non-local. In that model, state is unambiguous and deterministic.
According to the linked article, transferring the full game state is too large - such as for SupCom where the game state is huge. Instead, they only pass player input. I guess that says for a Javascript game, you must always pass the full game state?
No, you can pass the controller states and timestamps to whichever node is acting as its server. You then extrapolate everywhere else until a correction arrives from the server. It worked magnificently and we used to watch efficiency improve up to 4 consoles and then gradually decline due to increasing latency. Never patented any of this, have at it, we have scads of prior art if anyone tries to do so :-)...
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.
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.
"The reason is a mixture of widespread ignorance about floating-point arithmetic and the desire to get maximum performance."
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.
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.
I've never had to write a RTS game but fp determinism sounds like a nightmare. I can imagine someone clicking a button and not having it do the same thing every time. I'd be cursing the platform all the way down.
Here is another piece by the author "Reproducibility, replicability, and the two layers of computational science
" https://thewinnower.com/papers/reproducibility-replicability...
[deleted]
John Gustafson's unums are an effort to introduce a scheme for bitwise reproducible floats.
This is cool, but we can't seem to get floating point decimal jammed into languages. And that has an immediate business case.
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.
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.
Fixed-precision is much better for business uses. What, exactly is the benefit of floating point decimal? If you want to divide a $100 venmo three ways, you get to know that your 1/3 is carried to 12 decimal places instead of 2?
Fixed-precision is fine. Until your quantum isn't good enough.
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.
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.
OMG I love this guy and need to have his babies immediately. Some links:
http://www.vrworld.com/2015/03/24/the-evils-of-floating-poin...
http://sites.ieee.org/scv-cs/files/2013/03/Right-SizingPreci...
http://www.vrworld.com/2015/03/24/the-evils-of-floating-poin...
http://sites.ieee.org/scv-cs/files/2013/03/Right-SizingPreci...
I'm currently working on a Julia implementation of unums that supports environments {0,0} -> {6,11}. It will be public soon (next few weeks or so). I'm finished with addition, subtraction, multiplication, and division is not done (I'm working on it today), but the division algo works quite nicely. It is however, really slow (about 40x slower than bigfloat)...
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.
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.
> One interesting thing, John and I had an argument about the implementation, because there is one part about it 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.
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.
> there is one part about it that really sucks
Don’t leave us hanging! What is the part that really sucks?
Don’t leave us hanging! What is the part that really sucks?
The spec has an asymmetric exponent bias. IEEE floating points have an asymmetric exponent bias - for example float64 has 1022 bias (symmetric would be a 1023 bias). Because of the properties of unums, the universal representation of the value 1 is subnormal, and subnormals are tricky to deal with. If unums had symmetric exponent biases, then there would not be multiple representations of one.
Given that floats are already bitwise reproducible (provided the compiler is appropriately shackled), what does this idea add to reproducibility?
I strongly disagree. Bitwise reproducibility would make it impossible to change or improve matrix multiplication algorithms, since the order of operations matters, and will change across implementations.
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.
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.
Your comment is a nice example of the frequent misunderstandings concerning bitwise reproducibility.
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.
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.
Not to be too harsh, but this seems like the kind of thinking that leads to solutions like the leap second. For the sake of an optimization in an important but specialized corner case, you abandon a general principle of universal applicability (repeatable computing, chronological time).
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?
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?
It's not harsh to me, since you are critiquing the work of some of the best experts in the world, not me.
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.
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.
Yes, source code for every dependency is needed too!
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.]
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.]
The main problem is that with floating point numbers, (a+b)+c is different to a+(b+c), so almost any change can produce slightly different answers.
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.
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.
Let me say the same thing perhaps more clearly: there isn't any nondeterminism here, just failure to capture the inputs and outputs of a deterministic code transformation.
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.
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.
In principal there is nothing wrong with what you say, it's just that you need to now keep track of every possible change to the code and the environment.
For what I am proposing, keeping track of the major versions of dependencies should be enough.
See also sibling comment.
For what I am proposing, keeping track of the major versions of dependencies should be enough.
See also sibling comment.
[deleted]
> Source code for every dependency would be needed too.
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.
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.
I don't think the effort needed for this is worth it. Most scientists even ones who code, don't even know what bootstrap binaries are.
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.
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.
In a way we're arguing past each other: you're saying that approximate reproducibility is realistically the best scientists can do with today's toolchains. I'm saying that programmer's writing tomorrow's toolchains should do better. It seems at least possible that we could both be right :-)
Yes, I agree that the issue is in the toolchain. And more reproducibility in this area is a much more general and important problem. Even without aiming for bitwise reproducibility, it's still very hard to properly package your software and its dependencies. That is one reason why reproduction is so rare: simply installing the dependencies is too hard.
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.
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.
And you're completely wrong.
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...