5 ms·
Why Bitwise Reproducibility Matters
- yarvin9 11y agoIt seems clear that if we hadn't inherited a bunch of irreproducible languages and/or instruction sets from the 20th century, no one would bother creating a new one. There are certainly some ways to get optimization advantages from underspecified computation, but especially in a networked world this win is outweighed by the problems it causes. 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/floating-point-determinism/ http://gafferongames.com/networking-for-game-programmers/flo...
- varelse 11y agoNeither 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.
- yarvin9 11y agoYou 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.
- varelse 11y agoTo 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.
- yarvin9 11y agoYou can do a lot with single-threaded actors. You're right - it's not that hard, for certain values of "hard." Working on it... :-)
- dibanez 11y ago
- RyanZAG 11y agoThe 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...
- varelse 11y agoAs 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.
- RyanZAG 11y agoAccording 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?
- varelse 11y agoNo, 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.
- ArkyBeagle 11y agoSo 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.
- dnautics 11y ago.wav encodes amplitude data in what is essentially an integer representation (well, it's a fixed point float, but anyways).
- ArkyBeagle 11y agoSure. 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.
- jmnicholson 11y agoHere is another piece by the author "Reproducibility, replicability, and the two layers of computational science " https://thewinnower.com/papers/reproducibility-replicability-and-the-two-layers-of-computational-science https://thewinnower.com/papers/reproducibility-replicability...
- JesperRavn 11y agoI 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.
- yarvin9 11y agoNot 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?
- JesperRavn 11y agoIt'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.
- jtchang 11y agoI'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.
- deleted 11y ago[deleted]
- littlewing 11y ago"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.
- dnautics 11y agoJohn Gustafson's unums are an effort to introduce a scheme for bitwise reproducible floats.
- yarvin9 11y agoOMG I love this guy and need to have his babies immediately. Some links: http://www.vrworld.com/2015/03/24/the-evils-of-floating-point-and-the-joys-of-unum/2/ http://www.vrworld.com/2015/03/24/the-evils-of-floating-poin... http://sites.ieee.org/scv-cs/files/2013/03/Right-SizingPrecision1.pdf http://sites.ieee.org/scv-cs/files/2013/03/Right-SizingPreci...
- dnautics 11y agoI'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.
- jacobolus 11y ago> there is one part about it that really sucks Don’t leave us hanging! What is the part that really sucks?
- dnautics 11y agoThe 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.