Fast Reproducible Floating-Point Summation
Fast Reproducible Floating-Point Summation
复制标题
DOI：
10.1109/arith.2013.9
复制
发表时间：
2013-04
期刊：
影响因子：
--
通讯作者：
J. Demmel;Hong Diep Nguyen
中科院分区：
文献类型：
--
作者：
J. Demmel;Hong Diep Nguyen
可复制性，即从同一程序的多次运行中获得按位相同的浮点结果，是许多用户在许多代码中依赖于调试或正确性检查的属性[1]。然而，并行计算资源的动态调度和浮点非关联性的组合使得即使对于像并行计算数字的向量的和这样的简单归约操作，也难以获得再现性。我们提出了一种浮点求和的技术，是可再生的求和的顺序无关。我们的技术使用Rump的算法进行无错误的向量变换[2]，并且比使用（可能非常）高精度算法更有效。我们的算法权衡了效率和准确性：我们可重复地获得相当准确的结果（绝对误差界为c · n2 · macheps · max| vi|对于一个小常数c），只需2n + O（1）次浮点运算，并且结果相当准确（绝对误差界为c · n3 ·maceps2· max| vi| 5n + O（1）浮点运算，两者都只有两个归约运算。通过增加无误差变换的数量，也可以提高精度。只要使用相同的舍入模式，通过所提出的算法计算的结果对于在任何平台上的任何运行都是可再现的。
Reproducibility, i.e. getting the bitwise identical floating point results from multiple runs of the same program, is a property that many users depend on either for debugging or correctness checking in many codes [1]. However, the combination of dynamic scheduling of parallel computing resources, and floating point nonassociativity, make attaining reproducibility a challenge even for simple reduction operations like computing the sum of a vector of numbers in parallel. We propose a technique for floating point summation that is reproducible independent of the order of summation. Our technique uses Rump's algorithm for error-free vector transformation [2], and is much more efficient than using (possibly very) high precision arithmetic. Our algorithm trades off efficiency and accuracy: we reproducibly attain reasonably accurate results (with an absolute error bound c · n2 · macheps · max |vi| for a small constant c) with just 2n + O(1) floating-point operations, and quite accurate results (with an absolute error bound c · n3 · macheps2 · max |vi| with 5n + O(1) floating point operations, both with just two reduction operations. Higher accuracies are also possible by increasing the number of error-free transformations. As long as the same rounding mode is used, results computed by the proposed algorithms are reproducible for any run on any platform.