🔢 mathematics

Performance evaluation of branch-free fused multiply-add algorithms for multi-component-type multiple-precision floating-point arithmetic

This paper proposes and benchmarks new branch-free fused multiply-add algorithms for double-word, triple-word, and quadruple-word multiple-precision arithmetic, demonstrating that they achieve further performance improvements over existing methods by eliminating conditional branches.

Original authors: Tomonori Kouya

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tomonori Kouya

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to build a super-precise calculator using only standard, off-the-shelf Lego bricks. These bricks are your computer's normal floating-point numbers. Usually, when you stack them to make a "double-word" (two bricks), "triple-word" (three bricks), or "quadruple-word" (four bricks) number, you have to constantly check the size of the pieces as you build. If a piece is too big or too small, you have to stop, pause, and rearrange the stack. In the world of computer chips, these "pauses" are called branches.

When you try to build a million of these stacks at once (like on a modern graphics card or a powerful processor), these pauses become a nightmare. It's like a traffic jam where every car has to stop and check a different sign before moving. Some cars go left, some right, and the whole line grinds to a halt. This is called "lane divergence," and it kills performance.

The Big Discovery: The "No-Stop" Highway
Tomonori Kouya's paper introduces a new way to build these stacks that never stops to check the signs. It's a "branch-free" algorithm. Instead of asking "Is this piece big enough?" and waiting for an answer, the new method uses a clever, pre-planned route that works perfectly no matter what the pieces look like.

The paper proves, using a super-smart robot mathematician (called an SMT solver named FPANVerifier), that this new route is safe and accurate for all standard computer formats. The main finding is that by removing these "stop-and-check" pauses, the computer can calculate much faster.

The Magic Trick: Fusing the Move
The paper focuses on a specific move called Fused Multiply-Add (FMA). Imagine you have to multiply two numbers and then add a third. Usually, you do this in two steps:

Multiply (and maybe pause to fix the result).
Add (and maybe pause again).

The author proposes a "Fused" version that does both in one smooth motion, like a ninja who throws a knife and catches it in the same breath.

For Double-Word (2 bricks): The old way took 29 steps. The new way takes only 17.
For Triple-Word (3 bricks): The old way took 96 steps. The new way takes 66.
For Quadruple-Word (4 bricks): The old way took 209 steps. The new way takes 146.

The paper also discusses a "shortcut" method proposed by other researchers (the 6-step method). Crucially, this shortcut is NOT generally valid. It is a high-speed tool that only works if the numbers are already perfectly arranged in a specific way (specifically, if the added number is at least twice as large as the product). If you try to use this shortcut on general math problems like division or square roots, where you can't guarantee those numbers will line up, the accuracy degrades badly. The author's new method, however, works for any numbers without needing special arrangements, making it a true "drop-in" replacement for general high-precision math.

How Sure Are We?
The authors are incredibly confident, but they back it up with hard evidence, not just guesses.

Machine-Verified: They didn't just write code and hope; they used a computer program to mathematically prove that the error in their new method is tiny (specifically, bounded by formulas like $34u^2$ , $184u^3$ , and $812u^4$ , where $u$ is the tiny rounding error of a single number).
Tested Everywhere: They ran these new algorithms on two very different super-computers: an Arm-based chip (GB10) and an Intel-based chip (H100).
The Results:
- On the Arm chip, the new method was 1.5 to 2.1 times faster for division and square root calculations.
- On the Intel chip, it was 1.2 to 1.6 times faster for division and square root.
- For big math tasks like matrix multiplication (GEMM), the speedup was even more dramatic on the Arm chip, reaching up to 2.0 times faster for triple-word numbers.

The "Exact" Alternative
The paper also mentions a "Perfect" version of this trick called the Exact FMA. This version is even more precise, but it comes with a heavy price tag: it is 6 to 11 times slower than the new proposed method. The authors suggest using this "Perfect" version only when you absolutely, 100% need the highest possible accuracy and don't care about speed. For almost everything else, the new "branch-free" method is the winner.

What About the "Old" Way?
The paper also corrects a mistake from an earlier version of this research. Previously, the authors compared their new method to a "fully distilled" old method that was incredibly slow and inefficient. They realized that wasn't a fair fight. When they compared their new method against the actual standard "branch-free" method (which is already pretty fast), the new method still won, but the speedup was more modest (around 1.3 to 1.7 times faster). This is still a huge win, but it's a realistic one.

