5 ms·

It 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

by yarvin9 11y ago

It 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 ago
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.
- yarvin9 11y ago
  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.
  - varelse 11y ago
    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.
    - yarvin9 11y ago
      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... :-)
- dibanez 11y ago
  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.
  - varelse 11y ago
    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.
    - reality_czech 11y ago
      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).
RyanZAG 11y ago
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...
- varelse 11y ago
  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.
  - RyanZAG 11y ago
    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?
    - varelse 11y ago
      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.
ArkyBeagle 11y ago
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.
- 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 ago
    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.

by yarvin9 11y ago

varelse 11y ago

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.

yarvin9 11y ago
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.
- varelse 11y ago
  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.
  - yarvin9 11y ago
    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... :-)
dibanez 11y ago
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.
- varelse 11y ago
  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.
  - reality_czech 11y ago
    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).

RyanZAG 11y ago

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...

varelse 11y ago
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.
- RyanZAG 11y ago
  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?
  - varelse 11y ago
    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.

ArkyBeagle 11y ago

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.

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 ago
  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.