4 ms·

Floating Point Determinism

47 points by wallflower 15y ago

deleted 15y ago
[deleted]
- jerf 15y ago
  "vocabulary of the title/premise is a little misguided." What, "Floating Point Determinism"? Seems like what was discussed in great detail to me. How much more explanation of exactly what he meant are you looking for exactly? Your criticism rings very hollow.
  - Someone 15y ago
    I cannot read the original post, as it is deleted, but I may agree with it. Most random number generator are 100% deterministic. Yet, if I take two on two systems, I cannot guarantee that both produce the same sequence. And no, seeding does not guarantee that, at least GNU does not think so: http://www.gnu.org/s/hello/manual/libc/ISO-Random.html http://www.gnu.org/s/hello/manual/libc/ISO-Random.html states: — Macro: int RAND_MAX The value of this macro is an integer constant representing the largest value the rand function can return. In the GNU library, it is 2147483647, which is the largest signed integer representable in 32 bits. In other libraries, it may be as low as 32767. Barring bugs (a problem that the writer does not touch) floating point arithmetic should be deterministic. Problem is that different machine may determine to produce different results, given the same inputs.
- fleitz 15y ago
  Run some FP calculations on an AMD CPU and then an Intel CPU you'll get slightly different results. In 3D rendering for movies they use all the same CPU because otherwise you get weird colorspace distortions between frames.
  - psykotic 15y ago
    > Run some FP calculations on an AMD CPU and then an Intel CPU you'll get slightly different results. Are you saying that the exact same x87 or SSE instruction sequence will yield different results on AMD vs Intel? As far as I know that isn't true and would be a very serious CPU bug.
    - edge17 15y ago
      IEEE 754 floating point isn't associative
      - psykotic 15y ago
        Next you are going to tell me the moon isn't made out of cheese. No, really, that's why I said I was talking about a specific machine code instruction sequence.
    - vilhelm_s 15y ago
      IEEE specifies exact rounding for +,-,*,/ and sqrt, but it allows the transcendental functions to be inaccurate in the least significant bit (creating a fast exact algorithm for these is apparently quite hard). At one job, we were running our test suite on both Pentium4 and Athlon machines, and got into trouble because the exp() function returned different values about once every 10,000 numbers. We changed the regression tests to add a fuzz factor to the floating-point comparisons.
      - edge17 15y ago
        yea, I've encountered this before while diffing outputs of two versions of the same thing (like a testbench to compare behavioral code vs netlist vs c simulation). In fact, this is one of the challenges in doing relational databases on gpu hardware. With relational databases you want to make sure the result of the same query is the same across every run. Relational databases are otherwise perfect use cases for gpu type of parallelization - i.e. running large numbers of parallel, read-only lockless operations without cross dependencies (for the most part, for most relatively simple queries)
      - 15y ago
fleitz 15y ago
Just look at the source code for Quake. There is a solution in there, and it's about running the simulation on only one computer that computer makes the final decision on how soft body physics affects gameplay. Use the fast path for all non affective physics and send a sync once in a while for affective physics. Also, you can run your simulation on integer math that does have deterministic results. Incidentally it's probably how the universe works too. Quantum physics specifies that units (quanta) are not infinitely divisible. Even frequency of light shouldn't be infinitely divisible if you consider the quanta of time to be the speed of light over the planck length. All you need to do is send definite updates on object locations frequently enough that the error is not significant enough to be noticeable by players. In network game play the overriding error problems stem from network lag rather than FP divergence. For the most part it does not matter that your player is .001 millimeter from where they should be. Everyone who has sniped in Team Fortress knows that you have to lead your target a little for 'lag'. Ostensibly this is because the bullet takes time to travel, but realistically probably stems from lag. In all honesty just write the game using whatever running on whatever and if it looks realistic it's probably good enough. If you really can't solve the problem find a guy in creative to augment your story line to match the weirdness in your physics simulation.
- psykotic 15y ago
  The issue of floating-point determinism only really comes up in lock-step networking where you are in effect simulating a distributed state machine. Rather than continually transmitting the current state, you synchronize the state at startup and afterwards transmit only actions. In an RTS, where lock-step networking is still most commonplace, an action might be "order unit to move from A to B". In this context determinism is absolutely paramount, because any mismatch in the simulation between clients will compound itself over time, so even if the divergence starts small, it will soon grow to be very large. Whereas with client-server networking, as in Quake, a mismatch in the floating-point specifics between clients will only manifest self as a constant level of error. The error does not contaminate the simulation since it's client-side only, and the server is authoritative. The issue of latency is totally unrelated and something intrinsic to the workings of distributed systems.
mml 15y ago
Tl;dr: FP operations can be non deterministic across different systems, architectures and compilers unless you take great care, and know exactly what you are doing. This is widely applicable in multiplayer game programming.
extension 15y ago
I used to develop for the classic Gameboy which used a serial cable to connect two units for multiplayer. The serial port could exchange exactly one byte per frame, simultaneously in both directions. That was just enough to send the input state for the frame (U,D,L,R,A,B,Select,Start = 8 bits) from each device to the other. So, this sort of blind deterministic simulation was the only option. Identical hardware and predictable latency made this somewhat easier, but it was still devilishly tricky to get right. The simulation had to not be affected by which player is local and which is remote. That's a tall order for 8-bit assembly language on a 1MHz CPU.
JonnieCache 15y ago
Is this stuff ever an issue for people doing financial modelling?
dylanrw 15y ago
While authored a long time ago, this is a great article for the early game developer. Hopefully Glenn will continue writing awesome intro/theory, and giving talks.

