21–30 of 31 posts
Earlier quoted context omitted.
Plus 53-bit indices exceed the amount of memory that many 64-bit architectures can address (x86_64 is 48 bits, ARM is either 48 or 52 bits).
x86-64 is 57 bits these days https://en.wikipedia.org/wiki/Intel_5-level_paging
This seems to keep coming up, and I see confusion in the comments. There is a standard: IEEE 754-2008. There are additional things people add like approximate reciprocals and approximate sqrt. But if you don't use those, and you don't make an association error, you get consistent results. The question here with association for summation is what you want to match. OP chose to match the scalar for-loop equivalent. You…
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."
I'm still wondering if there could exist an alternative world where efficient addition over decimal numbers that we developers use on a day to day basis is associative. Is that even possible or is there perhaps some fundamental limit that forces us to trade associativity for performance? It seems to me that non associative floating point operations force us into a local maximum. The operation itself might be efficien…
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).
Earlier quoted context omitted.
x86-64 is 57 bits these days https://en.wikipedia.org/wiki/Intel_5-level_paging
Thanks for the correction! TIL.
Exact floating point accumulating is more or less solved with xsum [1] -- would it work in this context? [1] https://gitlab.com/radfordneal/xsum
This seems to keep coming up, and I see confusion in the comments. There is a standard: IEEE 754-2008. There are additional things people add like approximate reciprocals and approximate sqrt. But if you don't use those, and you don't make an association error, you get consistent results. The question here with association for summation is what you want to match. OP chose to match the scalar for-loop equivalent. You…
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]
Exact floating point accumulating is more or less solved with xsum [1] -- would it work in this context? [1] https://gitlab.com/radfordneal/xsum
Because it would be slower when the exact calculation is not necessary. The xsum paper does have performance numbers, but all of them came from at least decade-old processors and almost every result indicates that superaccumulators are still 4--8x slower than the simple sum (but faster than the traditional Kahan summation). Superaccumulators require extensive scatter-gather operations due to its large memory footprin…
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?
Seems crazy to try to paper over hardware implementation differences in software. Some org should be standardizing floating point intrinsics
Earlier quoted context omitted.
Because it would be slower when the exact calculation is not necessary. The xsum paper does have performance numbers, but all of them came from at least decade-old processors and almost every result indicates that superaccumulators are still 4--8x slower than the simple sum (but faster than the traditional Kahan summation). Superaccumulators require extensive scatter-gather operations due to its large memory footprin…
My takeaway from the linked post is that the author is more concerned with floating point invariance across platforms than speed (although improvements in speed are of course welcome). 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?
> 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.