The Bottom Line
This paper shows that by removing the "stop-and-check" pauses in high-precision math, we can make computers significantly faster without losing accuracy. It's like upgrading from a car that has to stop at every single intersection to a car that can fly over them. The authors have proven this works, tested it on real hardware, and shown that it's ready to be used in the next generation of super-fast calculators.

Technical Summary: Performance Evaluation of Branch-Free Fused Multiply-Add Algorithms for Multi-Component-Type Multiple-Precision Floating-Point Arithmetic

1. Problem Statement

Multi-component multiple-precision arithmetic (e.g., Double-Word/DW, Triple-Word/TW, Quadruple-Word/QW) achieves high performance by bundling standard binary64 (or binary32) components and handling carries exactly via Error-Free Transformations (EFTs). However, the renormalization stages in these algorithms typically rely on if-branches dependent on intermediate value magnitudes. These branches cause significant performance penalties in SIMD and GPU implementations due to lane or warp divergence.

While Zhang and Aiken previously proposed branch-free algorithms for DW/TW/QW addition and multiplication, the composition of these separate branch-free operations remains suboptimal. Specifically, performing a fused multiply-add (FMA) operation $z \leftarrow x \cdot y + c$ by sequentially composing a branch-free multiplication and a branch-free addition incurs a high operation count (e.g., 29 flops for DW, 96 for TW, 209 for QW) and redundant renormalization steps.

2. Methodology

The paper proposes new, branch-free fused multiply-add algorithms for DW, TW, and QW arithmetic (and their single-precision base variants DS, TS, QS). The core methodology involves:

Algorithmic Structure: The proposed FMA computes $z \leftarrow x \cdot y + c$ $z \leftarrow x \cdot y + c$ in a single fused stage rather than composing separate multiplication and addition. The process involves:
1. Product Expansion: Decomposing products of components using TwoProd.
2. Weight-wise Accumulation: Gathering terms arriving at the same power-of-two position using chains of TwoSum.
3. Renormalization: Reshaping the result into $K$ non-overlapping components.
Gate Selection and Verification: A critical design principle is the selection of renormalization gates based on machine-verifiable preconditions. The algorithm uses FastTwoSum (3 flops) only where the precondition $\text{exp}(a) \ge \text{exp}(b)$ can be machine-proven for all precisions $p$ using the SMT solver z3 via the FPANVerifier tool. Where the precondition cannot be proven, TwoSum (6 flops) is used to ensure correctness.
Commutativity: To ensure bitwise agreement under operand exchange ( $x \leftrightarrow y$ ), the algorithm re-associates diagonal sums so that transposed pairs (e.g., $P_{ij}$ and $P_{ji}$ ) are processed first. This is achieved without increasing the operation count.
Exact Variant: A "distillation" variant (Exact FMA) is also implemented as a reference. It performs a full error-free expansion followed by multiple TwoSum sweeps to achieve result-relative error bounds, though at a significantly higher computational cost.

3. Key Contributions

3.1 Minimal Branch-Free FMA Constructions

The paper presents minimal, machine-verified branch-free FMA algorithms with the following operation counts (fused FMA instruction counts as 1):

DW (K=2): 17 flops (vs. 29 for composed branch-free mul+add).
TW (K=3): 66 flops (vs. 96).
QW (K=4): 146 flops (vs. 209).

These counts represent the minimal constructions where every FastTwoSum precondition is machine-verified.

3.2 Machine-Verified Error Bounds

Using FPANVerifier, the authors certify error bounds relative to $(|xy| + |c|)$ for all precisions:

DW: $34 u^2 (|xy| + |c|)$
TW: $184 u^3 (|xy| + |c|)$
QW: $812 u^4 (|xy| + |c|)$
The validity of every FastTwoSum precondition and the bitwise agreement between the proven variant and a naive variant (where FastTwoSum is placed at the tail regardless of proof) are confirmed.

3.3 Commutativity