47 points by wallflower 15y ago

deleted 15y ago

[deleted]

jerf 15y ago
"vocabulary of the title/premise is a little misguided." What, "Floating Point Determinism"? Seems like what was discussed in great detail to me. How much more explanation of exactly what he meant are you looking for exactly? Your criticism rings very hollow.
- Someone 15y ago
  I cannot read the original post, as it is deleted, but I may agree with it. Most random number generator are 100% deterministic. Yet, if I take two on two systems, I cannot guarantee that both produce the same sequence. And no, seeding does not guarantee that, at least GNU does not think so: http://www.gnu.org/s/hello/manual/libc/ISO-Random.html http://www.gnu.org/s/hello/manual/libc/ISO-Random.html states: — Macro: int RAND_MAX The value of this macro is an integer constant representing the largest value the rand function can return. In the GNU library, it is 2147483647, which is the largest signed integer representable in 32 bits. In other libraries, it may be as low as 32767. Barring bugs (a problem that the writer does not touch) floating point arithmetic should be deterministic. Problem is that different machine may determine to produce different results, given the same inputs.
fleitz 15y ago
Run some FP calculations on an AMD CPU and then an Intel CPU you'll get slightly different results. In 3D rendering for movies they use all the same CPU because otherwise you get weird colorspace distortions between frames.
- psykotic 15y ago
  > Run some FP calculations on an AMD CPU and then an Intel CPU you'll get slightly different results. Are you saying that the exact same x87 or SSE instruction sequence will yield different results on AMD vs Intel? As far as I know that isn't true and would be a very serious CPU bug.
  - edge17 15y ago
    IEEE 754 floating point isn't associative
    - psykotic 15y ago
      Next you are going to tell me the moon isn't made out of cheese. No, really, that's why I said I was talking about a specific machine code instruction sequence.
  - vilhelm_s 15y ago
    IEEE specifies exact rounding for +,-,*,/ and sqrt, but it allows the transcendental functions to be inaccurate in the least significant bit (creating a fast exact algorithm for these is apparently quite hard). At one job, we were running our test suite on both Pentium4 and Athlon machines, and got into trouble because the exp() function returned different values about once every 10,000 numbers. We changed the regression tests to add a fuzz factor to the floating-point comparisons.
    - edge17 15y ago
      yea, I've encountered this before while diffing outputs of two versions of the same thing (like a testbench to compare behavioral code vs netlist vs c simulation). In fact, this is one of the challenges in doing relational databases on gpu hardware. With relational databases you want to make sure the result of the same query is the same across every run. Relational databases are otherwise perfect use cases for gpu type of parallelization - i.e. running large numbers of parallel, read-only lockless operations without cross dependencies (for the most part, for most relatively simple queries)
    - 15y ago

fleitz 15y ago

Just look at the source code for Quake. There is a solution in there, and it's about running the simulation on only one computer that computer makes the final decision on how soft body physics affects gameplay. Use the fast path for all non affective physics and send a sync once in a while for affective physics. Also, you can run your simulation on integer math that does have deterministic results. Incidentally it's probably how the universe works too. Quantum physics specifies that units (quanta) are not infinitely divisible. Even frequency of light shouldn't be infinitely divisible if you consider the quanta of time to be the speed of light over the planck length. All you need to do is send definite updates on object locations frequently enough that the error is not significant enough to be noticeable by players. In network game play the overriding error problems stem from network lag rather than FP divergence. For the most part it does not matter that your player is .001 millimeter from where they should be. Everyone who has sniped in Team Fortress knows that you have to lead your target a little for 'lag'. Ostensibly this is because the bullet takes time to travel, but realistically probably stems from lag. In all honesty just write the game using whatever running on whatever and if it looks realistic it's probably good enough. If you really can't solve the problem find a guy in creative to augment your story line to match the weirdness in your physics simulation.

psykotic 15y ago
The issue of floating-point determinism only really comes up in lock-step networking where you are in effect simulating a distributed state machine. Rather than continually transmitting the current state, you synchronize the state at startup and afterwards transmit only actions. In an RTS, where lock-step networking is still most commonplace, an action might be "order unit to move from A to B". In this context determinism is absolutely paramount, because any mismatch in the simulation between clients will compound itself over time, so even if the divergence starts small, it will soon grow to be very large. Whereas with client-server networking, as in Quake, a mismatch in the floating-point specifics between clients will only manifest self as a constant level of error. The error does not contaminate the simulation since it's client-side only, and the server is authoritative. The issue of latency is totally unrelated and something intrinsic to the workings of distributed systems.

mml 15y ago

Tl;dr: FP operations can be non deterministic across different systems, architectures and compilers unless you take great care, and know exactly what you are doing. This is widely applicable in multiplayer game programming.

extension 15y ago

I used to develop for the classic Gameboy which used a serial cable to connect two units for multiplayer. The serial port could exchange exactly one byte per frame, simultaneously in both directions. That was just enough to send the input state for the frame (U,D,L,R,A,B,Select,Start = 8 bits) from each device to the other. So, this sort of blind deterministic simulation was the only option. Identical hardware and predictable latency made this somewhat easier, but it was still devilishly tricky to get right. The simulation had to not be affected by which player is local and which is remote. That's a tall order for 8-bit assembly language on a 1MHz CPU.

JonnieCache 15y ago

Is this stuff ever an issue for people doing financial modelling?

dylanrw 15y ago

While authored a long time ago, this is a great article for the early game developer. Hopefully Glenn will continue writing awesome intro/theory, and giving talks.