Re: Faster div or 1/sqrt approximations (was: Continuations)

Michael S <already5chosen@yahoo.com> schrieb:

On Fri, 19 Jul 2024 20:25:51 -0000 (UTC)
Thomas Koenig <tkoenig@netcologne.de> wrote:
>

MitchAlsup1 <mitchalsup@aol.com> schrieb:
 

I, personally, have found many Newton-Raphson iterators that
converge faster using 1/SQRT(x) than using the SQRT(x) equivalent. 

 
I can well believe that.
 
It is interesting to see what different architectures offer for
faster reciprocals.
 
POWER has fre and fres (double and single version) for approximate
divisin, which are accurate to 1/256.  These operations are quite
fast, 4 to 7 cycles on POWER9, with up to 4 instructions per cycle
so obviously fully pipelined.  With 1/256 accuracy, this could
actually be the original Quake algorithm (or its modification)
with a single Newton step, but this is of course much better in
hardware where exponent handling can be much simplified (and
done only once).
 
x86_64 has rcpss, accurate to 1/6144, with (looking at the
instruction tables) 6 for newer architectures, with a throuhtput
of 1/4. 

>
It seems, you looked at the wrong instruction table.

[Note I was not writing about inverse squre root, I was writing
about inverse].

I have to admit to being almost terminally confused by Intel
generation names, so I am likely to mix up what is old and what
is new.

Here are not the very modern x86-64 cores:
Arch     Latency Throughput (scalar/128b/256b)
Zen3      3       2/2/1
Skylake   4       1/1/1
Ice Lake  4       1/1/1
Power9    5-7     4/2/N/A

Power9 has it for 128-bit, but not for 256 bits (it doesn't have
those registers), and if I read the handbook correctly, that
would also be 4 operations in parallel.

>

So, if your business depends on calculating many inaccurate
square roots, fast, buy a POWER :-)
 

>
If you are have enough of independent rsqrt to do, all four processors
have the same theoretical peak throughput, but x86 tend to have more
cores and to run at faster clock. And lower latency makes achieving
peak throughput easier. Also, depending on target precision, higher
initial precision of x86 estimate means that sometimes you can get away
with 1 less NR iteration.
>
Also, if what you really need is sqrt rather than rsqrt, then depending
on how much inaccuracy you can accept, sometimes on modern x86 the
calculating accurate sqrt can be better solution than calculating
approximation. It is less likely to be the case on POWER9 Accurate sqrt

[table reformatted, hope I got this right]

(single precision)
Zen3      14      0.20/0.200/0.200
SkyLake   12      0.33/0.333/0.167
Ice Lake  12      0.33/0.333/0.167
Power9    26      0.20/0.095/N/A
>
Accurate sqrt (double precision)
Zen3      20      0.111/0.111/0.111
Skylake   12      0.167/0.167/0.083
Ice Lake  12      0.167/0.167/0.083
Power9    36      0.111/0.067/N/A
>
>

Other architectures I have tried don't seem to have it.
 

>
Arm64 has it. It is called FRSQRTE.

Interesting that "gcc -O3 -ffast-meth -mrecip" does not
appear to use it.

>
>

Does it make sense? Well, if you want to calculate lots of Arrhenius
equations, you don't need full accuracy and (like in Mitch's case)
exp has become as fast as division, then it could actually make a
lot of sense.  It is still possible to add Newton steps afterwards,
which is what gcc does if you add -mrecip -ffast-math.

>
I don't know about POWER, but on x86 I wouldn't do it.
I'd either use plain division that on modern cores is quite fast
or will use NR to calculate normal reciprocal. x86 provides initial
estimate for that too (RCPSS).

Note that I was talking about the inverse in the first place.