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

On Sat, 20 Jul 2024 21:58:59 -0000 (UTC)
Thomas Koenig <tkoenig@netcologne.de> wrote:

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].
>

Oh, sorry. I misaunderstood.

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.
>

Gen 2 is Sandy Bridg
Gen 3 is Ivy Bridge which is very similar core microarchitecture
Gen 4 is Haswell
Gen 5 is Broadwell which is similar, but has few changes
Gen 6,7,8,9 and majority of 10 is all the same microarchitecture -
Skylake.
11 is mostly Tiger lake and partially Ice Lake and Rocket Lake. All
three are different from each other on silicon proces side, but ver
similar on core microarcheticture.
12 is Alder Lake that has P cores and E cores. Microarchitecture of P
core is called Golden Cove.

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.
>

Handbook is quite clear that both xvresp and xvredp have
max throughput=2.

 

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

That's the sentence that caused my misunderstanding.

>
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.
>

You mean, on other architectures gcc does emit approximate rsqrt from
plain C or plain Fortran? In which situations?

>
 

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.

Mitch was told more than one time that floating point division on
modern cores (esp. Apple, but others too) is much faster than he thinks.
But he tend to forget it quickly.

 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.