How can floating point calculations be made deterministic?

by

Floating-point is deterministic. The same floating-point operations, run on the same hardware, always produces the same result. There is no black magic, noise, randomness, fuzzing, or any of the other things that people commonly attribute to floating-point. The tooth fairy does not show up, take the low bits of your result, and leave a quarter under your pillow.

Now, that said, certain blocked algorithms that are commonly used for large-scale parallel computations are non-deterministic in terms of the order in which floating-point computations are performed, which can result in non-bit-exact results across runs.

What can you do about it?

First, make sure that you actually can’t live with the situation. Many things that you might try to enforce ordering in a parallel computation will hurt performance. That’s just how it is.

I would also note that although blocked algorithms may introduce some amount of non-determinism, they frequently deliver results with smaller rounding errors than do naive unblocked serial algorithms (surprising but true!). If you can live with the errors produced by a naive serial algorithm, you can probably live with the errors of a parallel blocked algorithm.

Now, if you really, truly, need exact reproducibility across runs, here are a few suggestions that tend not to adversely affect performance too much:

  1. Don’t use multithreaded algorithms that can reorder floating-point computations. Problem solved. This doesn’t mean you can’t use multithreaded algorithms at all, merely that you need to ensure that each individual result is only touched by a single thread between synchronization points. Note that this can actually improve performance on some architectures if done properly, by reducing D$ contention between cores.

  2. In reduction operations, you can have each thread store its result to an indexed location in an array, wait for all threads to finish, the accumulate the elements of the array in order. This adds a small amount of memory overhead, but is generally pretty tolerable, especially when the number of threads is “small”.

  3. Find ways to hoist the parallelism. Instead of computing 24 matrix multiplications, each one of which uses parallel algorithms, compute 24 matrix products in parallel, each one of which uses a serial algorithm. This, too, can be beneficial for performance (sometimes enormously so).

There are lots of other ways to handle this. They all require thought and care. Parallel programming usually does.

More Related Contents:

  1. error: incompatible types for a function that returns float in C
  2. How do I restrict a float value to only two places after the decimal point in C?
  3. Dividing 1/n always returns 0.0 [duplicate]
  4. How to represent FLOAT number in memory in C
  5. What operations and functions on +0.0 and -0.0 give different arithmetic results?
  6. What is the instruction that gives branchless FP min and max on x86?
  7. Checking if float is an integer
  8. What happens to a float variable when %d is used in a printf?
  9. Representing integers in doubles
  10. Why is printf round floating point numbers up?
  11. What is the fastest way to convert float to int on x86
  12. Casting float to int (bitwise) in C
  13. Why does adding a small float to a large float just drop the small one?
  14. Comparing floating point numbers in C
  15. Comparing float and double in C
  16. Can I make gcc tell me when a calculation results in NaN or inf at runtime?
  17. Is it safe to assume floating point is represented using IEEE754 floats in C?
  18. Count number of digits after `.` in floating point numbers?
  19. Status of __STDC_IEC_559__ with modern C compilers
  20. Is there a tool to know whether a value has an exact binary representation as a floating point variable?
  21. problems in floating point comparison [duplicate]
  22. Is fmod() exact when y is an integer?
  23. Trouble with float on C [duplicate]
  24. When does underflow occur?
  25. Serialize double and float with C
  26. C printf using %d and %f
  27. Comparing float and double
  28. Is there a document describing how Clang handles excess floating-point precision?
  29. clang 14.0.0 floating point optimizations
  30. Conditional tests in primality by trial division

Leave a Comment