🔢 mathematics

Robustness of Double-Word Addition Algorithms under Overlapping Inputs

本文确立了当输入分量重叠时双字加法算法的鲁棒性与误差界限，证明了 Fast2Sum 在特定条件下仍保持精确，并表明在 AVX-512 硬件上实现的简化乘加内核在对精度影响极小的情况下实现了显著的吞吐量提升。

原作者： Yuanyuan Yang, Xinyu Lyu, Sida He, Xiliang Lu, Ji Qi, Zhihao Li

发布于 2026-09-07

📖 1 分钟阅读🧠 深度阅读

原作者： Yuanyuan Yang, Xinyu Lyu, Sida He, Xiliang Lu, Ji Qi, Zhihao Li

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

现代计算机使用一种既强大又并不完美的数字语言。当处理器计算一个数值时，它必须将该数字放入一个固定的空间内，就像试图将一加仑的水倒入一个夸脱大小的量杯中一样。多出的部分会溢出，而计算机只保留能装下的部分，丢弃其余部分。这种被称为“舍入”（rounding）的过程是机器处理现实世界数量的标准方式，但它会在每一次计算中引入微小的误差。对于大多数日常任务而言，这些误差是不可见的。然而，在天气预报、航空航天工程或复杂的金融建模等领域，这些微小的错误可能会不断累积，最终导致最终结果产生足以影响决策的偏差。为了应对这一问题，科学家们开发了通过使用两个标准的计算机数字共同作为一个更大的单一单元来表示数值的方法。这种技术被称为“双字算术”（double-word arithmetic），它允许对现实进行更精确的表示，但需要仔细处理以确保这两个部分的数字保持正确对齐。

核心挑战在于如何将这些成对的数字相加。想象两个人在搬运重物，其中一人承担主要重量，另一人承担剩余部分。如果负载发生偏移，承担主要重量的人可能会突然变得比承担剩余部分的人还要轻，或者两者发生重叠，从而导致平衡混乱。在高性能计算的世界里，这种“重叠”发生在其中一个数字的小部分大到足以干扰另一个数字的主要部分时。传统上，旨在将这些配对数字相加的算法要求严格的顺序：第一个数字的主要部分必须大于第二个数字的主要部分。如果违反了这种顺序，计算机必须执行额外的、昂贵的步骤来重新组织这些数字。这种被称为“归一化”（normalization）的重新组织过程在计算上是非常昂ո的，会显著减慢复杂的计算速度。

来自华为技术有限公司和武汉大学的研究团队调查了这些严格的排序规则是否总是必要的。他们专注于两种用于对这些双字数字进行加法的特定方法：一种他们称之为“快速加法”的更快、更简单的方法，以及一种更严谨、更慢的称为“精确加法”的方法。“快速”方法之所以受欢迎，是因为它使用的计算机操作更少，因此速度更快，但通常被认为在输入存在重叠或数字大小接近但符号相反（即所谓的“抵消”现象）时具有风险。研究人员致力于确定这些方法在产生错误结果之前究竟能容忍多少程度的重叠。他们不仅仅是靠猜测；他们构建了一个数学证明，以展示快速方法保持可靠性的精确条件。

他们的发现表明，“快速”方法比此前认为的要更加稳健，但仅限于特定的限制范围内。他们证明了即使在输入存在重叠的情况下，只要重叠不超过一个明确定义的边界，该方法在许多常见场景下在数学上仍然是精确的。具体而言，他们确定了一个充分条件：只要数字的小部分不超过其主要部分的特定比例，快速方法就能完美运行，而无需额外的重新组织步骤。然而，他们明确警告说，这种稳健性在任意抵消情况下并不成立。如果数字相互抵消的程度非常严重，误差可能会变得很大，且该方法无法在这些极端情况下保证统一的相对误差界限。在抵消并不严重的场景中，快速方法引入的误差极其微小，其增长速率对于大多数实际用途而言是可以忽略不计的。事实上，他们的分析显示，在标准计算机格式中，该误差通常接近于机器精度的极小部分，远小于标准单精度计算中的误差。

