4 ms·

A huge roadblock I recently ran into: It's possible, that floating operations may yield different results depending on the compiler or CPU architecture. As far

A huge roadblock I recently ran into: It's possible, that floating operations may yield different results depending on the compiler or CPU architecture. As far as I know it's not possible to run a simulation depending on floats on different machines, expecting the same output. Some people recommend switching to integer operations and to keep floating point arithmetic to a minimum. Is this the only way to get deterministic math across machines? http://gafferongames.com/networking-for-game-programmers/floating-point-determinism/ http://gafferongames.com/networking-for-game-programmers/flo... Edit: I ran into this while trying to procedurally generate a map based on a seed value. Heightmap, zones/biomes, rivers, towns, etc are all based on a seed. The result must be completely reproducible on different machines, otherwise players would see different maps. The terrain is large and therefore chunked. There's a seed per chunk and only seeds of chunks visible to the client are sent to him. I now believe that the only way to implement this correctly is passing the full, complete state of a chunk to the player after the generation. There's no sane way to implement the whole generation with integer math only. But there's a positive side-effect: More traffic but less performance needed to regenerate the chunk on the client. Actually it's simpler to work around this problem in a physics simulation, because the authoritative server can simply sync the properties across the players frequently.

pjc50 11y ago
You have to set compiler and runtime options to: - force IEEE compliance on - force Intel systems to disable extended-precision mode (80 bit internal registers) See e.g. http://stackoverflow.com/questions/6683059/are-floating-point-numbers-consistent-in-c-can-they-be http://stackoverflow.com/questions/6683059/are-floating-poin... Fixed-point integer is generally easier to handle but you have to do it "manually" as language support is scarce. And then watch out for overflow. It also may not be as fast as FP on modern systems (especially GPUs). Edit: one could write an alternate history where the first PC 3D accelerators were targeted at Quake and implemented fast fixed point. It was a common design decision for 3D engines. http://gamedev.stackexchange.com/questions/26823/why-did-the-old-3d-games-have-jittery-graphics http://gamedev.stackexchange.com/questions/26823/why-did-the... Arguably fixed-point's limitations are easier to understand. Floating will give you within epsilon of the "right" answer, but as we have seen this may vary in weird ways across platforms. Fixed will run into precision loss problems a lot earlier, forcing you to confront and deal with them. You also have to confront truncate vs. round earlier. A cite for "floating point is faster than fixed point": http://cboard.cprogramming.com/brief-history-cprogramming-com/4265-floating-point-faster-than-fixed-point.html http://cboard.cprogramming.com/brief-history-cprogramming-co...
- rurban 11y ago
  Mostly nonsense. You are making the same mistake as Matlab, throwing away all the internal Intel precision, just because you don't know the boundaries and limitations or you don't care. In short Matlab did as you said in v6.0 and it was wrong. Read Kahan and matlab's (non)"defense": http://www.cs.berkeley.edu/~wkahan/MxMulEps.pdf http://www.cs.berkeley.edu/~wkahan/MxMulEps.pdf http://blogs.mathworks.com/cleve/2014/07/07/floating-point-numbers/ http://blogs.mathworks.com/cleve/2014/07/07/floating-point-n...
  - nothrabannosir 11y ago
    So, do you have something we can learn from? As it stands, pjc50 has some on-point advice that directly addresses OPs concerns with consistent results from seed values, and testing. Your reply is: "that is nonsense." Great. Now I still know nothing.
  - pjc50 11y ago
    Extended-precision mode is a disaster because it's confined to the FPU. If it were an 80-bit datatype it wouldn't be a problem. Because of this property, it's only predictable if you write all your math in assembler. If you write C, the generated code is very vulnerable to perturbation when the compiler changes when variables are written back to memory. It may well give you more accurate results, but if you're doing something that's inherently numerically unstable (in our case, ASIC timing feeding into k-means clustering) it can give you different results in response to tiny code changes. Force-truncating trades accuracy for stability across changes to the software. And obviously if you want C code that gives the same results on Intel and non-Intel hardware, you can't use Intel 80-bit FPU. (Edit: I'll concede somewhat on "within epsilon of the right answer", because there are some examples in the Matlab case where 80 bit gets much closer to the right answer to 64-bit.)
  - brucedawson 11y ago
    If you want compatibility between x86 CPUs and ARM/PowerPC/MIPS then you have to not use the extended 80-bit results. The 80-bit results can be more accurate (although not always, it depends on exactly how they are used) but the OP wasn't concerned with maximum accuracy but with exact repeatability. Similarly, if you want cross-architecture consistency you need to not use fmadd instructions because fmadd gives different results from separate multiply and add. The fmadd results are more accurate, but that is not the point in this case.
toolslive 11y ago
I once ran into this with python. 2 interpreters giving different results. Turns out they compiled 1 interpreter with some --I-don-t-care-about-correct-flops-as-long-as-they-are-fast flags. Still traumatised.
exDM69 11y ago
The important question to ask is: do you really need bit-accurate results? If so, then floating point arithmetic isn't probably what you want. However, running the same binary on different (compatible, ie. not ARM vs. x86) CPU architectures should produce identical results almost always (can anyone give a counterexample?). But in reality, it is often acceptable to have one or two least significant bits differing. Especially when computing with doubles, a relative error in the order of 2^-53 = ~10^-16 isn't really significant. Even 32 bit floats give a precision of 2^-24 = 5*10^-8. This is usually good enough for e.g. games, although multiplayer games need some kind of authoritative server model to avoid cheating. Finally, the x87 floating point unit shouldn't be used any more because SSE2 is ubiquitous at this point so issues with 80 bit internal precision should be a thing of the past. I'll conclude with a link to an article about a (very) competitive sim racing game where a least significant bit in a float ended up making a practical difference: http://www.iracing.com/q-circles-the-crop-circles-of-iracing/ http://www.iracing.com/q-circles-the-crop-circles-of-iracing...
- mortoray 11y ago
  I'm not sure 80-bit floats are a thing of the past. Many calculations still benefit from the extended precision compared to 64-bit. The issue also crops up agian on some platforms that can do 128-bit float, but are then truncated down to 64-bits for storage. I agree there are ways to avoid that problem, but the general issue of truncation across storage/calculation I think remains an important concept.
  - exDM69 11y ago
    > Many calculations still benefit from the extended precision compared to 64-bit. Out of curiosity, can you name some examples? 64 bit doubles are really precise, to give a practical figure: a 64 bit float is good enough to calculate the orbit of Neptune to a precision of half a millimiter (0.497 mm). That's a distance of about 30 AU = 4.5 * 10^12 m = four and a half billion kilometers. > The issue also crops up agian on some platforms that can do 128-bit float, but are then truncated down to 64-bits for storage. Which CPU architectures use 128 bit floats internally? Is it common to use such platforms? What comes to x87, I'd imagine that the difference in speed in comparison to SSE is already a good enough reason to not use 80 bit floats in most practical applications. Perhaps some nuclear simulations or particle accelerator physics deal with numbers that vary in magnitude so greatly that increased precision may be useful but these cases are really rare (albeit important).
alkonaut 11y ago
This is the case for example with the x86 .NET jit. The problem is usually when values are moved to 64bit locations rather than keeping them in 80bit fpu registers. This was a huge headache our regression tests for a .NET engineering/FEM application. .NET has no option to force "strict" FPU mode so there is no way of getting reproducible results. What saved us was that the x64 JIT uses only 64 bit, which makes it deterministic.
vhffm 11y ago
There's an additional caveat that may be of interest. If you execute code in parallel, you may pick up different round-off errors unless you take care to combine the results from parallel tasks in the same order every time. This can be a problem when simulating non-linear dynamical systems (such as the Solar System).
brucedawson 11y ago
It's not impossible, it's just hard. I covered the things you have to worry about a while ago in this article: https://randomascii.wordpress.com/2013/07/16/floating-point-determinism/ https://randomascii.wordpress.com/2013/07/16/floating-point-... As long as you avoid unspecified instructions (reciprocal square-root estimate, fsin) and avoid library functions or code-gen that takes different paths when SSE2/AVX/whatever are available and as long as you run the same binary on every machine (compatibility between PowerPC and x86 is much harder) you can definitely do it. Many games have. So, if you can restrict yourself to x86 CPUs it's manageable, at least for modest sized chunks of code.

pjc50 11y ago

You have to set compiler and runtime options to: - force IEEE compliance on - force Intel systems to disable extended-precision mode (80 bit internal registers) See e.g. http://stackoverflow.com/questions/6683059/are-floating-point-numbers-consistent-in-c-can-they-be http://stackoverflow.com/questions/6683059/are-floating-poin... Fixed-point integer is generally easier to handle but you have to do it "manually" as language support is scarce. And then watch out for overflow. It also may not be as fast as FP on modern systems (especially GPUs). Edit: one could write an alternate history where the first PC 3D accelerators were targeted at Quake and implemented fast fixed point. It was a common design decision for 3D engines. http://gamedev.stackexchange.com/questions/26823/why-did-the-old-3d-games-have-jittery-graphics http://gamedev.stackexchange.com/questions/26823/why-did-the... Arguably fixed-point's limitations are easier to understand. Floating will give you within epsilon of the "right" answer, but as we have seen this may vary in weird ways across platforms. Fixed will run into precision loss problems a lot earlier, forcing you to confront and deal with them. You also have to confront truncate vs. round earlier. A cite for "floating point is faster than fixed point": http://cboard.cprogramming.com/brief-history-cprogramming-com/4265-floating-point-faster-than-fixed-point.html http://cboard.cprogramming.com/brief-history-cprogramming-co...

rurban 11y ago
Mostly nonsense. You are making the same mistake as Matlab, throwing away all the internal Intel precision, just because you don't know the boundaries and limitations or you don't care. In short Matlab did as you said in v6.0 and it was wrong. Read Kahan and matlab's (non)"defense": http://www.cs.berkeley.edu/~wkahan/MxMulEps.pdf http://www.cs.berkeley.edu/~wkahan/MxMulEps.pdf http://blogs.mathworks.com/cleve/2014/07/07/floating-point-numbers/ http://blogs.mathworks.com/cleve/2014/07/07/floating-point-n...
- nothrabannosir 11y ago
  So, do you have something we can learn from? As it stands, pjc50 has some on-point advice that directly addresses OPs concerns with consistent results from seed values, and testing. Your reply is: "that is nonsense." Great. Now I still know nothing.
- pjc50 11y ago
  Extended-precision mode is a disaster because it's confined to the FPU. If it were an 80-bit datatype it wouldn't be a problem. Because of this property, it's only predictable if you write all your math in assembler. If you write C, the generated code is very vulnerable to perturbation when the compiler changes when variables are written back to memory. It may well give you more accurate results, but if you're doing something that's inherently numerically unstable (in our case, ASIC timing feeding into k-means clustering) it can give you different results in response to tiny code changes. Force-truncating trades accuracy for stability across changes to the software. And obviously if you want C code that gives the same results on Intel and non-Intel hardware, you can't use Intel 80-bit FPU. (Edit: I'll concede somewhat on "within epsilon of the right answer", because there are some examples in the Matlab case where 80 bit gets much closer to the right answer to 64-bit.)
- brucedawson 11y ago
  If you want compatibility between x86 CPUs and ARM/PowerPC/MIPS then you have to not use the extended 80-bit results. The 80-bit results can be more accurate (although not always, it depends on exactly how they are used) but the OP wasn't concerned with maximum accuracy but with exact repeatability. Similarly, if you want cross-architecture consistency you need to not use fmadd instructions because fmadd gives different results from separate multiply and add. The fmadd results are more accurate, but that is not the point in this case.

toolslive 11y ago

I once ran into this with python. 2 interpreters giving different results. Turns out they compiled 1 interpreter with some --I-don-t-care-about-correct-flops-as-long-as-they-are-fast flags. Still traumatised.

exDM69 11y ago

The important question to ask is: do you really need bit-accurate results? If so, then floating point arithmetic isn't probably what you want. However, running the same binary on different (compatible, ie. not ARM vs. x86) CPU architectures should produce identical results almost always (can anyone give a counterexample?). But in reality, it is often acceptable to have one or two least significant bits differing. Especially when computing with doubles, a relative error in the order of 2^-53 = ~10^-16 isn't really significant. Even 32 bit floats give a precision of 2^-24 = 5*10^-8. This is usually good enough for e.g. games, although multiplayer games need some kind of authoritative server model to avoid cheating. Finally, the x87 floating point unit shouldn't be used any more because SSE2 is ubiquitous at this point so issues with 80 bit internal precision should be a thing of the past. I'll conclude with a link to an article about a (very) competitive sim racing game where a least significant bit in a float ended up making a practical difference: http://www.iracing.com/q-circles-the-crop-circles-of-iracing/ http://www.iracing.com/q-circles-the-crop-circles-of-iracing...

mortoray 11y ago
I'm not sure 80-bit floats are a thing of the past. Many calculations still benefit from the extended precision compared to 64-bit. The issue also crops up agian on some platforms that can do 128-bit float, but are then truncated down to 64-bits for storage. I agree there are ways to avoid that problem, but the general issue of truncation across storage/calculation I think remains an important concept.
- exDM69 11y ago
  > Many calculations still benefit from the extended precision compared to 64-bit. Out of curiosity, can you name some examples? 64 bit doubles are really precise, to give a practical figure: a 64 bit float is good enough to calculate the orbit of Neptune to a precision of half a millimiter (0.497 mm). That's a distance of about 30 AU = 4.5 * 10^12 m = four and a half billion kilometers. > The issue also crops up agian on some platforms that can do 128-bit float, but are then truncated down to 64-bits for storage. Which CPU architectures use 128 bit floats internally? Is it common to use such platforms? What comes to x87, I'd imagine that the difference in speed in comparison to SSE is already a good enough reason to not use 80 bit floats in most practical applications. Perhaps some nuclear simulations or particle accelerator physics deal with numbers that vary in magnitude so greatly that increased precision may be useful but these cases are really rare (albeit important).

alkonaut 11y ago

This is the case for example with the x86 .NET jit. The problem is usually when values are moved to 64bit locations rather than keeping them in 80bit fpu registers. This was a huge headache our regression tests for a .NET engineering/FEM application. .NET has no option to force "strict" FPU mode so there is no way of getting reproducible results. What saved us was that the x64 JIT uses only 64 bit, which makes it deterministic.

vhffm 11y ago

There's an additional caveat that may be of interest. If you execute code in parallel, you may pick up different round-off errors unless you take care to combine the results from parallel tasks in the same order every time. This can be a problem when simulating non-linear dynamical systems (such as the Solar System).

brucedawson 11y ago

It's not impossible, it's just hard. I covered the things you have to worry about a while ago in this article: https://randomascii.wordpress.com/2013/07/16/floating-point-determinism/ https://randomascii.wordpress.com/2013/07/16/floating-point-... As long as you avoid unspecified instructions (reciprocal square-root estimate, fsin) and avoid library functions or code-gen that takes different paths when SSE2/AVX/whatever are available and as long as you run the same binary on every machine (compatibility between PowerPC and x86 is much harder) you can definitely do it. Many games have. So, if you can restrict yourself to x86 CPUs it's manageable, at least for modest sized chunks of code.