1
\$\begingroup\$

I've been designing a distributed procedural generation system for a while now in my spare time and one of the problem's I've been thinking about recently, with respect to the broader architecture, is that of floating point determinism inconsistency when you can't ensure that you have a homogeneous cluster of machines running a persistent world.

Part of my design requires that any given machine can regenerate procedural content as needed, allowing for unimportant but resource-hungry content to be destroyed and recreated as needed on whatever machine is available to do the work.

I have been running on the basic idea that I will use high-precision 32/64 bit integers for most things, and that generally works fine, but the standard coherent noise algorithms all use floating point values in their calculations.

  • Do I need to implement custom non-floating-point versions of all those algorithms (i.e. using longs) or is there a better approach?
  • Should I be using fixed-point types for this kind of thing, and if so, how does that impact my desire to have the option to offload some of the PCG work to the GPU, when possible? Also, are fixed point types fast enough for heavy use within a game engine?
  • Can I ignore floating point precision issues if I can get away with a maximum level of precision? i.e. If I'm happy to use no more than, say, six decimal places of a result, does that keep me safe across different machines and architectures?

Note: my engine is purely the simulation side of things. It doesn't matter to me if there are slight rendering inconsistencies when a user is playing the game; all that matters is that the procedurally-generated source data is consistently regenerated no matter which machine in a cluster is doing the work.

\$\endgroup\$
  • \$\begingroup\$ One way to ensure determinism is to reduce the bit precision by yourself, so that you match the lowest precise platform : expl -> 16 bits : x_fp16 = floor( x * 65536) / 65536. But then you'll have to call such a function on each computation, which might be both slower and harder to code. \$\endgroup\$ – GameAlchemist Feb 13 '16 at 13:38
  • \$\begingroup\$ Yeah I think I might have to ask this one (restructured as a general dev question) on StackOverflow... not getting many bites here. \$\endgroup\$ – Nathan Ridley Feb 14 '16 at 8:41
3
\$\begingroup\$

Can I ignore floating point precision issues if I can get away with a maximum level of precision? i.e. If I'm happy to use no more than, say, six decimal places of a result, does that keep me safe across different machines and architectures?

This depends entirely on your needs. If you must ensure that repeat execution on different hardware with identical inputs gives identical outputs, the answer is probably no. There's enough wiggle room in floating-point arithmetic that without extensive testing, this approach amounts to guess & hope. The oft cited required reading is What Every Computer Scientist Should Know About Floating-Point Arithmetic; it's a good piece & what I often turned to back when I was doing scientific computing, but predates IEEE 754-2008 & thus may no longer give the whole story.

Should I be using fixed-point types for this kind of thing, and if so, how does that impact my desire to have the option to offload some of the PCG work to the GPU, when possible?

Fixed point only solves the inconsistency problem if you can ensure things don't cross over into floating point either in your own code or behind your back in library calls.

Also, are fixed point types fast enough for heavy use within a game engine?

Somewhat covered in this question & more recently in this article. The short answer is, it depends. The operations you're performing, the frequency you perform them, the hardware being used & a quantitative performance expectation are all factors in determining if it's good enough. If you must ensure output consistency, you might have no other viable option.

Do I need to implement custom non-floating-point versions of all those algorithms (i.e. using longs) or is there a better approach?

Most languages have libraries for fixed point math. It might be worth searching for distributed scientific computing resources.

As something of an alternative, you might consider building some sort of checksum operation for the outputs that need ensured consistency. This doesn't solve the original problem, but does allow you a way to determine if the problem is manifesting itself in you system. (I.E. quickly determine mismatched outputs). It's entirely possible that it will happen so rarely that it's not worth the trouble to prevent the problem, but easier to deal with by reconciling differing results.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for the detailed answer. In retrospect, I think my question would have been better presented as something like this: "given two different machines, if one is chosen at random to do work while the other is unavailable for verification, and the work involves generating procedural terrain from a standard coherent noise algorithm, and then generating a data set based on physics-based collisions with the terrain, how can I ensure that both machines produce identical results that can be relied upon as the basis for derivative data at a later date?". I suspect the answer would be "I can't". \$\endgroup\$ – Nathan Ridley Feb 15 '16 at 0:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.