Fast exact summation using small and large superaccumulators
Fast exact summation using small and large superaccumulators
复制标题
使用小型和大型超级累加器进行快速精确求和
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Radford M. Neal
中科院分区：
文献类型：
--
作者：
Radford M. Neal
我提出了两种对一组浮点数进行精确求和，然后正确舍入到最接近的浮点数的新方法。在许多应用中，比如求数据的样本均值，比简单求和（每次加法后舍入）更高的精度是很重要的。精确求和还能保证并行和串行实现得到相同的结果，因为精确的和与顺序无关。新方法使用了“超级累加器”概念的变体——一个大的定点数，它能够精确表示任意合理数量的浮点值的和。一种方法使用一个具有67个64位块的“小”超级累加器，每个块与下一个块有32位重叠，这样进位传播就不需要很频繁地进行。在对少量项求和时单独使用小超级累加器。对于大量求和，也会使用一个“大”超级累加器。它由4096个64位块组成，每个可能的指数位和符号位组合对应一个块，并且还有每个块需要转移到小超级累加器的次数计数。要向大超级累加器添加一项，只需要更新一个块及其相关计数，如果精心实现，这只需要很少的指令。在现代64位处理器上，使用这种大小超级累加器的组合对一个大数组进行精确求和，串行实现时所花费的时间不到简单、不精确、有序求和的两倍。使用少量处理器核心的并行实现有望以达到内存带宽所限制的速度对大数组进行精确求和。因此，一些试图在不精确的情况下提高精度的常见方法可能是没有意义的，至少对于大量求和是这样，因为它们比精确计算和要慢。
I present two new methods for exactly summing a set of floating-point numbers, and then correctly rounding to the nearest floating-point number. Higher accuracy than simple summation (rounding after each addition) is important in many applications, such as finding the sample mean of data. Exact summation also guarantees identical results with parallel and serial implementations, since the exact sum is independent of order. The new methods use variations on the concept of a "superaccumulator" - a large fixed-point number that can exactly represent the sum of any reasonable number of floating-point values. One method uses a "small" superaccumulator with sixty-seven 64-bit chunks, each with 32-bit overlap with the next chunk, allowing carry propagation to be done infrequently. The small superaccumulator is used alone when summing a small number of terms. For big summations, a "large" superaccumulator is used as well. It consists of 4096 64-bit chunks, one for every possible combination of exponent bits and sign bit, plus counts of when each chunk needs to be transferred to the small superaccumulator. To add a term to the large superaccumulator, only a single chunk and its associated count need to be updated, which takes very few instructions if carefully implemented. On modern 64-bit processors, exactly summing a large array using this combination of large and small superaccumulators takes less than twice the time of simple, inexact, ordered summation, with a serial implementation. A parallel implementation using a small number of processor cores can be expected to perform exact summation of large arrays at a speed that reaches the limit imposed by memory bandwidth. Some common methods that attempt to improve accuracy without being exact may therefore be pointless, at least for large summations, since they are slower than computing the sum exactly.