Beating Floating Point at Its Own Game: Posit Arithmetic [pdf]
johngustafson.net
johngustafson.net
What a strange claim. Outputting a NaN is easier than raising an interrupt, or could be done within an interrupt, and detecting a NaN input requires a handful of gates or less.
This is not to say that NaNs are a good or bad method, but they're definitely not expensive to implement.
> posits lack a separate ∞ and −∞ [...] “negative zero” is another defiance of mathematical logic that exists in IEEE floats.
I will note that the IEEE standard almost had a projective infinity mode, and x87 has that mode.
> floats are asymmetric and use those bit patterns for a vast and unused cornucopia of NaN values
If we want to ignore languages like javascript and lua, sure.
These guys have never allreduced a timestep in a simulation where something can go aphysical.
I mean, sure, one can communicate aphysical conditions using out-of-band means. But it is so pretty when it just rides along for free as a NaN result.
Edit: I stand corrected having looked up authors. I still think having float effectively be Maybe[float] is a feature not a bug.
A closer analogue of NaN might be the x ("unknown") value in the three/four-valued logic of hardware simulation languages like Verilog. But the situation in Verilog, despite its challenges, is so much better since you don't have a hard discontinuity between "numbers" and "logical values". Numerical comparisons between unknowns can produce unknown logical values, and you have equations like true & unknown = unknown, true | unknown = true, ~unknown = unknown, etc, so you don't have the issue with NaNs where as soon as something crosses from the floating-point realm to the integer or logical realm, it has to commit to a definite value, with all the aforementioned issues.
All that said, NaNs were the right design choice given the constraints. But it's far from ideal.
I saw him explain that in float, there a too many bit representations that amount to "NaN". According to a Stack Overflow I found:
"IEEE 754 standard defines 16,777,214 32-bit floating point values as NaNs, or 0.4% of all possible values."
That's "expensive" in terms of losing bits of expressiveness that could have been used to represent actual numbers.
Cost of a Interrupt: 100 ns to 1 microseconds (Quora) Sorry, that solution is simply not interesting for most implementations where floats are used. There are sensors which in realtime hammer out so many values, that not using NaNs means dropping part of your sensor values.
This is a classic case of re-inventing a optimal wheel (fine for racing) and not really looking at the use-cases (not fine for a lot of normal day to day driving).
Im sure it will bring the groupies on conferences.
That sounds like the time it takes to do a context switch to the OS. A math error interrupt doesn't need to do a context switch. The cost doesn't need to be any higher than a branch misprediction at 10-20 cycles.
Thanks for putting it right, before the missinformation could spread.
The double precision floating point format already represents between 15 and 17 significant digits, and those who, for some reason, believe they need more expressiveness can already use the illusive and rarely needed 80-bit extended precision floating point format.
0.4% of anything is nothing.
Or is that exception hard to implement?
That doesn't help if the result could be partially valid, but if a "square root of minus one" or similar anywhere in the calculation means the result is invalid (and would be a NaN under floating point), sticky error bits in a status register could be sufficient.
https://github.com/interplanetary-robot/SigmoidNumbers/blob/...
That's probably why the recent RISC-V architecture doesn't even give the option of raising an interrupt on floating point errors ("As allowed by the standard, we do not support traps on floating-point exceptions in the base ISA, [...]"). Going even farther, it also doesn't raise an interrupt on integer divide by zero (https://content.riscv.org/wp-content/uploads/2017/05/riscv-s...). That probably simplifies out-of-order implementations, since the only things that can trap then are the instruction decoder (instruction fetch errors and invalid instructions), the load/store instructions, and special instructions (system calls, breakpoints, and like).
(It also doesn't propagate NaN payloads, always returning the same canonical NaN whenever an operation produces a NaN).
That's ok, because NaNs are exceptional responses to numerical errors thrown during number crunching, indicating that something failed unexpectedly and the output is crap.
The overall idea of choosing a number distribution that loses less precision for common operations and orders of magnitude is pretty compelling, though.
The next big TODOs are addition, substraction and rounding. Then advanced operations like sqrt, fma, etc. As part of the posit spec.
I've been working alone on that project, this being my first time working with floating point representation. I'm happy I could even get to that stage, and I hope someone can pick up my work and start contributing.
https://github.com/Etaphase/FastSigmoids.jl
contains both a julia library and a C/C++ library. Posits are implemented as a C type and a C++ class where the type and class sizes correspond to the bitwidth.
FastSigmoids uses float and double types which would be problematic in embedded environments.
I'll unpack just the first example that jumped out at me:
> Currently, half-precision (16-bit) IEEE floats are often used for this purpose, but 8-bit posits have the potential to be 2−4× faster. An important function for neural network training is a sigmoid function, a function f(x) that is asymptotically 0 as x → −∞ and asymptotically 1 as x → ∞. A common sigmoid function is 1/(1 + e−x) which is expensive to compute, easily requiring over a hundred clock cycles because of the math library call to evaluate exp(x), and because of the divide.
"have the potential to be" 2-4x faster? Sure. But until we see an implementation, 1-2x is much more likely (closer to the 1x end of the spectrum). Commodity hardware runs 32b IEEE float multiplications with 3-4 cycles latency and single-cycle throughput (or better). 16b can be made faster if designers care to. There's simply not much "faster" available for posits to inhabit (2-4x faster than 16b float would be faster than small integer arithmetic).
Evaluating a sigmoid function requires "over a hundred clock cycles" only in the most naive possible implementation sitting on top of a lousy math library. Using 32b floats on a current generation phone or laptop with a decent math library, a naive scalar implementation of the sigmoid function has a latency of less than 50 cycles. But latency doesn't matter at all in a machine learning context; we're interested only in throughput. On a machine with AVX-512, a single core can evaluate a sigmoid function with a throughput of about 1.25 cycles / input. In full-precision 32b floating-point (i.e. a relative error of ~10^-7). John's proposed posit implementation has a relative error of about 10^-1. If we target that error threshold, we can trivially go below 1 cycle/input in 32b or 16b float on a phone. So IEEE floats are at least two orders of magnitude faster than he claims. You need to go back more than 15 years for the numbers that the paper tosses around to even be plausible.
There are several other examples like this in the paper. I don't want to be too antagonistic, because posits are not a bad idea (actually, I think they're a pretty good format), but this paper is either ignorant of the state of the art, or more marketing than science.
A couple of points: 2-4x faster means 2x faster in dot product based simd and 4x faster in matrix simd, assuming that your bottleneck is memory throughput.
The sigmoid function realistically isn't a bottleneck in general, but you gotta admit it is pretty cool to have a ~zero clock cycle approximation. (I've tried to rein in John a bit on this one)
[a b, c d] dot [e, f]
is four multiplies
[a b c, d e f, g h i] dot [j, k, l]
is nine multiplies.
https://news.ycombinator.com/item?id=14013971
John Gustafson (the author) has an account
I find Gustafson's UNUMS 2.0 more compelling than the first version.
Type 2 unums are pretty much entirely deprecated by type 3 unums (now given the name 'posits' as referred to in the OP's linked paper)... they are basically superior in every way, and I recommend watching John's February 2nd talk at Stanford.