The proposed algorithms are bitwise commutative in $x$ and $y$ for all six types (DD/TD/QD/DS/TS/QS). This is achieved by symmetrizing the association order of plain additions, ensuring $fma(x, y, c) \equiv fma(y, x, c)$ without adding operations.

3.4 Specialized Variants for Division and Square Root

The paper identifies that intermediate residuals in division and square root algorithms may not satisfy the non-overlapping assumptions required for standard FMA proofs. Consequently, a "safe" variant is proposed for these contexts (DW 20 / TW 69 / QW 149 flops), which demotes unproven FastTwoSum gates to TwoSum to guarantee accuracy without re-verifying the entire structure for every usage context.

4. Experimental Results

The algorithms were evaluated on two platforms:

Arm: NVIDIA GB10 (Grace-Blackwell, Cortex-X925 CPU, Blackwell GPU).
x86: H100 node (Intel Xeon Gold 6526Y CPU, H100 GPU).
Implementations: Scalar, AVX2, AVX-512, NEON, SVE2, and CUDA.

4.1 Linear Algebra Kernels (AXPY, GEMV, GEMM)

Speedup: The proposed FMA consistently outperforms the branch-free baseline (BF) in compute-bound scenarios.
- AVX2 (x86): Speedups of $\times 1.49$ (DD), $\times 1.32$ (TD), and $\times 1.47$ (QD) in GEMM.
- NEON (Arm): Speedups of $\times 1.40$ (DD), $\times 1.42$ (TD), and $\times 1.47$ (QD) in GEMM.
- SVE2: Similar performance to NEON at equal lane width, with QD GEMM reaching $\times 1.62$ speedup over BF.
- GPU (GB10): On the compute-bound double-precision types, speedups match theoretical FLOP ratios ( $\times 1.71$ for DD, $\times 1.46$ for TD, $\times 1.40$ for QD). On bandwidth-bound workloads (single-precision or H100), speedups are closer to $\times 1.00$ .
Accuracy: The proposed FMA maintains working accuracy comparable to existing branch-free methods (Q/BF). In cancellation scenarios, the error behavior is numerically identical to the baseline. The Exact FMA offers superior result-relative accuracy but incurs a 2.5–5.0 $\times$ slowdown.

4.2 Division and Square Root

Division: The proposed FMA accelerates long division significantly, particularly for higher precision.
- NEON/SVE2: Speedups of $\times 1.54$ to $\times 2.11$ (QD division reaches $\times 2.11$ , exceeding the operation-count ratio of 1.51 due to the folding of two serial normalization chains into one).
- GB10 (Compute-only): Speedups of $\times 1.25$ to $\times 1.61$ .
Square Root: The proposed FMA achieves speedups of $\times 1.51$ to $\times 1.61$ with zero loss in accuracy compared to the baseline. This is because the Newton iteration converges well below the rounding unit, making the final error dominated by the last multiplication common to all methods.

4.3 Single-Precision Base (DS/TS/QS)

The algorithms were successfully extended to single-precision components, maintaining working accuracy and achieving speedups of $\times 1.37$ to $\times 1.83$ over the BF baseline.

5. Significance and Claims

The paper claims that the proposed branch-free fused FMA represents a minimal, machine-verified construction that successfully folds the two stages of existing branch-free multiplication and addition into a single operation.

Performance: It provides real-world speedups (up to $\times 2.11$ in division on CPUs and $\times 1.71$ in GEMM on GPUs) by reducing operation counts and shortening dependence chains, particularly beneficial for higher precision (TW/QW).
Correctness: The algorithms are rigorously verified. The error bounds and FastTwoSum preconditions are machine-proven for all precisions, and bitwise agreement across scalar, SIMD, and GPU implementations is confirmed via extensive testing (200,000+ trials).
Generality: The approach is not limited to linear algebra; it effectively accelerates division and square root algorithms, which rely heavily on MAC operations.
Commutativity: Unlike some prior branch-free approaches, the proposed FMA preserves bitwise commutativity, a crucial property for reproducibility in parallel reductions.

The authors position this work as a practical replacement for composing separate branch-free operations, offering a "drop-in" acceleration for multi-component arithmetic libraries without sacrificing accuracy or provability. Future work is suggested to explore alternative renormalization structures (e.g., Priest-style) to potentially reduce operation counts further while maintaining machine verifiability.