研究人员还检查了旨在实现精确但更为复杂的“精确”方法。他们发现，该方法在重叠条件下同样保持稳定，但需要一套略有不同的规则来确保最终结果的正确性。至关重要的是，他们证明了通过理解这些边界，工程师可以在许多实际应用中安全地跳过昂贵的重新组织步骤，前提是输入保持在已证实的“安全区”内。为了测试这一理论，他们在一种常见的数学运算——乘加运算（multiplication-addition）中，刻意跳过了最后的重新组织步骤，转而使用了更快的加法方法。他们在一种专为高速并行处理设计的现代计算机处理器上运行了该程序。结果令人瞩目：修改后的代码比传统的、经过完全重新组织的版本快了大约 84%。

尽管实现了如此巨大的速度提升，但在他们的随机实验中，结果的准确性几乎没有变化。当他们测量快速、未经过重新组织的计算结果与真实数学值之间的差异时，误差如此之小，以至于几乎无法与较慢、更谨慎的方法所产生的误差相区分。这表明，对于许多高性能计算任务，例如评估复杂的数学函数或模拟物理系统，只要输入不落入快速方法已知失效的特定“严重抵消”机制中，严格要求在每一步之后重新组织数字就是没有必要的。研究人员还确认，这些快速方法保持了一个对安全性要求极高的应用非常有用的特性：它们始终以可预测的方向进行舍入，即要么始终略微向上，要么始终略微向下。这种可预测性对于区间算术（interval arithmetic）至关重要，该技术用于保证计算出的范围包含真实答案，从而确保没有任何可能的误差被遗漏。

这项研究并非声称快速方法在所有情况下都是完美的。在某些特定的极端情况下，数字几乎完全相互抵消，在这些罕见的情况下，快速方法可能会产生较大的误差。然而，研究人员提供了这些危险区域的清晰地图，并表明对于绝大多数实际输入而言，快速方法是安全的。他们还指出，其结果依赖于计算机不会遇到导致数字溢出或下溢的极端值，这是任何浮点计算中的标准限制。通过证明“快速”加法算法在广泛的重叠输入下具有稳健性，该团队为在不牺牲可靠性的前提下提高高性能计算速度提供了坚实的理论基础。这项工作使得软件开发人员能够做出明智的决策，在选择更快的路径时，能够确信数学保证依然成立，从而有效地弥合了速度需求与精度需求之间的鸿沟。

技术摘要：重叠输入下双精度加法算法的鲁棒性

问题陈述
双精度算术（Double-word arithmetic）将实数表示为两个工作精度浮点数（ $x_h + x_l$ ）的未求值和，以实现比标准硬件格式更高的精度。虽然归一化展开（满足 $|x_l| \le u|x_h|$ ）已被广泛研究，但中间计算过程往往会产生“重叠”展开，即低位分量并不严格小于高位分量。在每次运算后都进行归一化在计算上是非常昂贵的。

存在两种基础的双精度加法算法：“非归一化加法”（算法 4）和“精确加法”（算法 5），两者均源自 QD 库。非归一化加法速度更快，但传统上建议在操作数符号相反时避免使用，因为这可能导致抵消（cancellation）且缺乏统一的误差界限。精确加法则更为鲁棒，但需要更多的运算。核心问题在于确定这些算法在何种条件下保持鲁棒——具体而言，是在其内部归一化步骤（使用 Fast2Sum）保持精确或有界的情况下——尽管存在输入重叠以及高位分量之间发生抵消的情况。

方法论
作者在具有无界指数和精度 $p$ 的理想基数为 2 的浮点模型中分析了这些算法。他们利用标准的无误差变换（Fast2Sum、2Sum、2Prod），并定义了特定的重叠参数（ $o_x, o_y$ ），使得 $|x_l| \le o_x u |x_h|$ 且 $|y_l| \le o_y u |y_h|$ 。

关键分析工具包括：

