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

Jul 16, 2026

High-performance multi-component multiple-precision arithmetic can be built from existing floating-point operations by using error-free transformations (EFTs). Branch-free designs remove if-branches that cause SIMD and GPU divergence, improving throughput. Prior work proposed branch-free addition and multiplication for double-, triple-, and quad-word formats (DW/TW/QW). This paper introduces new branch-free fused multiply-add (FMA) operations for DW/TW/QW, including verified error bounds and machine-checked FastTwoSum preconditions, and confirms acceleration via benchmarks.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages33

Reading Time1 h 23 min

Introduction

Branch-free FMA algorithms for DW, TW, and QW arithmetic

Basic operations (error-free transformations)

Overall structure of the proposed FMA

DW-FMA (proposed)

arXiv :2607 . 11391v1 [math .NA] 13 Jul 2026 Performance evaluation of branch-free fused multiply-add algorithms for multi-component-type multiple-precision floating-point arithmetic Tomonori Kouya 2026-07-13 Abstract High performance in multi-component multiple-precision arithmetic constructed from existing floating-point operations using error-free transformations (EFTs), can be achieved by employing branch-free algorithms that eliminate if-branches. Zhang and Aiken proposed branch-free algorithms for addition and multiplication in double-word(DW), tripleword(TW), and quadruple-word(QW) arithmetic. Among these, we implemented the TWand QW variants, for which substantial performance improvements over existing algorithms can be expected, and demonstrated that they indeed contribute to acceleration. In this paper, we propose new branch-free fused multiply-add operations for DW, TW, and QW arithmetic to achieve further performance improvements, and show through benchmark tests that the proposed operations can enhance performance. 1 Introduction Multi-component multiple-precision arithmetic bundles several binary64 (or binary32) components and handles carries exactly through error-free transformations (EFTs); double-word (DW), triple-word (TW), and quad-word (QW) formats—implemented as DD/TD/QD and, with a single-precision base, DS/TS/QS—belong to this family. Because it reuses the existing floatingpoint units directly, it tends to achieve much higher performance than arbitrary-precision libraries. Its internals, however—in particular the renormalization stages—contain if-branches that depend on the magnitudes of intermediate values, and these branches have been a major performance obstacle for SIMD and GPU implementations, where they manifest as lane or warp divergence. Zhang and Aiken proposed branch-free algorithms for DW/TW/QW addition and multiplication that eliminate these branches, together with machine-checked error bounds obtained with an SMT solver, and demonstrated high performance [1, 2] . We previously implemented the TWand QW variants, for which large speedups over the conventional algorithms can be expected, and confirmed that they indeed contribute to acceleration. In this paper we propose, for further acceleration, fused multiply-add (FMA) operations z ← x · y + c for DW/TW/QW (and for DS/TS/QS) . The proposed FMA requires fewer operations than the composition of branch-free addition and multiplication (DW 17 / TW 66 / QW 146 flops versus 29/96/209 flops), its error bounds and the validity of every FastTwoSum precondition are machine-verified with FPANVerifier, and it is bitwise commutative under the exchange x ↔ y. As a reference that measures the attainable accuracy, we also provide an Exact FMA variant with a result-relative error bound. The paper is organized as follows. Section 2 presents the proposed algorithms and their machine-verified error bounds; Section 3 contrasts them with existing FMA research; Section 4 reports benchmark tests on two platforms, GB10 (Arm) and H100 (x86)—the acceleration of division and square root, and the basic linear-algebra kernels AXPY/GEMV/GEMM in serial, OpenMP-parallel, and GPU-parallel settings. Section 5 concludes with future work. 2 Branch-free FMA algorithms for DW, TW, and QW arithmetic The proposed branch-free FMA computes z ← x · y + c in a single fused stage for K-component operands x, y, c (K = 2 , 3 , 4 for DW/TW/QW), and has the following properties. • Commutativity: it is commutative in x and y; fma(x, y, c) and fma(y, x, c) agree bitwise for all six types (Section 2.10) . • Machine-verified error bounds: the bounds 34u2 /184u3 /812u4 · (|xy| + |c|) and the validity of every FastTwoSum precondition are machine-verified with FPANVerifier for all precisions p (Section 2.9) . • Fewer operations: it needs only 17/66/146 flops, fewer than the combination of branchfree addition and multiplication (29/96/209 flops; Section 2.8) .

FAQs

Why do if-branches in multi-component multiple-precision arithmetic hurt SIMD and GPU performance?

Renormalization stages contain magnitude-dependent if-branches, which lead to lane or warp divergence on SIMD and GPU execution. This divergence becomes a major performance obstacle.

What key properties are claimed for the proposed branch-free FMA operations?

The operations are commutative in x and y, use machine-verified error bounds and FastTwoSum preconditions, require fewer floating-point operations than composing branch-free addition and multiplication, and have clear error semantics versus the Exact variant.

How is the proposed FMA algorithm structured for DW/TW/QW arithmetic?

It computes z ← x·y + c in three stages: product expansion via TwoProd, weight-wise accumulation using TwoSum chains for aligned powers of two, and renormalization that reshapes results into K non-overlapping components, truncating terms of sufficiently small order.

Jul 16, 2026

Upload by Genevieve