Alex Herbert created NUMBERS-220:
------------------------------------

             Summary: Use hardware supported FMA to accelerate the 
double-double (DD) computation of multiplication round-off
                 Key: NUMBERS-220
                 URL: https://issues.apache.org/jira/browse/NUMBERS-220
             Project: Commons Numbers
          Issue Type: Improvement
          Components: core
            Reporter: Alex Herbert


The DD (double-double) class supports computation of the exact 106-bit result 
from the multiplication of two 53-bit double values. The round-off from the 
product x * y is created using Decker's split method to split each factor into 
two parts that can be multiplied exactly. The product low part is computed as a 
helper method:

 
{code:java}
xy = x * y
xy_lo = twoProductLow(x, y, xy) // 16 FLOPS{code}
The low part can be compute in 2 FLOPS using fused-multiply-add (FMA):

 

 
{noformat}
xy_lo = Math.fma(x, y, -xy){noformat}
FMA was added in Java 9 and the library targets Java 8. The method can be used 
via the MethodHandle API to lookup the public method within the Math class. 
However if hardware supported FMA is not available the software fallback to 
support exact rounding for all cases is slow as it typically uses BigDecimal. 
So detection of the method and the ability to invoke it through a MethodHandle 
is not sufficient to ensure performance gains.

 

The HotSpot JVM has a UseFMA flag that can be read using the JDK management API 
using the com.sun.management.HotSpotDiagnosticMXBean. This flag is documented 
as a configurable option and can be enabled/disabled using `-XX:+UseFMA` on 
HotSpot JVMs. The default setting is enabled on hardware that supports FMA 
instructions.

If the FMA method is detected on first use of the DD class, and a reference to 
the method to compute (a * b + c) is held in a static final constant, then 
invocation of the method is efficiently inlined to the correct FMA call. A JMH 
performance test showed no measurable difference between calling Math.fma 
directly and using a static final reference to an interface accepting the 3 
arguments:

 
{code:java}
interface FMAOperator {
    double fma(double a, double b, double c);
}

static final FMA = // create method to use{code}
I propose to modify DD to detect hardware supported FMA. All functions that 
compute the round-off from multiplications can switch from the 16 FLOP current 
implementation to the 2 FLOP FMA call. A performance test should be used to 
demonstrate the difference between enabled and disabled, and verify the current 
software-only DD implementation performs the same as the FMA disabled version.

 
h3. Behavioural change

Results from all operations in the DD class should be identical with or without 
FMA where the non-FMA supported result is finite. The DD class is not 
documented to support non-finite IEEE arithmetic.

The current 16 FLOP implementation requires Decker's method to split a 53-bit 
number. This requires multiplication by a factor of approximately 2^27. Any 
multiplication involving factors above 2^996 can overflow in the intermediate 
during splitting. This is already known behaviour noted in the class javadoc. 
Multiply and divide operations should only be used with terms less than 2^996. 
Use of FMA would extend support for the exact 106-bit double to be computed up 
to the limit of a double. This increases the supported range. Users who 
previously relied on the DD result returning false from the isFinite() method 
after a multiply or divide may no longer obtain the same results they expect. 
The solution is to use correct scaling on arguments before combined operations 
that could overflow. This is supported by a fractional representation method 
(frexp) and scaling method (scalb) that transform the number by exact 
power-of-2 scaling operations.

There are locations other than computing product round-off where FMA can be 
used in the DD class that would increase accuracy by eliminating 1 rounding for 
chained multiply-add operations. This change does not support this usage. FMA 
should only be used in round-off computations for products where the 
performance gain is the most significant (16 to 2 FLOPS). For this reason the 
use of FMA should be internal to the DD class specialised to its particular use 
case. It should not be exposed via a public API. 
h3. Disclaimer

Claude code was used to investigate how to detect hardware-enabled FMA at 
runtime and performed a JMH benchmark on a prototype.

 



--
This message was sent by Atlassian Jira
(v10.3.26#10030026)

Reply via email to