Creating invariant floating-point accumulators(solidpixel.github.io) |
Creating invariant floating-point accumulators(solidpixel.github.io) |
The question here with association for summation is what you want to match. OP chose to match the scalar for-loop equivalent. You can just as easily make an 8-wide or 16-wide "virtual vector" and use that instead.
I suspect that an 8-wide virtual vector is the right default for people currently, since systems since Haswell support it, all recent AMD, and if you're using vectorization, you can afford to pay some overhead on Arm with a double-width virtual vector. You don't often gain enough from AVX512 to make the default 16-wide, but if you wanted to focus on Skylake+ (really Cascadelake+) or Genoa+ systems, it would be a fine choice.
Isn't it the other way around? The scalar for-loop was changed to match the vector loop's associativity. "To solve this problem for astcenc I decided to change our reference no-SIMD implementation to use 4-wide vectors."
There is still some flexibility in implementation, for example how and whether FMAs are formed for a given compiler when FP_CONTRACT is ON, and in the standard itself in things like when tininess is detected.
But to your point if you stick to the basic operations in the standard, and don’t enable FP_CONTRACT and FENV_ACCESS in C/C++, have a bug free compiler and don’t use fast-math, you’re good to go.
[edit to add a caveat about compile-time constant folding which is a whole can of worms]
[edit again to point out that the C/C++ standards allow for implementations to compute intermediate results at higher precision, so a compliant implementation can use all 80 bits on x87 when computing expressions]
If the data confined to a certain range of exponents, one could reduce the size of the accumulator, perhaps significantly.
Re 4-8x -- the large option in xsum was benchmarked at less than 2x the cost of a direct sum. Not so bad?
It seems to me that non associative floating point operations force us into a local maximum. The operation itself might be efficient on modern machines, but could it be preventing us from applying other important high level optimizations to our programs due to its lack of associativity? A richer algebraic structure should always be amenable to a richer set of potential optimizations.
---
I've asked a question that is very much related to that topic on the programming language subreddit:
"Could numerical operations be optimized by using algebraic properties that are not present in floating point operations but in numbers that have infinite precision?"
https://www.reddit.com/r/ProgrammingLanguages/comments/145kp...
The responses there might be interesting to some people here.
Floats are mostly for when you need that dynamic range.
You're always welcome to use a weaker notion of associativity than bitwise equality (e.g., -ffast-math pretends many operations are associative to reorder them for speed, and that only gives approximately correct results on well-conditioned problems).
In general though, yes, such a limit does exist. Imagine, for the sake of argument, an xxx.yyy fixed-point system. What's the result of 100 * 0.01 * 0.01? You either get 0.01 or 0, depending on where you place the parentheses.
The general problem is in throwing away information. Trashing bits doesn't necessarily mean your operations won't be associative (imagine as a counter-example the infix operator x+y==1 for all x,y). It doesn't take many extra conditions to violate associativity though, and trashed bits for addition and multiplication are going to fit that description.
How do you gain associativity then? At a minimum, you can't throw information away. Your fast machine operations use an unbounded amount of RAM and don't fit in registers. Being floating-point vs fixed-point only affects that conclusion in extremely specialized cases (like only doing addition without overflow -- which sometimes applies to the financial industry, but even then you need to think twice about the machine representation of what you're doing).
That's an interesting perspective that I haven't considered before, thank you.
Now I'm wondering, could we throw away some information in just the right way and still maintain associativity? That is, it doesn't seem like throwing information away is fundamentally what's preventing us from having an associative operation, since we can throw information away and still maintain associativity by, for example, converting each summand to a 0 and adding them, and that operation would be associative. However, we would have thrown all information away, which is not useful, but we would have an associative operation.
That is, the physicist writes the two line equation they want for electromagnetic force into their program, the same way they'd write a for-each style loop in the program if that's what they needed.
Obviously the CPU doesn't understand how to compute the appropriate approximation for this electromagnetic force equation, but nor does it understand how to iterate over each item in a container. Tools convert the for-each loop into machine code, why shouldn't other, smart, tools convert the physicist's equation into the FP instructions ?
Today the for-each loop thing just works, loads of programming languages do that, if a language can't do it (e.g. C) that's because it is old or only intended for experts or both.
But every popular language insists that physicist should laboriously convert the equation into the code to compute an approximation, which isn't really their skill set, so why not automate that problem?
... are you not aware of -ffast-math? There are several fast-math optimizations that are basically "assume FP operations have this algebraic property, even though they don't" (chiefly, -fassociative-math assumes associative and distributive laws hold).
> Re 4-8x -- the large option in xsum was benchmarked at less than 2x the cost of a direct sum. Not so bad?
I don't know where you did take that number, because xsum-paper.pdf clearly indicates larger performance difference. I'm specifically looking at the ratio between the minimum of any superaccumulator results and the minimum of any simple sum results, and among results I think relevant today (x86-64, no earlier than 2012), AMD Opteron 6348 is the only case where the actual difference is only about 1.5x and everything else hovers much higher.
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
the problem is it's marginally useful, since everyone expects number
Like many things in javascript it's a bit cursed but it does work.