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)