🔢 mathematics

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

本文提出并基准测试了针对双字、三字和四字多精度算术的新型无分支融合乘加算法，证明了通过消除条件分支，这些算法比现有方法实现了进一步的性能提升。

原作者： Tomonori Kouya

发布于 2026-07-14

📖 1 分钟阅读🧠 深度阅读

原作者： Tomonori Kouya

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图仅使用标准的、现成的乐高积木来建造一台超精确的计算器。这些积木就是你的计算机普通的浮点数。通常情况下，当你把这些积木堆叠成一个“双字长”（两块积木）、“三字长”（三块积木）或“四字长”（四块积木）的数字时，你必须不断检查每一块积木的大小。如果某块积木太大或太小，你就必须停下来，暂停并重新排列堆叠。在计算机芯片的世界里，这些“暂停”被称为分支（branches）。

当你试图同时构建一百万个这样的堆叠时（比如在现代图形卡或强大的处理器上），这些暂停会变成一场噩梦。这就像一场交通拥堵，每辆车在前进前都必须停下来看一眼不同的路标。有些车向左转，有些向右转，整个车队因此陷入停滞。这就是所谓的“通道分歧（lane divergence）”，它会严重破坏性能。

重大发现：“无停顿”高速公路
Tomonori Kouya 的论文介绍了一种构建这些堆叠的新方法，这种方法永远不需要停下来看路标。它是一种“无分支（branch-free）”算法。它不再询问“这块积木够大吗？”并等待答案，而是使用一种巧妙的、预先规划好的路线，无论积木看起来如何，这条路线都能完美运行。

该论文通过一个超级聪明的机器人数学家（一个名为 FPANVerifier 的 SMT 求解器）证明了这条新路线对于所有标准计算机格式都是安全且准确的。主要发现是，通过消除这些“停下并检查”的暂停，计算机可以计算得更快。

魔术技巧：融合移动
论文关注一个特定的动作，叫做融合乘加（Fused Multiply-Add, FMA）。想象一下，你需要将两个数字相乘，然后加上第三个数字。通常，你需要分两步完成：

相乘（并可能为了修正结果而暂停）。
相加（并可能再次暂停）。

作者提出了一个“融合”版本，将这两步合并为一个流畅的动作，就像一个忍者在投掷飞刀的同时还能顺势接住它一样。

对于双字长（2 块积木）： 旧方法需要 29 步。新方法仅需 17 步。
对于三字长（3 块积木）： 旧方法需要 96 步。新方法仅需 66 步。
对于四字长（4 块积木）： 旧方法需要 209 步。新方法仅需 146 步。

论文还讨论了由其他研究人员提出的一个“捷径”方法（6 步法）。至关重要的是，这个捷径并不具有普适性。 它是一个高速工具，仅在数字已经以特定方式排列好时（具体来说，如果加数至少是乘积的两倍）才有效。如果你尝试将这个捷径用于除法或平方根等通用数学问题（在这些问题中你无法保证数字会如此排列），其准确性会大幅下降。然而，作者的新方法无需特殊的排列即可适用于任何数字，使其成为一个真正的“即插即用”型通用高精度数学替代方案。

我们有多确定？
作者非常有信心，但他们是用硬核证据而非猜测来支撑这种信心的。

机器验证： 他们不仅仅是编写了代码并寄希望于成功；他们使用了一个计算机程序在数学上证明了他们新方法的误差极小（具体而言，受限于类似于 $34u^2$ 、 $184u^3$ 和 $812u^4$ 的公式，其中 $u$ 是单个数字的微小舍入误差）。
到处测试： 他们在两种截然不同的超级计算机上运行了这些新算法：一台是 基于 Arm 的芯片（GB10），另一台是 基于 Intel 的芯片（H100）。
结果：
- 在 Arm 芯片上，新方法在进行除法和平方根计算时，速度提升了 1.5 到 2.1 倍。
- 在 Intel 芯片上，新方法在进行除法和平方根计算时，速度提升了 1.2 到 1.6 倍。
- 对于像矩阵乘法（GEMM）这样的大型数学任务，在 Arm 芯片上的加速效果更为显著，对于三字长数字，速度提升高达 2.0 倍。

“精确”的替代方案
论文还提到了这个技巧的一个“完美”版本，称为 Exact FMA。这个版本更加精确，但代价沉重：它比新提出的方法要慢 6 到 11 倍。作者建议仅在您绝对、百分之百需要最高精度且不在乎速度时，才使用这个“完美”版本。对于几乎所有其他情况，这种“无分支”方法才是赢家。