改进的 Fast2Sum 分析： 作者证明了一个充分条件（引理 3.1），在该条件下，即使违反了传统的幅度排序（ $|a| \ge |b|$ ），只要满足“末位比特”条件（ $uls(a) \ge ulp(b)$ ），Fast2Sum 仍能保持精确。
鲁棒性证明： 他们确立了在显式重叠界限（ $o \le (8u)^{-1} - 2$ ）下，非归一化加法和精确加法的归一化步骤在舍入到最近（RN）模式下保持精确，并且在定向舍入（RD/RU）模式下满足单侧 $O(u^2)$ 界限，前提是避免了严重抵消（ $r(x_h, y_h) > 1/2$ ）或对其进行了处理。
误差分析： 文中推导了非归一化加法的分段相对误差界限，区分了非严重抵消（ $r \le 1/2$ ）和严重抵消机制。对于定向舍入，分析了一个基于比较的精确加法变体（算法 6），以将二阶误差界限与单侧属性分离。
应用于 MAA： 该分析应用于乘加（MAA）内核，其中在应用非归一化加法之前，省略了双精度乘法的最终归一化步骤。
数值实验： 在 AVX-512 平台（华为 FusionServer）上进行了基准测试，通过矩阵乘法（GEMM）来测量吞吐量和分量级前向误差。

主要贡献

重叠下的鲁棒性： 作者证明了非归一化加法和精确加法在广泛的、显式参数化的重叠范围内保持鲁棒。具体而言，只要重叠程度与 $u$ 独立且避免了严重抵消，这两种算法中的归一化步骤在 RN 下是精确的，并在定向舍入下满足二阶界限。
放宽的 Fast2Sum 条件： 建立了一个新的充分条件，使 Fast2Sum 无需依赖标准的算子幅度排序即可保持精确，而是依赖于较大操作数的最小有效位与较小操作数的单位最后一位（ulp）之间的关系。
非归一化加法的误差界限： 详细的误差分析表明，在 RN 模式下，在不存在严重抵消的情况下，非归一化加法的相对误差界限为 $4u^2 + O(u^3)$ 。Binary64 的示例显示误差接近 $3u^2$ 。
定向舍入变体： 对于定向舍入中的一种基于比较的精确加法变体，推导出了一个显式的有限精度界限 $(3o + 15)u^2 + O(u^3)$ ，其中 $o$ 是重叠参数。
单侧误差属性： 本文正式记录了这些加法内核在定向舍入下的单侧误差属性，这对于区间算术应用至关重要。
MAA 优化： 研究分析了一个省略双精度乘法最终归一化的 MAA 内核。理论分析表明，虽然这会增加重叠参数，但在良态场景下（例如多项式求值），分量级前向误差仍然很小。

结果

理论层面： 分析确认，在重叠受限且不存在严重抵消的情况下，非归一化加法是许多场景下替代精确加法的可行方案。推导出的界限是显式的，并依赖于重叠参数 $o$ 。
实验层面： 在 AVX-512 平台上，通过省略乘法归一化并使用非归一化加法的 MAA 实现，其吞吐量相比完全归一化的精确加法方法提升了约 84%。
准确度： 对随机输入的数值实验显示，在省略归一化或使用非归一化加法时，测得的分量级前向误差变化极小。然而，作者强调，这些随机测试并不能建立最坏情况下的安全性；必须满足理论上的重叠和抵消假设才能获得保证的界限。
向量化： 使用 vrangepd 指令（AVX-512）替换 Fast2Sum 中的条件分支，使双精度 GEMM 操作的性能提升了 6–15%。

意义与主张
本文声称将三个经常在双精度算术中被混淆的不同问题进行了区分：归一化的精确性、分量级前向误差以及抵消下的相对误差。它为在输入重叠的情况下使用更快的“非归一化”加法提供了严谨的依据，前提是满足特定的重叠大小和抵消条件。

作者谦虚地指出，其结果允许在特定 MAA 内核中获得显著的性能增益（高达 84%），且不会对良态问题的分量级准确度造成实质性损失。他们明确表示，其研究并未声称非归一化加法在任意抵消情况下都具有统一的相对误差界限，也未断言未经修改的原始 QD 精确加法算法在没有特定比较修改的情况下仍能满足推导出的定向舍入界限。其意义在于，通过放宽严格的归一化要求，同时保持可证明的误差界限，从而在现代 SIMD 硬件上实现高性能、高精度的算术运算。

类似论文