关于“旧”方法
论文还纠正了之前研究版本中的一个错误。此前，作者将他们的新方法与一种极其缓慢且低效的“完全蒸馏（fully distilled）”旧方法进行了对比。他们意识到这并不是一场公平的竞争。当他们将新方法与实际的标准“无分支”方法（该方法本身已经很快了）进行对比时，新方法依然胜出，但速度提升幅度较为温和（大约为 1.3 到 1.7 倍）。这仍然是一个巨大的胜利，但这是一个更现实的胜利。

底线
这篇论文表明，通过消除高精度数学中的“停下并检查”的暂停，我们可以在不损失准确性的情况下显著提高计算机的速度。这就像是从一辆必须在每个路口都停下的汽车，升级到了一辆可以飞越路口的汽车。作者已经证明了这行得通，并在真实硬件上进行了测试，展示了它已准备好用于下一代超快速计算器。

技术摘要：面向多组件类型多精度浮点运算的无分支融合乘加算法性能评估

1. 问题陈述

多组件多精度算术（例如，双字/DW、三字/TW、四字/QW）通过捆绑标准 binary64（或 binary32）组件并利用误差无关变换（EFTs）精确处理进位，从而实现高性能。然而，这些算法中的重正化阶段通常依赖于取决于中间值量级的 if-分支。由于这些分支会导致 SIMD 和 GPU 实现中的通道（lane）或线程束（warp）分歧，从而造成显著的性能惩罚。

虽然 Zhang 和 Aiken 此前曾提出过针对 DW/TW/QW 加法和乘法的无分支算法，但这些独立无分支操作的组合仍然不是最优的。具体而言，通过顺序组合一个无分支乘法和一个无分支加法来执行融合乘加（FMA）操作 $z \leftarrow x \cdot y + c$ ，会产生较高的运算次数（例如，DW 为 29 次 flops，TW 为 96 次，QW 为 209 次）以及冗余的重正化步骤。

2. 方法论

本文提出了针对 DW、TW 和 QW 算术（及其单精度基底变体 DS、TS、QS）的新型无分支融合乘加（FMA）算法。其核心方法论包括：

算法结构： 提议的 FMA 在单个融合阶段计算 $z \leftarrow x \cdot y + c$ $z \leftarrow x \cdot y + c$ ，而不是通过组合独立的乘法和加法。该过程涉及：
1. 乘积展开： 使用 TwoProd 对组件乘积进行分解。
2. 按权累加： 使用 TwoSum 链收集到达相同 2 的幂次位置的项。
3. 重正化： 将结果重新塑形成 $K$ 个互不重叠的组件。
门电路选择与验证： 一个关键的设计原则是根据机器可验证的前置条件选择重正化门。算法仅在可以通过 SMT 求解器 z3 通过 FPANVerifier 工具在所有精度 $p$ 下均能被机器证明满足 $\text{exp}(a) \ge \text{exp}(b)$ 前置条件的情况下，才使用 FastTwoSum（3 flops）。在无法证明前置条件的情况下，则使用 TwoSum（6 flops）以确保正确性。
交换律： 为了确保在操作数交换（ $x \leftrightarrow y$ ）下的位一致性（bitwise agreement），算法对对角线和进行了重新结合，使得转置对（例如 $P_{ij}$ 和 $P_{ji}$ ）优先被处理。这是在不增加运算次数的情况下实现的。
精确变体： 同时实现了一个“蒸馏”变体（Exact FMA）作为参考。它执行完整的误差无关展开，随后进行多次 TwoSum 扫描，以达到相对于结果的误差界限，尽管其计算成本显著更高。

3. 核心贡献

3.1 极小无分支 FMA 构造

本文展示了极小、机器验证的无分支 FMA 算法，其运算次数如下（融合 FMA 指令计为 1）：

DW (K=2)： 17 flops（对比组合式无分支乘+加的 29 flops）。
TW (K=3)： 66 flops（对比 96 flops）。
QW (K=4)： 146 flops（对比 209 flops）。

这些计数代表了每一个 FastTwoSum 前置条件都经过机器验证的极小构造。

3.2 机器验证的误差界限

利用 FPANVerifier，作者认证了相对于 $(|xy| + |c|)$ 在所有精度下的误差界限：

DW： $34 u^2 (|xy| + |c|)$
TW： $184 u^3 (|xy| + |c|)$
QW： $812 u^4 (|xy| + |c|)$
每个 FastTwoSum 前置条件的有效性，以及证明过的变体与一个（无论如何都将 FastTwoSum 置于末尾的）朴素变体之间的位一致性，均得到了确认。

3.3 交换律

所提算法对于所有六种类型（DD/TD/QD/DS/TS/QS）在 $x$ 和 $y$ 之间都是位交换可交换的。这是通过对称化普通加法的结合顺序来实现的，确保了 $fma(x, y, c) \equiv fma(y, x, c)$ 而不增加运算。

3.4 除法与平方根的专用变体

论文指出，除法和平方根算法中的中间残差可能不满足标准 FMA 证明所需的非重叠假设。因此，针对这些场景提出了一个“安全”变体（DW 20 / TW 69 / QW 149 flops），它将未经验证的 FastTwoSum 门降级为 TwoSum，以在无需为每个使用上下文重新验证整个结构的情况下保证精度。

4. 实验结果

算法在两个平台上进行了评估：

Arm： NVIDIA GB10 (Grace-Blackwell, Cortex-X925 CPU, Blackwell GPU)。
x86： H100 节点 (Intel Xeon Gold 6526Y CPU, H100 GPU)。
实现方式： Scalar、AVX2、AVX-512、NEON、SVE2 以及 CUDA。

4.1 线性代数内核 (AXPY, GEMV, GEMM)

加速比： 在计算密集型场景下，提议的 FMA 始终优于无分支基准（BF）。
- AVX2 (x86)： GEMM 中的加速比分别为 $\times 1.49$ (DD)、 $\times 1.32$ (TD) 和 $\times 1.47$ (QD)。
- NEON (Arm)： GEMM 中的加速比分别为 $\times 1.40$ (DD)、 $\times 1.42$ (TD) 和 $\times 1.47$ (QD)。
- SVE2： 在等效通道宽度下，性能与 NEON 相似，其中 QD GEMM 相比 BF 达到了 $\times 1.62$ 的加速。
- GPU (GB10)： 在计算密集型的双精度类型上，加速比符合理论 FLOP 比例（DD 为 $\times 1.71$ ，TD 为 $\times 1.46$ ，QD 为 $\times 1.40$ ）。在带宽密集型工作负载（单精度或 H100）上，加速比接近 $\times 1.00$ 。
精度： 提议的 FMA 保持了与现有无分支方法（Q/BF）相当的工作精度。在消去（cancellation）场景下，其误差行为在数值上与基准完全一致。Exact FMA 提供更优的相对于结果的精度，但会带来 2.5–5.0 $\times$ 的减速。

4.2 除法与平方根

除法： 提议的 FMA 显著加速了长除法，特别是在高精度情况下。
- NEON/SVE2： 加速比为 $\times 1.54$ 至 $\times 2.11$ （QD 除法达到 $\times 2.11$ ，由于将两个串行重正化链折叠为一个，超过了 1.51 的运算计数比）。
- GB10 (仅计算)： 加速比为 $\times 1.25$ 至 $\times 1.61$ 。
平方根： 提议的 FMA 实现了 $\times 1.51$ 至 $\times 1.61$ 的加速，且与基准相比零精度损失。这是因为 Newton 迭代在远低于舍入单位处收敛，使得最终误差由所有方法共有的最后一次乘法主导。

4.3 单精度基底 (DS/TS/QS)

算法成功扩展到了单精度组件，保持了工作精度，并实现了相对于 BF 基准 $\times 1.37$ 至 $\times 1.83$ 的加速。

5. 重要性与主张

本文声称，所提出的无分支融合 FMA 代表了一种极小、机器验证的构造，它成功地将现有无分支乘法和加法的两个阶段折叠进了一个单一操作中。

性能： 它通过减少运算次数和缩短依赖链，提供了真实的加速（在除法中高达 $\times 2.11$ ，在 GEMM 中在 GPU 上高达 $\times 1.71$ ），这对于更高精度（TW/QW）尤其有利。
正确性： 算法经过严格验证。误差界限和 FastTwoSum 前置条件在所有精度下均经过机器证明，并通过超过 200,000 次试验确认了标量、SIMD 和 GPU 实现之间的位一致性。
通用性： 该方法不仅限于线性代数；它有效地加速了高度依赖 MAC 操作的除法和平方根算法。
交换律： 与之前的某些无分支方法不同，所提 FMA 保留了位交换可交换性，这是并行归约中实现可复现性的关键属性。

作者将这项工作定位为对组合式独立无分支操作的实用替代方案，在不牺牲精度或可证明性的情况下，为多组件算术库提供了一种“即插即用”式的加速。未来的工作建议探索替代的重正化结构（例如 Priest 式），以期在保持机器可验证性的同时进一步降低运算次数。